拓扑结构对增长的复杂网络演化的影响研究
|
摘要
从神经生物学到统计物理学,从工程技术到经济社会等各种领域,关于复杂网络的研究最基本的议题都离不开结构。网络的拓扑结构是构建复杂系统模型、研究系统性质、功能和行为的基础,研究拓扑结构是如何影响或者在多大程度上影响网络的演化,将有助于更好地认识存在于真实世界各种类型的复杂网络,对于优化设计复杂工程系统也有重要的启示意义。
本论文的研究重点关注在网络增长和外部目标功能的双重作用下,拓扑结构对复杂网络的演化过程产生的影响。在经典的布尔网络模型上运用了多种节点增长规则驱动不同拓扑结构的网络向着预先设定的目标函数演化,并利用遗传算法进行了大量仿真模拟以考查不同类型的网络表现出来的演化性能。结果显示:(1)在动态增长的网络向着预先定义的目标函数演化的过程中,无标度网络表现出略胜于随机网络的演化能力,一方面是在网络演化前期能够更加快速地向目标函数收敛,另外一方面是在陷入局部极值时能够更加快速地逃离。但是由于引入了节点增长,两种类型的网络在演化中后期都表现出明显的演化性能下降,最终形成了几乎相同的弱演化能力;(2)无论是无标度网络还是随机网络,演化性能都随着平均连边数的增加而出现了提高的趋势,但是提升的空间存在明显的极限;(3)在网络增长的过程中,新增节点的时间间隔对网络演化性能也有比较明显的影响,节点增加越频繁,网络表现出相对越快的收敛速度;(4)无标度网络和随机网络同处一个群体中混合竞争演化时,并没有表现出相对于彼此的演化性能优势;( 5 )Disassortative-Mixing类型的无标度网络表现出比Assortative-Mixing类型的无标度网络更快速更稳健的演化能力。
总之,本论文的研究揭示了拓扑结构对于动态增长的复杂网络向目标功能演化的影响,对更加全面地理解复杂网络的结构、功能以及演化之间的关系起到了积极的推动作用。
The structure is always inevitably one of the most basic issues in the study of complex networks among a large variety of research areas, whether from neurobiology to statistical physics, or from engineering to economics and sociology. Topology is the foundation of either constructing models for complex systems or investigating the characteristics, functions and behaviour of complex systems. Studies on how or to what extent the topology will impose an influence on network evolution will no doubt not only contribute to a better understanding of a variety of categories of complex networks existing in the real world, but also will it definitely bring important inspiration to the optimization and design of artificial complex engineering systems.
In this paper, we focused on the impact of topology during the evolution of complex networks, under the influence of both network growth and target function. We drive networks of distinct topologies evolving toward predetermined target function on the classical Boolean Network model by applying several different kinds of growing rules on the network evolution. We employed genetic algorithms to perform extensive simulations, and examined in detail the evolutionary performance of networks with different types of topologies. The results demonstrated that: (1) When evolving to the pre-established target function with a concurrent dynamic network growth, the scale-free network displays a slightly better performance than its random counterpart in two ways: one is that in the early stage of network evolution the scale-free network can converge to the target function more quickly, and the other is that the scale-free network is also able to escape more fast when caught in local extremum. But meanwhile, due to the influence of node growth, both scale-free and random network have shown obvious degradation on their performance after the mid-term of the evolution and finally deteriorate to almost the same very weak evolutionary capability. (2) The evolutionary performance tend to be raised when the average connectivity increased both for scale-free network and random network, but there is an obvious bottleneck for far more promotion.(3) During the network growth, the interval that a new node is added has obvious effects on the evolutionary performance, that is, the more frequently the node increases, the relatively faster the network evolves. (4) When scale-free network compete with random network in the same population, they do not show evolutionary advantage over each other. (5) Scale-free network with disassortative mixing feature exhibits a more faster and more robust evolutionary performance than the assortative mixing one.
In short, this paper reveals the impact of the topological structure on the dynamic growing complex network when evolving to pre-defined target function. It benefits us to develop a more comprehensive understanding of the relationship among structure, function and evolution of the complex networks .
本论文的研究重点关注在网络增长和外部目标功能的双重作用下,拓扑结构对复杂网络的演化过程产生的影响。在经典的布尔网络模型上运用了多种节点增长规则驱动不同拓扑结构的网络向着预先设定的目标函数演化,并利用遗传算法进行了大量仿真模拟以考查不同类型的网络表现出来的演化性能。结果显示:(1)在动态增长的网络向着预先定义的目标函数演化的过程中,无标度网络表现出略胜于随机网络的演化能力,一方面是在网络演化前期能够更加快速地向目标函数收敛,另外一方面是在陷入局部极值时能够更加快速地逃离。但是由于引入了节点增长,两种类型的网络在演化中后期都表现出明显的演化性能下降,最终形成了几乎相同的弱演化能力;(2)无论是无标度网络还是随机网络,演化性能都随着平均连边数的增加而出现了提高的趋势,但是提升的空间存在明显的极限;(3)在网络增长的过程中,新增节点的时间间隔对网络演化性能也有比较明显的影响,节点增加越频繁,网络表现出相对越快的收敛速度;(4)无标度网络和随机网络同处一个群体中混合竞争演化时,并没有表现出相对于彼此的演化性能优势;( 5 )Disassortative-Mixing类型的无标度网络表现出比Assortative-Mixing类型的无标度网络更快速更稳健的演化能力。
总之,本论文的研究揭示了拓扑结构对于动态增长的复杂网络向目标功能演化的影响,对更加全面地理解复杂网络的结构、功能以及演化之间的关系起到了积极的推动作用。
The structure is always inevitably one of the most basic issues in the study of complex networks among a large variety of research areas, whether from neurobiology to statistical physics, or from engineering to economics and sociology. Topology is the foundation of either constructing models for complex systems or investigating the characteristics, functions and behaviour of complex systems. Studies on how or to what extent the topology will impose an influence on network evolution will no doubt not only contribute to a better understanding of a variety of categories of complex networks existing in the real world, but also will it definitely bring important inspiration to the optimization and design of artificial complex engineering systems.
In this paper, we focused on the impact of topology during the evolution of complex networks, under the influence of both network growth and target function. We drive networks of distinct topologies evolving toward predetermined target function on the classical Boolean Network model by applying several different kinds of growing rules on the network evolution. We employed genetic algorithms to perform extensive simulations, and examined in detail the evolutionary performance of networks with different types of topologies. The results demonstrated that: (1) When evolving to the pre-established target function with a concurrent dynamic network growth, the scale-free network displays a slightly better performance than its random counterpart in two ways: one is that in the early stage of network evolution the scale-free network can converge to the target function more quickly, and the other is that the scale-free network is also able to escape more fast when caught in local extremum. But meanwhile, due to the influence of node growth, both scale-free and random network have shown obvious degradation on their performance after the mid-term of the evolution and finally deteriorate to almost the same very weak evolutionary capability. (2) The evolutionary performance tend to be raised when the average connectivity increased both for scale-free network and random network, but there is an obvious bottleneck for far more promotion.(3) During the network growth, the interval that a new node is added has obvious effects on the evolutionary performance, that is, the more frequently the node increases, the relatively faster the network evolves. (4) When scale-free network compete with random network in the same population, they do not show evolutionary advantage over each other. (5) Scale-free network with disassortative mixing feature exhibits a more faster and more robust evolutionary performance than the assortative mixing one.
In short, this paper reveals the impact of the topological structure on the dynamic growing complex network when evolving to pre-defined target function. It benefits us to develop a more comprehensive understanding of the relationship among structure, function and evolution of the complex networks .
引文
[1] R. Albert and A.L. Barabási. Statistical mechanics of complex networks. Reviews of Modem Physics, 2002, 74(1): 47-97.
[2] A. Capocci, V.D.P. Servedio, F. Colaiori, L.S. Buriol, D. Donato, S. Leonardi, and G. Caldarelli. Preferential attachment in the growth of social networks: The internet encyclopedia Wikipedia. Phys. Rev. E, 2006, 74(3):036116.
[3] M. Barthelemy, and A. Flammini. Modeling Urban Street Patterns. Phys. Rev. Lett., 2008, 100(13):138702.
[4] R.X. Brunet and I.M. Sokolov.Growing networks under geographical constraints. Phys. Rev. E, 2007,75(4):046117.
[5] L.F. Costa, F.A. Rodrigues,and G. Travieso. Analyzing trails in complex networks. Phys. Rev. E, 2007, 76(2):046106.
[6] S.H. Strogat. Exploring complex networks. Nature, 2001, 410(6825): 268-276.
[7] S. Bernhardsson and P. Minnhagen. Models and average properties of scale-free directed networks. Phys. Rev. E, 2006, 74(2):026104.
[8] S. Ciliberti, O.C. Martin, A. Wagner. Robustness Can Evolve Gradually in Complex Regulatory Gene Networks with Varying Topology. PLOS, 2007, 3(2).
[9] M. Liu and K.E. Bassler. Emergent criticality from coevolution in random Boolean networks. Phys. Rev. E, 2006, 74(4):041910.
[10] M.E.J. Newman. The structure and function of complex networks. SIAM Review, 2003, 45(2): 167-256.
[11] R. Lambiotte, S. Thurner, and R.Hanel. Unanimity rule on networks. Phys. Rev. E, 2007, 76(2):046101.
[12] T. Antal, P.L. Krapivsky, and S. Redner. Dynamics of Social Balance on Networks. Phys. Rev. E, 2005, 72(3):036121.
[13] K.I. Goh,Y.H. Eom, H. Jeong, B. Kahng, and D. Kim. Structure and evolution of online social relationships: Heterogeneity in unrestricted discussions. Phys. Rev. E, 2006, 73(6):066123.
[14] S. Valverde and R.V. Solé. Self-organization versus hierarchy in open-source social networks. Phys. Rev. E, 2007, 76(4):046118.
[15] J.M. Kumpula, J.P. Onnela, J. Saramaki, K. Kaski, and J. Kertesz. Emergence of Communities in Weighted Networks. Phys. Rev. Lett., 2007, 99(22):228701.
[16] WenXu, Wang BingHong, Wang Bo,Hu GangYan and Qing Ou. General Dynamics ofTopology and Traffic on Weighted Technological Networks. Phys. Rev. Lett., 2005, 94(18):188702.
[17] A.L. Barabási. Linked: The new science of networks. Massachusetts, Persus Publishing, 2002.
[18] Erd? s and Rényi. On the evolution of random graphs. Publ.Math.Inst, 1960, 5:17-61.
[19] D.J. Watts and S.H. Strogatz. Collective dynamics of small-world networks. Nature, 1998, 393(6684):440-442.
[20] A.L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 1999, 286: 509-512.
[21] A.L. Barabási, R. Albert and H. Jeong. Scale-free characteristics of random networks: the topology of the World Wide Web. Physica A, 2000, 281(4):69-77.
[22] A.L. Barabási, H. Jeong, Z. Neda,E. Ravasz, A. Schubert, T. Vicsek.. Evolution of the social network of scientific collaborations. Physica A, 2002, 311(3):590-614.
[23] LiNa Wang, JinLi Guoa, HanXin Yang and Tao Zhou. Local preferential attachment model for hierarchical networks. Physica A, 2009, 388(8):1713-1720.
[24] T. Antal and P.L. Krapivsky. Weight-driven growing networks. Phys.Rev.E, 2005, 71(2):026103.
[25] A. Barrat, M. Barthélemy, and A. Vespignani. Weighted Evolving Networks: Coupling Topology and Weight Dynamics. Phys.Rev.E, 2004, 92(22):228701.
[26] Feng Fu, C. Hauert, M.A. Nowak,and Long Wang. Reputation-based partner choice promotes cooperation in social networks. Phys. Rev. E, 2008, 78(2):026117.
[27] Yihong Hu,Daoli Zhu,Nianqu Zhu. A weighted network evolution model based on passenger behaviour. Physics.soc-ph,2007.
[28] R.Albert and A.L.Barabasi. Topology of evolving networks:local events and universality. Phys.Rev.Lett, 2000, 85(24):5234-5237.
[29] Liang Tian,DaNing Shi,and ChenPing Zhu. Rank-based model for weighted network with hierarchical organization and disassortative mixing. European Physical Journal B, 2007,56(2):167-171.
[30] V.C. Barbosa,R. Donangelo,and S.R. Souza. Emergence of scale-free networks from local connectivity and communication trade-offs. Phys.Rev.E, 2006, 74(1):016113.
[31] M.J Alava,and S.N Dorogovtse. Complex networks created by aggregation. Phys. Rev. E, 2005, 71(3):036107.
[32] R.Albert, H.JeongH and A.L. Barabasi. Attack and error tolerance of complex networks. Nature, 2000, 406:378-382.
[33] Chunquan He, Qingsheng Ren. Robustness during Network Evolution. Fukuoka:International Conference on Complex, Intelligent and Software Intensive Systems, 2009:1240-1244.
[34] P.Oikonomou and P.Cluzel. Effects of topology on network evolution. Nature Physics, 2006,2(8):532-536.
[35] Zhen Shao,and Haijun Zhou.Dynamics-Driven Evolution to Structural Heterogeneity in Complex Networks. Physica A, 2008, 388(4):523-528.
[36] P. Satorras, and Vespignani. Epidemic Spreading in Scale-Free Networks. Phys.Rev.Lett, 2000, 86(14):3200-3203.
[37] A.L. Barabási, and Z.N. Oltvai. Network biology: understanding the cell's functional organization. Nature Reviews Genetics, 2004, 5: 101-113.
[38] J. Nacher, N. Ueda, T. Yamada, M. Kanehisa, T. Akutsu. Clustering under the line graph transformation: application to reaction network. BMC Bioinformatics, 2004, 5(1):207-211.
[39] T. Yamada, M. Kanehisa, S. Goto. Extraction of phylogenetic network modules from the metabolic network. BMC Bioinformatics, 2006, 7(1):130-134.
[40] E.Ravasz, and A.L.Barabasi. Hierarchicalorganization in complex networks. Phys.Rev.E, 2003, 67(2):026112.
[41] R. Geisberger, P. Sanders, D. Schultes. Better Approximation of Betweenness Centrality. Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments, 2008.
[42] M.E.J. Newman. Mixing patterns in networks. Phys Rev E, 2003, 67(2):026126.
[43] M.E.J. Newman. Assortative mixing in networks. Phys Rev Lett, 2002, 89(20):208701.
[44] B. Bollobas. Random Graphs. Cambridge University Press, 2001, 2 edition.
[45] S.A. Kauffman. Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of Theoritical Biology,1969, 22(3):437-467.
[46] I. Shmulevich, E.R. Dougherty, and W. Zhang. From Boolean to Probabilistic Boolean Networks as Models of Genetic Regulatory Networks. Proceedings of the IEEE, 2002, 90(11):1778-1792.
[47] B.J. Kim, A. Trusina, P. Minnhagen, and K. Sneppen. Self organized scale-free networks from merging and regeneration. European Physical Journal B, 2005, 43(3):369-372.
[48] C.C.Leung, H.F.Chau. Weighted assortative and disassortative networks model. Physica A, 2007, 378(2):591-602.
[49] H. Stefancic and V. Zlatic. Winner takes it all-Strongest node rule for evolution of scale-free networks. Phys. Rev. E, 2005, 72(3):036105.
[50] M. Serrano. Rich-club vs rich-multipolarization phenomena in weighted networks. Phys. Rev. E, 2008, 78(2):026101.
[51] N. Kashtan, U. Alon. Spontaneous evolution of modularity and network motifs. Proceedings of the National Academy of Sciences of the USA. 2005, 102(29):13773-13778.
[52] N. Kashtan, U. Alon. Varying environments can speed up evolution. Proceedings of the National Academy of Sciences of the USA. 2007, 104:13711-13716.
[53] M. Barahona, and L.M. Pecora. Synchronization in Small-World Systems. Phys.Rev.Lett, 2002, 89(5):054101.
[54] P. Holme, and B.J. Kim. Vertex overload breakdown in evolving networks. Phys.Rev.E, 2002, 65(6):066109.
[55] S. Redner. Networks: Teasing out the missing links. Nature, 2008, 453:47-48.
[2] A. Capocci, V.D.P. Servedio, F. Colaiori, L.S. Buriol, D. Donato, S. Leonardi, and G. Caldarelli. Preferential attachment in the growth of social networks: The internet encyclopedia Wikipedia. Phys. Rev. E, 2006, 74(3):036116.
[3] M. Barthelemy, and A. Flammini. Modeling Urban Street Patterns. Phys. Rev. Lett., 2008, 100(13):138702.
[4] R.X. Brunet and I.M. Sokolov.Growing networks under geographical constraints. Phys. Rev. E, 2007,75(4):046117.
[5] L.F. Costa, F.A. Rodrigues,and G. Travieso. Analyzing trails in complex networks. Phys. Rev. E, 2007, 76(2):046106.
[6] S.H. Strogat. Exploring complex networks. Nature, 2001, 410(6825): 268-276.
[7] S. Bernhardsson and P. Minnhagen. Models and average properties of scale-free directed networks. Phys. Rev. E, 2006, 74(2):026104.
[8] S. Ciliberti, O.C. Martin, A. Wagner. Robustness Can Evolve Gradually in Complex Regulatory Gene Networks with Varying Topology. PLOS, 2007, 3(2).
[9] M. Liu and K.E. Bassler. Emergent criticality from coevolution in random Boolean networks. Phys. Rev. E, 2006, 74(4):041910.
[10] M.E.J. Newman. The structure and function of complex networks. SIAM Review, 2003, 45(2): 167-256.
[11] R. Lambiotte, S. Thurner, and R.Hanel. Unanimity rule on networks. Phys. Rev. E, 2007, 76(2):046101.
[12] T. Antal, P.L. Krapivsky, and S. Redner. Dynamics of Social Balance on Networks. Phys. Rev. E, 2005, 72(3):036121.
[13] K.I. Goh,Y.H. Eom, H. Jeong, B. Kahng, and D. Kim. Structure and evolution of online social relationships: Heterogeneity in unrestricted discussions. Phys. Rev. E, 2006, 73(6):066123.
[14] S. Valverde and R.V. Solé. Self-organization versus hierarchy in open-source social networks. Phys. Rev. E, 2007, 76(4):046118.
[15] J.M. Kumpula, J.P. Onnela, J. Saramaki, K. Kaski, and J. Kertesz. Emergence of Communities in Weighted Networks. Phys. Rev. Lett., 2007, 99(22):228701.
[16] WenXu, Wang BingHong, Wang Bo,Hu GangYan and Qing Ou. General Dynamics ofTopology and Traffic on Weighted Technological Networks. Phys. Rev. Lett., 2005, 94(18):188702.
[17] A.L. Barabási. Linked: The new science of networks. Massachusetts, Persus Publishing, 2002.
[18] Erd? s and Rényi. On the evolution of random graphs. Publ.Math.Inst, 1960, 5:17-61.
[19] D.J. Watts and S.H. Strogatz. Collective dynamics of small-world networks. Nature, 1998, 393(6684):440-442.
[20] A.L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 1999, 286: 509-512.
[21] A.L. Barabási, R. Albert and H. Jeong. Scale-free characteristics of random networks: the topology of the World Wide Web. Physica A, 2000, 281(4):69-77.
[22] A.L. Barabási, H. Jeong, Z. Neda,E. Ravasz, A. Schubert, T. Vicsek.. Evolution of the social network of scientific collaborations. Physica A, 2002, 311(3):590-614.
[23] LiNa Wang, JinLi Guoa, HanXin Yang and Tao Zhou. Local preferential attachment model for hierarchical networks. Physica A, 2009, 388(8):1713-1720.
[24] T. Antal and P.L. Krapivsky. Weight-driven growing networks. Phys.Rev.E, 2005, 71(2):026103.
[25] A. Barrat, M. Barthélemy, and A. Vespignani. Weighted Evolving Networks: Coupling Topology and Weight Dynamics. Phys.Rev.E, 2004, 92(22):228701.
[26] Feng Fu, C. Hauert, M.A. Nowak,and Long Wang. Reputation-based partner choice promotes cooperation in social networks. Phys. Rev. E, 2008, 78(2):026117.
[27] Yihong Hu,Daoli Zhu,Nianqu Zhu. A weighted network evolution model based on passenger behaviour. Physics.soc-ph,2007.
[28] R.Albert and A.L.Barabasi. Topology of evolving networks:local events and universality. Phys.Rev.Lett, 2000, 85(24):5234-5237.
[29] Liang Tian,DaNing Shi,and ChenPing Zhu. Rank-based model for weighted network with hierarchical organization and disassortative mixing. European Physical Journal B, 2007,56(2):167-171.
[30] V.C. Barbosa,R. Donangelo,and S.R. Souza. Emergence of scale-free networks from local connectivity and communication trade-offs. Phys.Rev.E, 2006, 74(1):016113.
[31] M.J Alava,and S.N Dorogovtse. Complex networks created by aggregation. Phys. Rev. E, 2005, 71(3):036107.
[32] R.Albert, H.JeongH and A.L. Barabasi. Attack and error tolerance of complex networks. Nature, 2000, 406:378-382.
[33] Chunquan He, Qingsheng Ren. Robustness during Network Evolution. Fukuoka:International Conference on Complex, Intelligent and Software Intensive Systems, 2009:1240-1244.
[34] P.Oikonomou and P.Cluzel. Effects of topology on network evolution. Nature Physics, 2006,2(8):532-536.
[35] Zhen Shao,and Haijun Zhou.Dynamics-Driven Evolution to Structural Heterogeneity in Complex Networks. Physica A, 2008, 388(4):523-528.
[36] P. Satorras, and Vespignani. Epidemic Spreading in Scale-Free Networks. Phys.Rev.Lett, 2000, 86(14):3200-3203.
[37] A.L. Barabási, and Z.N. Oltvai. Network biology: understanding the cell's functional organization. Nature Reviews Genetics, 2004, 5: 101-113.
[38] J. Nacher, N. Ueda, T. Yamada, M. Kanehisa, T. Akutsu. Clustering under the line graph transformation: application to reaction network. BMC Bioinformatics, 2004, 5(1):207-211.
[39] T. Yamada, M. Kanehisa, S. Goto. Extraction of phylogenetic network modules from the metabolic network. BMC Bioinformatics, 2006, 7(1):130-134.
[40] E.Ravasz, and A.L.Barabasi. Hierarchicalorganization in complex networks. Phys.Rev.E, 2003, 67(2):026112.
[41] R. Geisberger, P. Sanders, D. Schultes. Better Approximation of Betweenness Centrality. Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments, 2008.
[42] M.E.J. Newman. Mixing patterns in networks. Phys Rev E, 2003, 67(2):026126.
[43] M.E.J. Newman. Assortative mixing in networks. Phys Rev Lett, 2002, 89(20):208701.
[44] B. Bollobas. Random Graphs. Cambridge University Press, 2001, 2 edition.
[45] S.A. Kauffman. Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of Theoritical Biology,1969, 22(3):437-467.
[46] I. Shmulevich, E.R. Dougherty, and W. Zhang. From Boolean to Probabilistic Boolean Networks as Models of Genetic Regulatory Networks. Proceedings of the IEEE, 2002, 90(11):1778-1792.
[47] B.J. Kim, A. Trusina, P. Minnhagen, and K. Sneppen. Self organized scale-free networks from merging and regeneration. European Physical Journal B, 2005, 43(3):369-372.
[48] C.C.Leung, H.F.Chau. Weighted assortative and disassortative networks model. Physica A, 2007, 378(2):591-602.
[49] H. Stefancic and V. Zlatic. Winner takes it all-Strongest node rule for evolution of scale-free networks. Phys. Rev. E, 2005, 72(3):036105.
[50] M. Serrano. Rich-club vs rich-multipolarization phenomena in weighted networks. Phys. Rev. E, 2008, 78(2):026101.
[51] N. Kashtan, U. Alon. Spontaneous evolution of modularity and network motifs. Proceedings of the National Academy of Sciences of the USA. 2005, 102(29):13773-13778.
[52] N. Kashtan, U. Alon. Varying environments can speed up evolution. Proceedings of the National Academy of Sciences of the USA. 2007, 104:13711-13716.
[53] M. Barahona, and L.M. Pecora. Synchronization in Small-World Systems. Phys.Rev.Lett, 2002, 89(5):054101.
[54] P. Holme, and B.J. Kim. Vertex overload breakdown in evolving networks. Phys.Rev.E, 2002, 65(6):066109.
[55] S. Redner. Networks: Teasing out the missing links. Nature, 2008, 453:47-48.