Abstract
We present a deterministic model for on-line social networks based on transitivity and local knowledge in social interactions. In the Iterated Local Transitivity (ILT) model, at each time-step and for every existing node x, a new node appears which joins to the closed neighbour set of x. The ILT model provably satisfies a number of both local and global properties that were observed in real-world on-line social and other complex networks, such as a densification power law, decreasing average distance, and higher clustering than in random graphs with the same average degree. Experimental studies of social networks demonstrate poor expansion properties as a consequence of the existence of communities with low number of inter-community links. A spectral gap for both the adjacency and normalized Laplacian matrices is proved for graphs arising from the ILT model, thereby simulating such bad expansion properties.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adamic, L.A., Buyukkokten, O., Adar, E.: A social network caught in the web. First Monday 8 (2003)
Ahn, Y., Han, S., Kwak, H., Moon, S., Jeong, H.: Analysis of topological characteristics of huge on-line social networking services. In: Proceedings of the 16th International Conference on World Wide Web (2007)
Bebek, G., Berenbrink, P., Cooper, C., Friedetzky, T., Nadeau, J., Sahinalp, S.C.: The degree distribution of the generalized duplication model. Theoretical Computer Science 369, 234–249 (2006)
Bhan, A., Galas, D.J., Dewey, T.G.: A duplication growth model of gene expression networks. Bioinformatics 18, 1486–1493 (2002)
Bonato, A.: A Course on the Web Graph. American Mathematical Society Graduate Studies Series in Mathematics, Providence, Rhode Island (2008)
Bonato, A., Janssen, J.: Infinite limits and adjacency properties of a generalized copying model. Internet Mathematics (accepted)
Caldarelli, G.: Scale-Free Networks. Oxford University Press, Oxford (2007)
Chung, F.: Spectral Graph Theory. American Mathematical Society, Providence, Rhode Island (1997)
Chung, F., Lu, L., Dewey, T., Galas, D.: Duplication models for biological networks. Journal of Computational Biology 10, 677–687 (2003)
Chung, F., Lu, L.: Complex graphs and networks. American Mathematical Society, Providence, Rhode Island (2006)
Chung, F., Lu, L., Vu, V.: The spectra of random graph with given expected degrees. Internet Mathematics 1, 257–275 (2004)
Crandall, D., Cosley, D., Huttenlocher, D., Kleinberg, J., Suri, S.: Feedback effects between similarity and social influence in on-line communities. In: Proceedings of the 14th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining (2008)
Durrett, R.: Random Graph Dynamics. Cambridge University Press, New York (2006)
Ebel, H., Davidsen, J., Bornholdt, S.: Dynamics of social networks. Complexity 8, 24–27 (2003)
Estrada, E.: Spectral scaling and good expansion properties in complex networks. Europhys. Lett. 73, 649–655 (2006)
Frank, O.: Transitivity in stochastic graphs and digraphs. Journal of Mathematical Sociology 7, 199–213 (1980)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 7821–7826 (2002)
Gkantsidis, C., Mihail, M., Saberi, A.: Throughput and congestion in power-law graphs. In: Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement Modeling of Computer Systems (2003)
Golder, S., Wilkinson, D., Huberman, B.: Rhythms of social interaction: messaging within a massive on-line network. In: 3rd International Conference on Communities and Technologies (2007)
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the web graph. In: Proceedings of the 41th IEEE Symposium on Foundations of Computer Science (2000)
Kumar, R., Novak, J., Tomkins, A.: Structure and evolution of on-line social networks. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2006)
Leskovec, J., Kleinberg, J., Faloutsos, C.: 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)
Leskovec, J., Chakrabarti, D., Kleinberg, J., Faloutsos, C.: Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. In: Jorge, A.M., Torgo, L., Brazdil, P.B., Camacho, R., Gama, J. (eds.) PKDD 2005. LNCS, vol. 3721, pp. 133–145. Springer, Heidelberg (2005)
Liben-Nowell, D., Novak, J., Kumar, R., Raghavan, P., Tomkins, A.: Geographic routing in social networks. Proceedings of the National Academy of Sciences 102, 11623–11628 (2005)
Milgram, S.: The small world problem. Psychology Today 2, 60–67 (1967)
Mislove, A., Marcon, M., Gummadi, K., Druschel, P., Bhattacharjee, B.: Measurement and analysis of on-line social networks. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement (2007)
Pastor-Satorras, R., Smith, E., Sole, R.V.: Evolving protein interaction networks through gene duplication. J. Theor. Biol. 222, 199–210 (2003)
Scott, J.P.: Social Network Analysis: A Handbook. Sage Publications Ltd., London (2000)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)
White, H., Harrison, S., Breiger, R.: Social structure from multiple networks, I: Blockmodels of roles and positions. American Journal of Sociology 81, 730–780 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bonato, A., Hadi, N., Horn, P., Prałat, P., Wang, C. (2009). A Dynamic Model for On-Line Social Networks. In: Avrachenkov, K., Donato, D., Litvak, N. (eds) Algorithms and Models for the Web-Graph. WAW 2009. Lecture Notes in Computer Science, vol 5427. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-95995-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-95995-3_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-95994-6
Online ISBN: 978-3-540-95995-3
eBook Packages: Computer ScienceComputer Science (R0)