Jérôme Kunegis
Marcel Blattner
ABSTRACT
We perform an empirical study of the preferential attachment phenomenon in temporal networks and show that on the Web, networks follow a nonlinear preferential attachment model in which the exponent depends on the type of network considered. The classical preferential attachment model for networks by Barabási and Albert (1999) assumes a linear relationship between the number of neighbors of a node in a network and the probability of attachment. Although this assumption is widely made in Web Science and related fields, the underlying linearity is rarely measured. To fill this gap, this paper performs an empirical longitudinal (time-based) study on forty-seven diverse Web network datasets from seven network categories and including directed, undirected and bipartite networks. We show that contrary to the usual assumption, preferential attachment is nonlinear in the networks under consideration. Furthermore, we observe that the deviation from linearity is dependent on the type of network, giving sublinear attachment in certain types of networks, and superlinear attachment in others. Thus, we introduce the preferential attachment exponent β as a novel numerical network measure that can be used to discriminate different types of networks. We propose explanations for the behavior of that network measure, based on the mechanisms that underly the growth of the network in question.
- Aiello, L. M., Barrat, A., Cattuto, C., Ruffo, G., and Schifanella, R. Link creation and profile alignment in the aNobii social network. In Int. Conf. on Social Computing (2010), 249--256. Google Scholar
Digital Library
- Albert, R., and Barabási, A.-L. Statistical mechanics of complex networks. Reviews of Modern Physics 74, 1 (2002), 47--97.Google ScholarDigital Library
- Barabási, A.-L., and Albert, R. Emergence of scaling in random networks. Science 286, 5439 (1999), 509--512.Google ScholarCross Ref
- Barabási, A.-L., Jeong, H., Neda, Z., Ravasz, E., and Schubert, A. Evolution of the social network of scientific collaborations. Physica A 311, 3--4 (2002), 590--614.Google ScholarCross Ref
- Bennett, J., and Lanning, S. The Netflix Prize. In Proc. KDD Cup (2007), 3--6.Google Scholar
- Benz, D., Hotho, A., Jäschke, R., Krause, B., Mitzlaff, F., Schmitz, C., and Stumme, G. The social bookmark and publication management system BibSonomy. The VLDB J. 19, 6 (dec 2010), 849--875. Google ScholarDigital Library
- Bollobás, B. Modern Graph Theory. Springer, 1998.Google ScholarCross Ref
- Brandes, U., and Lerner, J. Structural similarity: Spectral methods for relaxed blockmodeling. J. Classification 27, 3 (2010), 279--306. Google ScholarDigital Library
- Capocci, A., Servedio, V. D. P., Colaiori, F., Buriol, L. S., Donato, D., Leonardi, S., and Caldarelli, G. Preferential attachment in the growth of social networks: The Internet encyclopedia Wikipedia. Phys. Rev. E 74, 3 (2006), 036116.Google ScholarCross Ref
- Celma, Ò. Music Recommendation and Discovery in the Long Tail. Springer, 2010. Google ScholarDigital Library
- Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Gass, R., and Scott, J. Impact of human mobility on opportunistic forwarding algorithms. IEEE Trans. on Mobile Computing 6, 6 (2007), 606--620. Google ScholarDigital Library
- Champernowne, D. A model of income distribution. Economic Journal 63 (1953), 318--351.Google ScholarCross Ref
- Choudhury, M. D., Lin, Y.-R., Sundaram, H., Candan, K. S., Xie, L., and Kelliher, A. How does the data sampling strategy impact the discovery of information diffusion in social media? In Proc. Int. Conf. on Weblogs and Social Media (2010), 34--41.Google Scholar
- Choudhury, M. D., Sundaram, H., John, A., and Seligmann, D. D. Social synchrony: Predicting mimicry of user actions in online social media. In Proc. Int. Conf. on Computational Science and Engineering (2009), 151--158. Google ScholarDigital Library
- Clauset, A., Shalizi, C. R., and Newman, M. E. J. Power-law distributions in empirical data. SIAM Rev. 51, 4 (2009), 661--703. Google ScholarDigital Library
- Dahlander, L., Frederiksen, L., and Rullani, F. Online communities and open innovation: Governance and symbolic value creation. Industry and Innovation 15, 2 (2008), 115--123.Google ScholarCross Ref
- Dereich, S., and Mörters, P. Random networks with sublinear preferential attachment: Degree evolutions. Electrical J. of Probability 14 (2009), 1222--1267.Google ScholarCross Ref
- Dholakiaa, U. M., Bagozzia, R. P., and Pearo, L. K. A social influence model of consumer participation in network- and small-group-based virtual communities. Int. J. of Research in Marketing 21, 3 (2004), 241--263.Google ScholarCross Ref
- Dorogovtsev, S. N., and Mendes, J. F. F. Evolution of networks. Adv. Phys. 51 (2002), 1079--1187.Google ScholarCross Ref
- Dror, G., Koenigstein, N., Koren, Y., and Weimer, M. The Yahoo! Music dataset and KDD-Cup'11. In JMLR Workshop and Conf. Proc., vol. 18 (2012), 3--18.Google Scholar
- Eagle, N., and Pentland, A. S. Reality Mining: Sensing complex social systems. Personal Ubiquitous Computing 10, 4 (2006), 255--268.Google ScholarDigital Library
- Emamy, K., and Cameron, R. CiteULike: A researcher's social bookmarking service. Ariadne, 51 (2007).Google Scholar
- Erdős, P., and Rényi, A. On random graphs I. Publ. Math. Debrecen 6 (1959), 290--297.Google ScholarCross Ref
- Faraj, S., and Johnson, S. L. Network exchange patterns in online communities. Organization Science 22, 6 (2010), 1464--1480. Google ScholarDigital Library
- Gabel, A., and Redner, S. Sublinear but never superlinear preferential attachment by local network growth. arXiv:1212.0518.Google Scholar
- Gay, B., and Dousset, B. Innovation and network structural dynamics: Study of the alliance network of a major sector of the biotechnology industry. Research Policy 34, 10 (2005), 1457--1475.Google ScholarCross Ref
- Gibrat, R. Les Inegalités économiques: Applications aux inégalités des richesses, à la concentration des entreprises, aux populations des villes, aux statistiques des familles, etc., d'une loi nouvelle: la loi de l'effect proportionnel. Sirey, 1931.Google Scholar
- GroupLens Research. MovieLens data sets. http://www.grouplens.org/node/73, October 2006.Google Scholar
- Gulati, R., Puranam, P., and Tushman, M. Meta-organization design: Rethinking design in interorganizational and community contexts. Strategic Management J. 33 (2012), 571--586.Google ScholarCross Ref
- Gómez, V., Kaltenbrunner, A., and López, V. Statistical analysis of the social network and discussion threads in Slashdot. In Proc. Int. World Wide Web Conf. (2008), 645--654. Google ScholarDigital Library
- Hanaki, N., Nakajima, R., and Ogura, Y. The dynamics of R&D network in the IT industry. Research Policy 39, 3 (2010), 386--399.Google ScholarCross Ref
- Jeong, H., Néda, Z., and Barabási, A. L. Measuring preferential attachment for evolving networks. Europhysics Lett. 61, 4 (2001), 567--572.Google Scholar
- Kapteyn, J. C., and van Uven, M. J. Skew Frequency Curves in Biology and Statistics. Hoitsema Brothers, Groningen, 1916.Google Scholar
- Klimt, B., and Yang, Y. The Enron corpus: A new dataset for email classification research. In Proc. European Conf. on Machine Learning (2004), 217--226.Google ScholarDigital Library
- Krapivsky, P. L., and Krioukov, D. Scale-free networks as preasymptotic regimes of superlinear preferential attachment. Phys. Rev. E 78 (2008), 026114.Google ScholarCross Ref
- Krapivsky, P. L., and Redner, S. Organization of growing random networks. Phys. Rev. E 63 (2001), 066123.Google ScholarCross Ref
- Lemarchand, G. A. The long-term dynamics of co-authorship scientific networks: Iberoamerican countries (1973--2010). Research Policy 41, 2 (2012), 291--305.Google ScholarCross Ref
- Ley, M. The DBLP computer science bibliography: Evolution, research issues, perspectives. In Proc. Int. Symp. on String Processing and Information Retrieval (2002), 1--10. Google ScholarDigital Library
- Liben-Nowell, D., and Kleinberg, J. The link prediction problem for social networks. In Proc. Int. Conf. on Information and Knowledge Management (2003), 556--559. Google ScholarDigital Library
- Lim, E.-P., Nguyen, V.-A., Jindal, N., Liu, B., and Lauw, H. W. Detecting product review spammers using rating behaviors. In Proc. Int. Conf. on Information and Knowledge Management (2010), 939--948. Google ScholarDigital Library
- Lotka, A. J. The frequency distribution of scientific productivity. J. of the Washington Academy of Sciences 16, 12 (1926), 317--324.Google Scholar
- Massa, P., and Avesani, P. Controversial users demand local trust metrics: an experimental study on epinions.com community. In Proc. American Association for Artificial Intelligence Conf. (2005), 121--126. Google ScholarDigital Library
- Mislove, A. Online Social Networks: Measurement, Analysis, and Applications to Distributed Information Systems. PhD thesis, Rice University, 2009. Google ScholarDigital Library
- Mislove, A., Koppula, H. S., Gummadi, K. P., Druschel, P., and Bhattacharjee, B. Growth of the Flickr social network. In Proc. Workshop on Online Social Networks (2008), 25--30. Google ScholarDigital Library
- Moser, C., Groenewegen, P., and Huysman, M. Social norms as governance mechanisms in online professional communities. In Proc. Academy of Management Meeting (2011).Google Scholar
- Newman, M. E. J. Clustering and preferential attachment in growing networks. Phys. Rev. E 67, 5 (2002).Google Scholar
- Newman, M. E. J. The structure and function of complex networks. SIAM Review 45, 2 (2003), 167--256.Google ScholarDigital Library
- Newman, M. E. J. Power laws, Pareto distributions and Zipf's law. Contemporary Phys. 46, 5 (2006), 323--351.Google Scholar
- Oliveira, R., and Spencer, J. Connectivity transitions in networks with super-linear preferential attachment. Internet Math 2 (2005), 121--163.Google ScholarCross Ref
- O'mahony, S., and Ferraro, F. The emergence of governance in an open source community. Academy of Management J. 50, 5 (2007), 1079--1106.Google ScholarCross Ref
- Opsahl, T., and Panzarasa, P. Clustering in weighted networks. Social Networks 31, 2 (2009), 155--163.Google ScholarCross Ref
- Opsahl, T., and Panzarasa, P. Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social Networks 34 (2011).Google Scholar
- Pfeil, U., Zaphiris, P., and Ang, C. S. Cultural differences in collaborative authoring of Wikipedia. J. of Computer-mediated Communication 12, 1 (2006), 88--113.Google ScholarCross Ref
- Rocha, L. E. C., Liljeros, F., and Holme, P. Information dynamics shape the sexual networks of Internet-mediated prostitution. Proc. of the National Academy of Sciences 107, 13 (2010), 5706--5711.Google ScholarCross Ref
- Rudas, A., Tóth, B., and Valkó, B. Random trees and general branching processes. Random Struct. Algorithms 31, 2 (2007), 186--202. Google ScholarDigital Library
- Said, A., De Luca, E. W., and Albayrak, S. How social relationships affect user similarities. In Proc. IUI Workshop on Social Recommender Systems (2010).Google Scholar
- Simon, H. A. On a class of skew distribution functions. Biometrika 42 (1955), 425--440.Google ScholarCross Ref
- Stack Exchange Inc. Stack Exchange Data Explorer. http://data.stackexchange.com/, 2011.Google Scholar
- Tremayne, M., Zheng, N., Lee, J. K., and Jeong, J. Issue publics on the Web: Applying network theory to the war blogosphere. J. of Computer-mediated Communication 12, 1 (2006), 290--310.Google ScholarCross Ref
- Viswanath, B., Mislove, A., Cha, M., and Gummadi, K. P. On the evolution of user interaction in Facebook. In Proc. Workshop on Online Social Networks (2009), 37--42. Google ScholarDigital Library
- Wagner, C. S., and Leydesdorff, L. Network structure, self-organization, and the growth of international collaboration in science. Research Policy 34, 10 (2005), 1608--1618.Google ScholarCross Ref
- Wang, E. S. T., and Chen, L. S. L. Forming relationship commitments to online communities: The role of social motivations. Computers in Human Behavior 28, 2 (2012), 570--575. Google ScholarDigital Library
- Watts, D. J. The 'new' science of networks. Annual Review of Sociology 30 (2004), 243--270.Google ScholarCross Ref
- Wikimedia Foundation. Wikimedia downloads. http://dumps.wikimedia.org/, January 2010.Google Scholar
- Yule, G. U. A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, F. R. S. Philos. Trans. of the Royal Society of London, Ser. B 213 (1925), 21--87.Google ScholarCross Ref
- Zhou, T. Understanding online community user participation: a social influence perspective. Internet Research 21, 1 (2011), 67--81.Google ScholarCross Ref
- Zipf, G. K. The Psychobiology of Language. Houghton Mifflin, 1935.Google Scholar
Index Terms
- Preferential attachment in online networks: measurement and explanations
Recommendations
Parallelizing Preferential Attachment Models for Generating Large-Scale Social Networks that Cannot Fit into Memory
SOCIALCOM-PASSAT '12: Proceedings of the 2012 ASE/IEEE International Conference on Social Computing and 2012 ASE/IEEE International Conference on Privacy, Security, Risk and TrustSocial network generation is an important problem in social network analysis. The goal is to produce artificial networks that preserve some real world properties of social networks. As one of most popular social network generation algorithms, the ...
Distributed-memory parallel algorithms for generating massive scale-free networks using preferential attachment model
SC '13: Proceedings of the International Conference on High Performance Computing, Networking, Storage and AnalysisRecently, there has been substantial interest in the study of various random networks as mathematical models of complex systems. As these complex systems grow larger, the ability to generate progressively large random networks becomes all the more ...
On the relationship between trading network and WWW network: a preferential attachment perspective
This paper describes the relationship between trading network and WWW network from preferential attachment mechanism perspective. This mechanism is known to be the underlying principle in the network evolution and has been incorporated to formulate two ...
Comments