Local Clustering Coefficient in Generalized Preferential Attachment Models

详细信息    查看全文

• 关键词：Networks ; Random graph models ; Preferential attachment ; Clustering coefficient
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9479
• 期：1
• 页码：15-28
• 全文大小：261 KB
• 参考文献：1.Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002)CrossRef MATH
  2.Bansal, S., Khandelwal, S., Meyers, L.A.: Exploring biological network structure with clustered random networks. BMC Bioinf. 10, 405 (2009)CrossRef
  3.Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Sci. 286(5439), 509–512 (1999)CrossRef
  4.Barabási, A.-L., Albert, R., Jeong, H.: Mean-field theory for scale-free random networks. Phys. A 272(1–2), 173–187 (1999)CrossRef
  5.Albert, R., Jeong, H., Barabási, A.-L.: Internet: diameter of the world-wide web. Nat. 401, 130–131 (1999)CrossRef
  6.Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.-U.: Complex networks: structure and dynamics. Phys. Rep. 424(45), 175–308 (2006)CrossRef MathSciNet
  7.Bollobás, B., Riordan, O.M.: Mathematical results on scale-free random graphs. In: Handbook of Graphs and Networks: From the Genome to the Internet (2003)
  8.Bollobás, B., Riordan, O.M., Spencer, J., Tusnády, G.: The degree sequence of a scale-free random graph process. Random Struct. Algorithms 18(3), 279–290 (2001)CrossRef MATH
  9.Borgs, C., Brautbar, M., Chayes, J., Khanna, S., Lucier, B.: The power of local information in social networks. Preprint (2012)
  10.Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.: Graph structure in the web. Comput. Netw. 33(16), 309–320 (2000)CrossRef
  11.Buckley, P.G., Osthus, D.: Popularity based random graph models leading to a scale-free degree sequence. Discrete Math. 282, 53–63 (2004)CrossRef MathSciNet MATH
  12.Catanzaro, M., Caldarelli, G., Pietronero, L.: Assortative model for social networks. Phys. Rev. E 70, 037101 (2004)CrossRef
  13.Leskovec, J.: Dynamics of large networks. ProQuest (2008)
  14.Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: Proceedings of SIGCOMM (1999)
  15.Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proc. Nat. Acad. Sci. 99(12), 7821–7826 (2002)CrossRef MathSciNet MATH
  16.Holme, P., Kim, B.J.: Growing scale-free networks with tunable clustering. Phys. Rev. E 65(2), 026107 (2002)CrossRef
  17.Newman, M.E.J.: Pareto distributions and Zipf’s law. Contemp. Phys. 46(5), 323–351 (2005)CrossRef
  18.Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)CrossRef MathSciNet MATH
  19. Ostroumova, L., Ryabchenko, A., Samosvat, E.: Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient. In: Bonato, A., Mitzenmacher, M., Prałat, P. (eds.) WAW 2013. LNCS, vol. 8305, pp. 185–202. Springer, Heidelberg (2013) CrossRef
  20.Ravasz, E., Barabási, A.-L.: Hierarchical organization in complex networks. Phys. Rev. E 67(2), 26112 (2003)CrossRef
  21.Serrano, M.A., Boguñá, M.: Clustering in complex networks. I. General formalism. Phys. Rev. E 74, 056114 (2006)CrossRef MathSciNet
  22.Serrano, M.A., Boguñá, M.: Clustering in complex networks. II. Percolation properties. Phys. Rev. E 74, 056115 (2006)CrossRef MathSciNet
  23.Vázquez, A., Pastor-Satorras, R., Vespignani, A.: Large-scale topological and dynamical properties of the internet. Phys. Rev. E 65, 066130 (2002)CrossRef
  24.Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)CrossRef
  25.Zhou, T., Yan, G., Wang, B.-H.: Maximal planar networks with large clustering coefficient and power-law degree distribution. Phys. Rev. E 71(4), 046141 (2005)CrossRef
  
• 作者单位：Alexander Krot (16)
  Liudmila Ostroumova Prokhorenkova (17) (18)
  
  16. Moscow Institute of Physics and Technology, Moscow, Russia
  17. Yandex, Moscow, Russia
  18. Moscow State University, Moscow, Russia
  
• 丛书名：Algorithms and Models for the Web Graph
• ISBN：978-3-319-26784-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In this paper, we analyze the local clustering coefficient of preferential attachment models. A general approach to preferential attachment was introduced in [19], where a wide class of models (PA-class) was defined in terms of constraints that are sufficient for the study of the degree distribution and the clustering coefficient. It was previously shown that the degree distribution in all models of the PA-class follows a power law. Also, the global clustering coefficient was analyzed and a lower bound for the average local clustering coefficient was obtained. We expand the results of [19] by analyzing the local clustering coefficient for the PA-class of models. Namely, we analyze the behavior of C(d) which is the average local clustering for the vertices of degree d.