×

An extended scale-free network evolution model based on star-like coupling motif embedding. (English) Zbl 07639839

Summary: As the only brand-new basic model that can study networks with scale change characteristics at present, the Barabási-Albert scale-free network evolution model (BA model) can well describe the entry phenomenon of a single subject. However, for many evolutionary networks in the real world, the entry of the subject is more realized in a team way. Therefore, the BA model’s assumption concerning one new node entering alone per unit of time can only be used as a particular case of a team entry. This deficiency makes it difficult for the BA model to analyze how the team entry mechanism affects the network’s performance and thus leads to the BA model’s certain limitations. To make up for this shortcoming, with the help of the motif’s concept, an extended BA model with a star-like coupling motif embedding (SCME-BA model) is constructed, where the motif’s scale obeys an arbitrary discrete probability distribution. The exact explicit expression of the network’s steady-state degree distribution of the SCME-BA model is first obtained by the Markov chain analytic method, and its numerical characteristics are explored. Then, the correctness of the analytic expression is verified by numerical simulation. The study results show that, compared with the BA model, the left tail of the SCME-BA model’s steady-state degree distribution can reflect the distribution law of the embedded motif scale well while the right one still has power-law attenuation characteristics whose power-law exponent is adjustable. Specifically, the power-law exponent is positively and negatively correlated with the expectation of the motif’s scale and the initial number of existing nodes connected to the new embedded motif, respectively. Moreover, the SCME-BA model can degenerate into the BA model when the motif’s scale is subject to the one-point distribution with parameter 1. Finally, the rationality of the SCME-BA model is verified through a case study.

MSC:

82-XX Statistical mechanics, structure of matter
Full Text: DOI

References:

