Efficient network generation under general preferential attachment

详细信息    查看全文

• 作者：James Atwood ; Bruno Ribeiro ; Don Towsley
• 关键词：Preferential ; Attachment ; Network ; Science
• 刊名：Computational Social Networks
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：2
• 期：1
• 全文大小：1743KB
• 参考文献：1.Newman, MEJ: The structure and function of complex networks. SIAM Rev. 45(2), 167-56 (2003).CrossRef MATH MathSciNet
  2.Barabási, A-L, Albert, R, Jeong, H: Internet: diameter of the World-Wide Web. Nature. 401(6749), 130-31 (1999).CrossRef
  3.Barabási, A-L, Albert, R, Jeong, H: Scale-free characteristics of random networks: the topology of the world-wide web. Physica A: Stat. Mech. Appl. 281(1-), 69-7 (2000).CrossRef
  4.Broder, A, Kumar, R, Maghoul, F, Raghavan, P, Rajagopalan, S, Stata, R, Tomkins, A, Wiener, J: Graph structure in the web. Comput networks. 33(1), 309-20 (2000).CrossRef
  5.Chen, Q, Chang, H, Govindan, R, Jamin, S: The origin of power laws in Internet topologies revisited. In: INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, pp. 608-17. IEEE (2002).
  6.Faloutsos, M, Faloutsos, P, Faloutsos, C: On power-law relationships of the internet topology. ACM SIGCOMM Comput Commun Rev. 29(4), 251-62 (1999).CrossRef
  7.Vázquez, A, Pastor-Satorras, R, Vespignani, A: Large-scale topological and dynamical properties of the Internet. Phys. Rev. E. 65(6), 066130 (2002).CrossRef
  8.Aiello, W, Chung, F, Lü, L: A random graph model for massive graphs. In: the Thirty-second Annual ACM Symposium, pp. 171-80. ACM, New York (2000).
  9.Aiello, W, Chung, F, Lu, L: Random evolution in massive graphs. Found Comput Sci (2001).
  10.de Solla Price, DJ: Networks of scientific papers. Science. 169, 510-15 (1965).CrossRef
  11.Ribeiro, B, Gauvin, W, Liu, B, Towsley, D: On MySpace account spans and double Pareto-like distribution of friends. In: INFOCOM. NFOCOM IEEE Conference on Computer Communications Workshops, New York, USA (2010).
  12.Quicknet Implementation. https://?github.?com/?hackscience/?quicknet .
  13.Krapivsky, P, Redner, S: Organization of growing random networks. Phys. Rev. E. 63(6), 066123 (2001).CrossRef
  14.Tonelli, R, Concas, G, Locci, M: Three efficient algorithms for implementing the preferential attachment mechanism in Yule-Simon stochastic process. WSEAS Trans. Inf. Sci. App. 7(2), 176-85 (2010).
  15.Aragon, CR, Seidel, RG: Randomized search trees. In: Foundations of Computer Science, 1989, 30th Annual Symposium on, pp. 540-45. IEEE (1989).
  16.Price, D. d. S: A general theory of bibliometric and other cumulative advantage processes. J. Am. Soc. Inform. Sci. 27(5), 292-06 (1976).CrossRef
  17.Barabási, AL, Albert, R: Emergence of scaling in random networks. Science, 509-12 (1999).
  18.Krapivsky, P, Rodgers, G, Redner, S: Degree distributions of growing networks. Phys. Rev. Lett. 86(23), 5401-404 (2001).CrossRef
  19.Capocci, A, Servedio, V, Colaiori, F, Buriol, L. S, al, e: Preferential attachment in the growth of social networks: the Internet encyclopedia Wikipedia. Phys. Rev. E. 74(3), 036116 (2006).CrossRef
  20.Ren, W, Li, J: A fast algorithm for simulating scale-free networks. ICCTA, 264-68 (2009).
  21.Hruz, T, Geisseler, S, Sch?ngens, M: Parallelism in simulation and modeling of scale-free complex networks. Parallel Comput. 36(8), 469-85 (2010).CrossRef MATH MathSciNet
  22.D’Angelo, G, Ferretti, S: Simulation of scale-free networks. In: Proceedings of the 2nd International Conference on Simulation Tools and Techniques, p. 20. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering) (2009).
  23.Machta, B, Machta, J: Parallel dynamics and computational complexity of network growth models. Phys. Rev. E. 71(2), 026704 (2005).CrossRef
  
• 作者单位：James Atwood (1)
  Bruno Ribeiro (2)
  Don Towsley (1)
  
  1. School of Computer Science, University of Massachusetts Amherst, Amherst, 01003, MA, USA
  2. School of Computer Science, Carnegie Mellon University, Pittsburgh, 15213, PA, USA
  
• 刊物类别：Mathematical Models of Cognitive Processes and Neural Networks; Database Management; Media Sociology
• 刊物主题：Mathematical Models of Cognitive Processes and Neural Networks; Database Management; Media Sociology; Industrial Organization; Socio- and Econophysics, Population and Evolutionary Models; Industrial a
• 出版者：Springer International Publishing
• ISSN：2197-4314

文摘

Preferential attachment (PA) models of network structure are widely used due to their explanatory power and conceptual simplicity. PA models are able to account for the scale-free degree distributions observed in many real-world large networks by sequentially introducing nodes that attach preferentially to existing nodes with high degree. The ability to efficiently generate instances from PA models is a key asset in understanding both the models themselves and the real networks that they represent. Surprisingly, little attention has been paid to the problem of efficient instance generation. In this paper, we show that the complexity of generating network instances from a PA model depends on the preference function of the model, provides efficient data structures that work under any preference function, and presents empirical results from an implementation based on these data structures. We demonstrate that, by indexing growing networks with a simple augmented heap, we can implement a network generator which scales many orders of magnitude beyond existing capabilities (106 to 108 nodes). We show the utility of an efficient and general PA network generator by investigating the consequences of varying the preference functions of an existing model. We also provide ‘quicknet,-a freely available open-source implementation of the methods described in this work. Keywords Preferential Attachment Network Science