×

The iterated local model for social networks. (English) Zbl 1444.91173

Summary: On-line social networks, such as in Facebook and Twitter, are often studied from the perspective of friendship ties between agents in the network. Adversarial ties, however, also play an important role in the structure and function of social networks, but are often hidden. Underlying generative mechanisms of social networks are predicted by structural balance theory, which postulates that triads of agents, prefer to be transitive, where friends of friends are more likely friends, or anti-transitive, where adversaries of adversaries become friends. The previously proposed iterated local transitivity (ILT) and iterated local anti-transitivity (ILAT) models incorporated transitivity and anti-transitivity, respectively, as evolutionary mechanisms. These models resulted in graphs with many observable properties of social networks, such as low diameter, high clustering, and densification.
We propose a new, generative model, referred to as the iterated local model (ILM) for social networks synthesizing both transitive and anti-transitive triads over time. In ILM, we are given a countably infinite binary sequence as input, and that sequence determines whether we apply a transitive or an anti-transitive step. The resulting model exhibits many properties of complex networks observed in the ILT and ILAT models. In particular, for any input binary sequence, we show that asymptotically the model generates finite graphs that densify, have clustering coefficient bounded away from 0, have diameter at most 3, and exhibit bad spectral expansion. We also give a thorough analysis of the chromatic number, domination number, Hamiltonicity, and isomorphism types of induced subgraphs of ILM graphs.

MSC:

91D30 Social networks; opinion dynamics
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aiello, W.; Bonato, A.; Cooper, C.; Janssen, J.; Prałat, P., A spatial web graph model with local influence regions, Internet Math., 5, 175-196 (2009) · Zbl 1206.68221
[2] Barabási, A.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223
[3] V. Boginski, S. Butenko, P.M. Pardalos, On structural properties of the market graph, in: A. Nagurney (Ed.), Innovation in Financial and Economic Networks, Edward Elgar Publishers, pp. 29-45.
[4] Bollobás, B.; Riordan, O.; Spencer, J.; Tusnády, G., The degree sequence of a scale-free random graph process, Random Struct. Algorithms, 18, 279-290 (2001) · Zbl 0985.05047
[5] A. Bonato, A Course on the Web Graph, in: American Mathematical Society Graduate Studies Series in Mathematics, Providence, Rhode Island, 2008. · Zbl 1142.05072
[6] A. Bonato, D.W. Cranston, M. Huggan, T. Marbach, R. Mutharasan, The Iterated Local Directed Transitivity model for social networks, in: Proceedings of WAW’20, 2020.
[7] A. Bonato, N. Eikmeier, D.F. Gleich, R. Malik, Dynamic competition networks: detecting alliances and leaders, in: Proceedings of WAW’18, 2018.
[8] Bonato, A.; Gleich, D. F.; Kim, M.; Mitsche, D.; Prałat, P.; Tian, A.; Young, S. J., Dimensionality matching of social networks using motifs and eigenvalues, PLoS One, 9, 9, Article e106052 pp. (2014)
[9] Bonato, A.; Hadi, N.; Horn, P.; Prałat, P.; Wang, C., Models of on-line social networks, Internet Math., 6, 285-313 (2011)
[10] A. Bonato, N. Hadi, P. Prałat, C. Wang, Dynamic models of on-line social networks, in: Proceedings of WAW’09, 2009. · Zbl 1207.68080
[11] A. Bonato, E. Infeld, H. Pokhrel, P. Prałat, Common adversaries form alliances: modelling complex networks via anti-transitivity, in: Proceedings of WAW’17, 2017.
[12] Bonato, A.; Janssen, J.; Prałat, P., Geometric protean graphs, Internet Math., 8, 2-28 (2012) · Zbl 1245.91081
[13] Bonato, A.; Janssen, J.; Roshanbin, E., How to burn a graph, Internet Math., 1-2, 85-100 (2016)
[14] A. Bonato, E. Meger, Iterated global models for complex networks, in: Proceedings of WAW’20, 2020.
[15] Bonato, A.; Tian, A., Complex networks and social networks, invited book chapter, (Kranakis, E., Social Networks. Social Networks, Mathematics in Industry Series (2011), Springer)
[16] Broder, A.; Kumar, R.; Maghoul, F.; Raghavan, P.; Rajagopalan, S.; Stata, R.; Tomkins, A.; Wiener, J., Graph structure in the web, Comput. Netw., 33, 309-320 (2000)
[17] Chung, F. R.K., Spectral Graph Theory (1997), American Mathematical Society: American Mathematical Society Providence, Rhode Island · Zbl 0867.05046
[18] Chung, F. R.K.; Lu, L., Complex Graphs and Networks (2004), American Mathematical Society: American Mathematical Society U.S.A.
[19] Easley, D.; Kleinberg, J., Networks, Crowds, and Markets Reasoning About a Highly Connected World (2010), Cambridge University Press · Zbl 1205.91007
[20] Estrada, E., Spectral scaling and good expansion properties in complex networks, Europhys. Lett., 73, 649-655 (2006)
[21] Guo, W.; Lu, X.; Donate, G. M.; Johnson, S., The spatial ecology of war and peace (2020), Preprint
[22] Krioukov, D.; Papadopoulos, F.; Kitsak, M.; Vahdat, A.; Boguñá, M., Hyperbolic geometry of complex networks, Phys. Rev. E, 82, Article 036106 pp. (2010)
[23] J. Leskovec, J. Kleinberg, C. Faloutsos, Graphs over time: densification Laws, shrinking diameters and possible explanations, in: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2005.
[24] Lovász, L., Large Networks and Graph Limits (2012), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1292.05001
[25] Memišević, V.; Milenković, T.; Pržulj, N., An integrative approach to modeling biological networks, J. Integr. Bioinform., 7, 120 (2010)
[26] Scott, J. P., Social Network Analysis: A Handbook (2000), Sage Publications Ltd.: Sage Publications Ltd. London
[27] Small, L.; Mason, O., Information diffusion on the iterated local transitivity model of online social networks, Discrete Appl. Math., 161, 1338-1344 (2013) · Zbl 1285.91107
[28] West, D. B., Introduction to Graph Theory (2001), Prentice Hall
[29] Zachary, W. W., An information flow model for conflict and fission in small groups, J. Anthropol. Res., 33, 452-473 (1977)
[30] Zhang, Z.; Comellas, F.; Fertin, G.; Rong, L., Highdimensional apollonian networks, J. Phys. A: Math. Gen., 39, 1811 (2006) · Zbl 1086.68017
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.