[1] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223
[2] Chen, G.; Wang, X.; Li, X., Introduction to Complex Networks: Models, Structures and Dynamics (2012), Higher Education Press
[3] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’networks, Nature, 393, 6684, 440-442 (1998) · Zbl 1368.05139
[4] Milo, R.; Shen-Orr, S.; Itzkovitz, S.; Kashtan, N.; Chklovskii, D.; Alon, U., Network motifs: simple building blocks of complex networks, Science, 298, 5594, 824-827 (2002)
[5] Shen-Orr, S. S.; Milo, R.; Mangan, S.; Alon, U., Network motifs in the transcriptional regulation network of escherichia coli, Nat. Genet., 31, 1, 64-68 (2002)
[6] Takemoto, K.; Oosawa, C., Evolving networks by merging cliques, Phys. Rev. E, 72, 4, 046116 (2005)
[7] Takemoto, K.; Oosawa, C., Modeling for evolving biological networks with scale-free connectivity, hierarchical modularity, and disassortativity, Math. Biosci., 208, 2, 454-468 (2007) · Zbl 1119.92044
[8] Colizza, V.; Flammini, A.; Maritan, A.; Vespignani, A., Characterization and modeling of protein-protein interaction networks, Phys. A Stat. Mech. Appl., 352, 1, 1-27 (2005)
[9] Goh, K.-I.; Kahng, B.; Kim, D., Graph theoretic analysis of protein interaction networks of Eukaryotes, Phys. A Stat. Mech. Appl., 357, 3-4, 501-512 (2005)
[10] Organisation for Economic Co-operation and Development, K.-I., The Global Competition for Talent: Mobility of the Highly Skilled (2008), OECD Publishing Paris
[11] Dazhong Daily, K.-I., Introducing a talent brings a team; set up an enterprise to drive an industry! (2021), [EB/OL]. https://ishare.ifeng.com/c/s/v002AlotG9OandVxPBVJ5tHT7IjUEYN1bR-F7ounkK-njac__. (Accessed 14 June 2021)
[12] Yu, X.; Li, Z.; Zhang, D.; Liang, F.; Wang, Y.; Wu, X., The topology of an accelerated growth network, J. Phys. A: Math. Gen., 39, 46, 14343-14351 (2006) · Zbl 1148.82311
[13] Guo, J.; Wang, L., Scale-free networks with the power-law exponent between 1 and 3, Acta Phys. Sin., 56, 10, 5635-5639 (2007) · Zbl 1150.90338
[14] Feng, M.; Qu, H.; Yi, Z.; Xie, X.; Kurths, J., Evolving scale-free networks by Poisson process: Modeling and degree distribution, IEEE Trans. Cybern., 46, 5, 1144-1155 (2016)
[15] Wang, J.; Rong, L.; Yu, K., Evolving model of scale-free networks based on batch growth of nodes, J. Syst. Eng., 25, 5, 579-584 (2010) · Zbl 1240.90077
[16] Wang, D.; Jian, L.; Duan, L.; Xue, C., An extended scale-free network evolution model based on global coupling motif embedding, J. Stat. Mech. Theory Exp., 2021, 2, Article 023401 pp. (2021) · Zbl 1541.90106
[17] Babu, M. M.; Luscombe, N. M.; Aravind, L.; Gerstein, M.; Teichmann, S. A., Structure and evolution of transcriptional regulatory networks, Curr. Opin. Struct. Biol., 14, 3, 283-291 (2004)
[18] Vermeij, A., Apple after Jony Ive: Aligning hardware and software design in an innovation network (2019), [EB/OL]. https://www.kenedict.com/apple-after-jony-ive-aligning-hardware-and-software-design-in-an-innovation-network/. (Accessed 25 September 2019)
[19] Vermeij, A., A peek inside the dutch government’s supplier networks: Open data visualized (2015), [EB/OL] https://www.kenedict.com/a-peek-inside-the-dutch-governments-supplier-networks-open-data-visualized/. (Accessed 14 December 2015)
[20] Wuchty, S.; Oltvai, Z. N.; Barabási, A.-L., Evolutionary conservation of motif constituents in the yeast protein interaction network, Nat. Genet., 35, 2, 176-179 (2003)
[21] Visible Network Labs, S., Organizational network structures: 6 common examples (2021), [EB/OL] https://visiblenetworklabs.com/2021/03/09/network-organizational-structures/. (Accessed 9 March 2021)
[22] Barabási, A.-L., Network Science (2016), Cambridge University Press · Zbl 1353.94001
[23] Barabási, A.-L.; Albert, R.; Jeong, H., Mean-field theory for scale-free random networks, Physica A, 272, 1-2, 173-187 (1999)
[24] Krapivsky, P. L.; Redner, S.; Leyvraz, F., Connectivity of growing random networks, Phys. Rev. Lett., 85, 21, 4629-4632 (2000)
[25] Dorogovtsev, S. N.; Mendes, J. F.F.; Samukhin, A. N., Structure of growing networks with preferential linking, Phys. Rev. Lett., 85, 21, 4633-4636 (2000)
[26] Bollobás, B.; Riordan, O. M., Mathematical results on scale-free random graphs, (Handbook of Graphs and Networks: From the Genome to the Internet (2003), Wiley-Vch Weinheim), 1-34 · Zbl 1044.90002
[27] Chen, Q.; Shi, D., Markov chains theory for scale-free networks, Physica A, 360, 1, 121-133 (2006)
[28] Hou, Z.; Kong, X.; Shi, D.; Chen, G., Degree-distribution stability of scale-free networks (2008), arXiv preprint arXiv:0805.1434
[29] Zhang, X.; He, Z.; He, Z.; Rayman-Bacchus, L., SPR-based Markov chain method for degree distributions of evolving networks, Physica A, 391, 11, 3350-3358 (2012)
[30] Zhang, X.; He, Z.; Rayman-Bacchus, L., Random birth-and-death networks, J. Stat. Phys., 162, 4, 842-854 (2016) · Zbl 1337.60219
[31] Zhang, X.; Yang, H., Degree distribution of random birth-and-death network with network size decline, Chin. Phys. B, 25, 6, Article 060202 pp. (2016)
[32] Long, Y.; Zhang, X.-J.; Wang, K., Theoretical solutions for degree distribution of decreasing random birth-and-death networks, Modern Phys. Lett. B, 31, 14, Article 1750161 pp. (2017)
[33] Hou, Z.; Kong, X.; Shi, D.; Chen, G.; Zhao, Q., Degree-distribution stability of growing networks, (International Conference on Complex Sciences (2009), Springer), 1827-1837
[34] Kong, X. X.; Hou, Z. T.; Shi, D. H.; Chen, Q. R.; Zhao, Q. G., Markov chain-based degree distributions of evolving networks, Acta Math. Sin. (Engl. Ser.), 28, 10, 1981-1994 (2012) · Zbl 1255.05051
[35] ErdHos, P.; Rényi, A., On random graphs, Publ. Math., 6, 290-297 (1959) · Zbl 0092.15705
[36] Stolz, O., Vorlesungen Über Allgemeine Arithmetik: Nach Den Neueren Ansichten, Vol. 1 (1885), BG Teubner · JFM 17.0116.01
[37] Milne-Thomson, L. M., The Calculus of Finite Differences (1951), Macmillan · Zbl 0008.01801
[38] Bollobás, B.; Riordan, O.; Spencer, J.; Tusnády, G., The degree sequence of a scale-free random graph process, Random Struct. Algorithms, 18, 3, 279-290 (2001) · Zbl 0985.05047
[39] Newman, M. E.; Watts, D. J., Renormalization group analysis of the small-world network model, Phys. Lett. A, 263, 4-6, 341-346 (1999) · Zbl 0940.82029
[40] Shi, D.; Liu, L.; Zhu, S.; Zhou, H., Degree distributions of evolving networks, Europhys. Lett., 76, 4, 731 (2006)
[41] Johnson, N. L.; Kotz, S.; Kemp, A. W., Univariate Discrete Distributions (2005), John Wiley & Sons · Zbl 1092.62010
[42] Palla, G.; Farkas, I. J.; Pollner, P.; Derényi, I.; Vicsek, T., Fundamental statistical features and self-similar properties of tagged networks, New J. Phys., 10, 12, Article 123026 pp. (2008)
[43] R. Rossi, N. Ahmed, The network data repository with interactive graph analytics and visualization, in: Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015, pp. 4292-4293.
[44] Rossi, R. A.; Ahmed, N. K., An interactive data repository with visual analytics, ACM SIGKDD Explor. Newsl., 17, 2, 37-41 (2016)
[45] Rossi, R. A.; Ahmed, N. K., The network data repository with interactive graph analytics and visualization, (Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)), 4292-4293, http://networkrepository.com
[46] Drożdż, S.; Kulig, A.; Kwapień, J.; Niewiarowski, A.; Stanuszek, M., Hierarchical organization of H. Eugene Stanley scientific collaboration community in weighted network representation, J. Informetr., 11, 4, 1114-1127 (2017)
[47] Dorogovtsev, S. N.; Mendes, J. F., Evolution of networks, Adv. Phys., 51, 4, 1079-1187 (2002)
[48] Holme, P.; Kim, B. J., Growing scale-free networks with tunable clustering, Phys. Rev. E, 65, 2, 026107 (2002)
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.