×

Labelled graph strategic rewriting for social networks. (English) Zbl 1430.68134

Summary: We propose an algebraic and logical approach to the study of social networks, where network components and processes are directly defined by labelled port graph strategic rewriting. Data structures attached to graph elements (nodes, ports and edges) model local and global knowledge in the network, rewrite rules express elementary and local transformations, and strategies control the global evolution of the network. We show how this approach can be used to generate random networks, simulate existing propagation and dissemination mechanisms, and design new, improved algorithms.

MSC:

68Q42 Grammars and rewriting systems
68P05 Data structures
68R10 Graph theory (including graph drawing) in computer science
91D30 Social networks; opinion dynamics

Software:

visone; GP 2; PORGY; ELAN
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Carrington, P.; Scott, J.; Wasserman, S., Models and Methods in Social Network Analysis, Structural Analysis in the Social Sciences (2005), Cambridge University Press
[2] Newman, M.; Barabási, A.-L.; Watts, D. J., The Structure and Dynamics of Networks, Princeton Studies in Complexity (2006), Princeton University Press · Zbl 1362.00042
[3] Scott, J.; Carrington, P. J., The SAGE Handbook of Social Network Analysis (2011), SAGE
[4] Granovetter, M., Threshold models of collective behavior, Am. J. Sociol., 83, 6, 1420 (1978)
[5] Dodds, P.; Watts, D., A generalized model of social and biological contagion, J. Theor. Biol., 232, 4, 587-604 (2005) · Zbl 1442.92162
[6] Bertuzzo, E.; Casagrandi, R.; Gatto, M.; Rodriguez-Iturbe, I.; Rinaldo, A., On spatially explicit models of cholera epidemics, J. R. Soc. Interface, 7, 43, 321-333 (2010)
[7] Chen, W.; Wang, C.; Wang, Y., Scalable influence maximization for prevalent viral marketing in large-scale social networks, (Proc. of the 16th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining. Proc. of the 16th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, KDD ’10 (2010), ACM), 1029-1038
[8] Tanenbaum, A. S.; Wetherall, D. J., Computer Network (2010), Pearson
[9] Son, S.; Shmatikov, V., The Hitchhiker’s Guide to DNS Cache Poisoning, 466-483 (2010), Springer: Springer Berlin, Heidelberg
[10] Vallet, J.; Kirchner, H.; Pinaud, B.; Melançon, G., A visual analytics approach to compare propagation models in social networks, (Rensink, A.; Zambon, E., Proc. Graphs as Models. Proc. Graphs as Models, GaM 2015. Proc. Graphs as Models. Proc. Graphs as Models, GaM 2015, EPTCS, vol. 181 (2015)), 65-79
[11] Fernández, M.; Kirchner, H.; Pinaud, B.; Vallet, J., Labelled graph rewriting meets social networks, (Lucanu, D., Rewriting Logic and Its Applications. Rewriting Logic and Its Applications, WRLA 2016. Rewriting Logic and Its Applications. Rewriting Logic and Its Applications, WRLA 2016, LNCS, vol. 9942 (2016), Springer International Publishing: Springer International Publishing Switzerland, Eindhoven, Netherlands), 1-25 · Zbl 1367.68129
[12] Andrei, O.; Fernández, M.; Kirchner, H.; Melançon, G.; Namet, O.; Pinaud, B., PORGY: strategy-driven interactive transformation of graphs, (Echahed, R., 6th Int. Workshop on Computing with Terms and Graphs, vol. 48 (2011)), 54-68 · Zbl 1457.68134
[13] Fernández, M.; Kirchner, H.; Namet, O., A strategy language for graph rewriting, (Vidal, G., Logic-Based Program Synthesis and Transformation. Logic-Based Program Synthesis and Transformation, LNCS, vol. 7225 (2012), Springer: Springer Berlin, Heidelberg), 173-188 · Zbl 1377.68098
[14] Fernández, M.; Kirchner, H.; Pinaud, B., Strategic port graph rewriting: an interactive modelling and analysis framework, (Bosnacki, D.; Edelkamp, S.; Lluch-Lafuente, A.; Wijs, A., Proc. 3rd Workshop on GRAPH Inspection and Traversal Engineering. Proc. 3rd Workshop on GRAPH Inspection and Traversal Engineering, GRAPHITE 2014. Proc. 3rd Workshop on GRAPH Inspection and Traversal Engineering. Proc. 3rd Workshop on GRAPH Inspection and Traversal Engineering, GRAPHITE 2014, EPTCS, vol. 159 (2014)), 15-29
[15] Fernandez, M.; Kirchner, H.; Pinaud, B., Strategic port graph rewriting: an interactive modelling framework, Math. Struct. Comput. Sci. (2018), to appear
[16] Kempe, D.; Kleinberg, J.; Tardos, É., Maximizing the spread of influence through a social network, (Proc. of the 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining. Proc. of the 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, KDD ’03 (2003), ACM), 137-146
[17] Goyal, A.; Bonchi, F.; Lakshmanan, L. V., Learning influence probabilities in social networks, (Web Search and Data Mining. Web Search and Data Mining, Proc. of the 3rd ACM Int. Conf. on WSDM ’10 (2010), ACM), 241-250
[18] Giakkoupis, G.; Guerraoui, R.; Jégou, A.; Kermarrec, A.-M.; Mittal, N., Privacy-conscious information diffusion in social networks, (Moses, Y.; Roy, M., 29th Int. Symp. on Distributed Computing, Toshimitsu Masuzawa and Koichi Wada. 29th Int. Symp. on Distributed Computing, Toshimitsu Masuzawa and Koichi Wada, DISC 2015. 29th Int. Symp. on Distributed Computing, Toshimitsu Masuzawa and Koichi Wada. 29th Int. Symp. on Distributed Computing, Toshimitsu Masuzawa and Koichi Wada, DISC 2015, LNCS, vol. 9363 (2015), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, Tokyo, Japan) · Zbl 1394.68427
[19] Pinaud, B.; Melançon, G.; Dubois, J., PORGY: a visual graph rewriting environment for complex systems, Comput. Graph. Forum, 31, 3, 1265-1274 (2012)
[20] Barendregt, H.; van Eekelen, M.; Glauert, J.; Kennaway, J. R.; Plasmeijer, M.; Sleep, M., Term graph rewriting, (Proc. of PARLE, Parallel Architectures and Languages Europe. Proc. of PARLE, Parallel Architectures and Languages Europe, LNCS, vol. 259-II (1987), Springer-Verlag), 141-158
[21] Lafont, Y., Interaction nets, (Proc. of the 17th ACM Symp. on Principles of Programming Languages. Proc. of the 17th ACM Symp. on Principles of Programming Languages, POPL’90 (1990), ACM Press), 95-108
[22] Barthelmann, K., How to Construct a Hyperedge Replacement System for a Context-Free Set of Hypergraphs (1996), Universität Mainz, Institut Für Informatik, Tech. Rep.
[23] Corradini, A.; Montanari, U.; Rossi, F.; Ehrig, H.; Heckel, R.; Löwe, M., Algebraic approaches to graph transformation - Part I: Basic concepts and double pushout approach, (Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations (1997), World Scientific), 163-246 · Zbl 0908.68095
[24] Plump, D., Term graph rewriting, (Ehrig, H.; Engels, G.; Kreowski, H.-J.; Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Volume 2: Applications, Languages, and Tools (1998), World Scientific), 3-61
[25] Habel, A.; Müller, J.; Plump, D., Double-pushout graph transformation revisited, Math. Struct. Comput. Sci., 11, 5, 637-688 (2001) · Zbl 0987.18005
[26] Andrei, O.; Kirchner, H., A rewriting calculus for multigraphs with ports, Proc. of RULE’07. Proc. of RULE’07, Electron. Notes Theor. Comput. Sci., 219, 67-82 (2008) · Zbl 1286.68256
[27] Andrei, O.; Kirchner, H., A higher-order graph calculus for autonomic computing, (Graph Theory, Computational Intelligence and Thought. Golumbic Festschrift. Graph Theory, Computational Intelligence and Thought. Golumbic Festschrift, LNCS, vol. 5420 (2009), Springer), 15-26 · Zbl 1194.68117
[28] Erdős, P.; Rényi, A., On the Evolution of Random Graphs, Publication of the Mathematical Institute, vol. 5, 17-61 (1960), Hungarian Academy of Sciences · Zbl 0103.16301
[29] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139
[30] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223
[31] Wang, L.; Du, F.; Dai, H. P.; Sun, Y. X., Random pseudofractal scale-free networks with small-world effect, Eur. Phys. J. B, Cond. Matter Complex Syst., 53, 3, 361-366 (2006) · Zbl 1189.68079
[32] Batagelj, V.; Brandes, U., Efficient generation of large random networks, Phys. Rev. E, 71, Article 036113 pp. (2005)
[33] Brandes, U.; Wagner, D., Analysis and visualization of social networks, (Jünger, M.; Mutzel, P., Graph Drawing Software, Mathematics and Visualization (2004), Springer: Springer Berlin, Heidelberg), 321-340
[34] Kivelä, M.; Arenas, A.; Barthelemy, M.; Gleeson, J. P.; Moreno, Y.; Porter, M. A., Multilayer networks, J. Complex Netw., 2, 3, 203-271 (2014)
[35] Plump, D., The graph programming language GP, (Bozapalidis, S.; Rahonis, G., CAI. CAI, LNCS, vol. 5725 (2009), Springer), 99-122 · Zbl 1256.68023
[36] Borovanský, P.; Kirchner, C.; Kirchner, H.; Moreau, P.-E.; Ringeissen, C., An overview of ELAN, Electron. Notes Theor. Comput. Sci., 15, 55-70 (1998) · Zbl 0917.68022
[37] Ehrig, H.; Heckel, R.; Korff, M.; Löwe, M.; Ribeiro, L.; Wagner, A.; Corradini, A., Algebraic approaches to graph transformation - Part II: single pushout approach and comparison with double pushout approach, (Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations (1997), World Scientific), 247-312, Chapter 4
[38] Löwe, M.; Korff, M.; Wagner, A., An algebraic framework for the transformation of attributed graphs, (Sleep, M. R.; Plasmeijer, M. J.; van Eekelen, M. C.J. D., Term Graph Rewriting (1993), John Wiley and Sons Ltd.: John Wiley and Sons Ltd. Chichester, UK), 185-199 · Zbl 0818.68099
[39] Fernández, M.; Kirchner, H.; Pinaud, B.; Vallet, J., Porgy Strategy Language: User Manual (Jul. 2017), Université de Bordeaux, LaBRI; Inria Bordeaux Sud-Ouest; King’s College London, Research report
[40] Sallaberry, A.; Zaidi, F.; Melançon, G., Model for generating artificial social networks having community structures with small world and scale free properties, Social Network Analysis and Mining 3 (597-609)
[41] Milgram, S., The small world problem, Psychol. Today, 2, 60-67 (1967)
[42] Kejžar, N.; Nikoloski, Z.; Batagelj, V., Probabilistic inductive classes of graphs, J. Math. Sociol., 32, 2, 85-109 (2008) · Zbl 1135.91424
[43] Cartwright, D.; Harary, F., Structural balance: a generalization of Heider’s theory, Psychol. Rev., 63, 277-293 (1956)
[44] Leskovec, J.; Huttenlocher, D.; Kleinberg, J., Signed networks in social media, (Proc. of the SIGCHI Conf. on Human Factors in Computing Systems. Proc. of the SIGCHI Conf. on Human Factors in Computing Systems, CHI ’10 (2010), ACM), 1361-1370
[45] Nick, B.; Lee, C.; Cunningham, P.; Brandes, U., Simmelian backbones: amplifying hidden homophily in Facebook networks, (2013 IEEE/ACM Int. Conf. on Advances in Social Networks Analysis and Mining (ASONAM) (2013)), 525-532
[46] Chen, W.; Collins, A.; Cummings, R.; Ke, T.; Liu, Z.; Rincón, D.; Sun, X.; Wang, Y.; Wei, W.; Yuan, Y., Influence maximization in social networks when negative opinions may emerge and propagate, (Proc. of the 11th SIAM Int. Conf. on Data Mining. Proc. of the 11th SIAM Int. Conf. on Data Mining, SDM 2011 (2011)), 379-390
[47] Wonyeol, L.; Jinha, K.; Hwanjo, Y., CT-IC: continuously activated and time-restricted independent cascade model for viral marketing, (2012 IEEE 12th Int. Conf. on Data Mining (ICDM) (2012)), 960-965
[48] Kempe, D.; Kleinberg, J.; Tardos, É., Influential nodes in a diffusion model for social networks, (Caires, L.; Italiano, G. F.; Monteiro, L.; Palamidessi, C.; Yung, M., Automata, Languages and Programming. Automata, Languages and Programming, LNCS, vol. 3580 (2005), Springer: Springer Berlin, Heidelberg), 1127-1138 · Zbl 1084.91053
[49] Watts, D. J., A simple model of global cascades on random networks, Proc. Natl. Acad. Sci. USA, 99, 9, 5766-5771 (2002) · Zbl 1022.90001
[50] Gomez-Rodriguez, M.; Leskovec, J.; Krause, A., Inferring networks of diffusion and influence, (Proc. of the 16th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining. Proc. of the 16th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, KDD ’10 (2010), ACM), 1019-1028
[51] Zachary, W., An information flow model for conflict and fission in small groups, J. Anthropol. Res., 33, 452-473 (1977)
[52] Yang, J.; Leskovec, J., Defining and evaluating network communities based on ground-truth, CoRR
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.