无权网络零模型的构造及应用
|
摘要
静态无权网络是目前最常见的复杂网络形式,这种网络零模型也被研究得最广泛和最深入。该文将无权网络分成无权无向网络和无权有向网络两种形式,分别研究了这两类网络的零模型构造及应用,其中重点是无权无向网络。首先根据不同阶数随机图理论阐述了无权无向网络由低到高各阶零模型的定义,然后描述了使用ER随机图、配置模型和基于断边重连等方式构造各阶零模型的过程及相关应用。针对断边重连这种最重要的零模型构造方式,论述了无倾向性断边重连、有倾向性同配或异配断边重连,以及检测网络是否具有富人俱乐部性质的局部断边重连等构造方式,并且首次将高阶零模型扩展到社团检测等网络中尺度特性的分析中。最后,阐述了无权有向网络1阶零模型的构造以及如何基于该零模型检测网络中存在的出入度匹配特性。该文发现网络零模型能为实证无权网络提供一个准确的基准,结合网络的统计量指标定性和定量地描述出实际复杂网络的非平凡特性以及这种非平凡特性的程度及来源。
The static unweighted network, whose null models have been studied widely and thoroughly, is the most common type of complex networks at present. In this study, we classify an unweighted network into two types of networks: undirected network and directed network. We study the construction and applications of null models for the two kinds of networks, especially the null models of unweighted undirected network are emphasized. Firstly, we illustrate the definitions of null models from low to high orders for unweighted undirected network according to the theory of random graph series. And then we describe the constructing process and related applications for 1 k-3 k null models by using ER random graph, configuration model, edge swapping, and so on. For the edge swapping algorithm, which is the most important mode for constructing null models, we introduce non-tendentious random edge swapping, tendentious assortative or dis-assortative edge swapping, and local edge swapping for detecting whether the rich-club properties exist in a network. Moreover, the high order null models are firstly extended to analyze meso-scale network features such as community detection. Finally, we analyze 1 k null models of directed network and tried to detect four types of in-out degree assortativities. In this study, we find that null models can not only provide an accurate baseline for real-life networks, but also qualitatively and quantitatively describe non-trivial properties of empirical complex networks.
The static unweighted network, whose null models have been studied widely and thoroughly, is the most common type of complex networks at present. In this study, we classify an unweighted network into two types of networks: undirected network and directed network. We study the construction and applications of null models for the two kinds of networks, especially the null models of unweighted undirected network are emphasized. Firstly, we illustrate the definitions of null models from low to high orders for unweighted undirected network according to the theory of random graph series. And then we describe the constructing process and related applications for 1 k-3 k null models by using ER random graph, configuration model, edge swapping, and so on. For the edge swapping algorithm, which is the most important mode for constructing null models, we introduce non-tendentious random edge swapping, tendentious assortative or dis-assortative edge swapping, and local edge swapping for detecting whether the rich-club properties exist in a network. Moreover, the high order null models are firstly extended to analyze meso-scale network features such as community detection. Finally, we analyze 1 k null models of directed network and tried to detect four types of in-out degree assortativities. In this study, we find that null models can not only provide an accurate baseline for real-life networks, but also qualitatively and quantitatively describe non-trivial properties of empirical complex networks.
引文
[1]GJOKA M,KURANT M,MARKOPOULOU A.2.5K-graphs:from sampling to generation[C]//IEEEINFOCOM.New York:IEEE,2013:1968-1976.
[2]MAHADEVAN P,HUBBLE C,KRIOUKOV D V,et al.Orbis:Rescaling degree correlations to generate annotated internet topologies[J].ACM Special Interest Group on Data Communication,2007,37(4):325-336.
[3]MAHADEVAN P,KRIOUKOV D V,FALL K R,et al.Systematic topology analysis and generation using degree correlations[J].ACM Special Interest Group on Data Communication,2006,36(4):135-146.
[4]ORSINI C,DANKULOV M M,et al.Quantifying randomness in real networks[J].Nature Communications,2015,6:8627.
[5]BOLLOBAS B.Random graphs[M].England:Cambridge University Press,2001.
[6]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.
[7]BARABáSI A,ALBERT R.Statistical mechanics of complex networks[J].Reviews of Modern Physics,2002,74(1):47-97.
[8]MOLLOY M,REED B.The size of the giant component of a random graph with a given degree sequence[J].Combinatorics,Probability and Computing,1998,7(3):295-305.
[9]尚可可,许小可.基于置乱算法的复杂网络零模型构造及其应用[J].电子科技大学学报,2014,43(1):7-20.SHANG Ke-ke,XU Xiao-ke.Construction and application for null models of complex networks based on randomized algorithms[J].Journal of University of Electronic Science and Technology of China,2014,43(1):7-20.
[10]尚可可.在线社交网络的零模型构造和行为预测研究[D].青岛:青岛理工大学,2013.SHANG Ke-ke,The study of null model construction and user behavior prediction for online social networks[D].Qingdao:Qingdao Technological University,2013.
[11]MOLLOY M,REED B.A critical point for random graphs with a given degree sequence[J].Random Structures and Algorithms,1995,6(2-3):161-180.
[12]NEWMAN M E J,SRROGATZ S H,WATTS D J.Random graphs with arbitrary degree distributions and their applications[J].Physical Review E,2001,64(2):26118.
[13]WATTS D J,STROGATZ S H.Collective dynamics of‘small-world’networks[J].Nature,1998,393(6684):440-442.
[14]BARABASI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.
[15]明均仁,党永杰.基于科研贡献度加权的作者合作网络对比研究[J].数字图书馆论坛,2016(1):34-40.MING Jun-ren,DANG Yong-jie.Comparative study of author collaboration network based on scientific contribution degree[J].Digital Library Forum,2016(1):34-40.
[16]李慧嘉,李慧颖,李爱华.多尺度的社团结构稳定性分析[J].计算机学报,2015,38(2):301-312.LI Hui-jia,LI Hui-ying,LI Ai-hua.Analysis of multi-scale stability in community structure[J].Chonese Journal of Computers,2015,38(2):301-312.
[17]王林,戴冠中.复杂网络的度分布研究[J].西北工业大学学报,2006,24(4):405-409.WANG Lin,DAI Guan-zhong.On degree distribution of complex network[J].Journal of Northwestern Polytechnical University,2006,24(4):405-409.
[18]陈庆华.无标度网络的相关性和联合度分布[J].福建师大学报(自然科学版),2006,22(1):1-6.CHEN Qing-hua.Correlations and joint degree distributions of scale-free networks[J].Journal of Fujian Normal University(Natural Science Edition),2006,22(1):1-6.
[19]NEWMAN M E J.Clustering and preferential attachment in growing networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2001,64(2):025102.
[20]NEWMAN M E J.Random graphs with clustering[J].Physical Review Letters,2009,103(5):58701.
[21]NEWMAN M E J,KARRER B.Random graphs containing arbitrary distributions of subgraphs[J].Physical Review E,2010,82(6):66118.
[22]NEWMAN M E J.Networks:an introduction[M].郭世泽,陈哲,译.北京:电子工业出版社,2010.NEWMAN M E J.Networks:an introduction[M].Translated by GUO Shi-ze,CHEN Zhe.Beijing:Publishing House of Electronics Industry,2010.
[23]HOLME P.Network reachability of real-world contact sequences[J].Physical Review E,2005,71(4):46119.
[24]MASLOV S,SNEPPEN K.Specificity and stability in topology of protein networks[J].Science,2002,296(5569):910-913.
[25]李欢,卢罡,郭俊霞.复杂网络零模型的量化评估[J].计算机应用,2015,35(6):1560-1563.LI Huan,LU Gang,GUO Jun-xia.Quantitative evaluation for null models of complex networks[J].Journal of Computer Applications,2015,35(6):1560-1563
[26]曾进群,杨建梅,陈泉,等.基于零模型的开源社区大众生产合作网络结构研究[J].华南理工大学学报(社会科学版),2013(2):29-34.ZENG Jin-qun,YANG Jian-mei,CHEN Quan,et al.Research of the open source community cooperation network structure of the mass production based on null model[J].Journal of South China University of Technology(Social Science Edition),2013(2):29-34.
[27]陈泉,杨建梅,曾进群.零模型及其在复杂网络研究中的应用[J].复杂系统与复杂性科学,2013(1):8-17.CHEN Quan,YANG Jian-mei,ZENG Jin-qun.Null model and its application in the reserch of complex nexworks[J].Complex Systems and Complexity Science,2013(1):8-17.
[28]MILO R,SHEN-ORR S,ITZKOVITZ S,et al.Network motifs:Simple building blocks of complex networks[J].Science,2002,298(5594):824-827.
[29]SHEN-ORR S,MILO R,MANGAN S,et al.Network motifs in the transcriptional regulation network of escherichia coli[J].Nature Genetics,2002,31(1):64-68.
[30]MILO R,ITZKOVITZ S,KASHTAN N,et al.Superfamilies of evolved and designed networks[J].Science,2004,303(5663):1538-1542.
[31]MASLOV S,SNEPPEN K,ZALIZNVAK A.Detection of topological patterns in complex networks:correlation profile of the internet[J].Physica A:Statistical Mechanics and its Applications,2004,333:529-540.
[32]ZHOU S,MONDRAGON R J.The rich-club phenomenon in the internet topology[J].IEEE Communications Letters,2004,8(3):180-182.
[33]COLIZZA V,FLAMMINI A,SERRANO M A,et al.Detecting rich-club ordering in complex networks[J].Nature Physics,2006,2(2):110-115.
[34]AMARAL N L A,GUIMERA R.Complex networks:Lies,damned lies and statistics[J].Nature Physics,2006,2(2):75-76.
[35]ZHOU S,MONDRAGON R J.Structural constraints in complex networks[J].New Journal of Physics,2007,9(6):173.
[36]XU Xiao-ke,ZHANG J,SMALL M.Rich-club connectivity dominates assortativity and transitivity of complex networks[J].Physical Review E,2010,82(4):46117.
[37]NEWMAN M E J.Assortative mixing in networks[J].Physical Review Letters,2002,89(20):208701.
[38]NEWMAN M E J.Mixing patterns in networks[J].Physical Review E,2003,67(2):26126.
[39]XU Xiao-ke,ZHANG J,SUN J,et al.Revising the simple measures of assortativity in complex networks[J].Physical Review E,2009,80(5):56106.
[40]NEWMAN M E J.Detecting community structure in networks[J].The European Physicial Journal B-Condensed Matter and Complex Systems,2004,38(2):321-330.
[41]DANON L,DIZA-GUILERA A,DUCH J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005(9):P09008.
[42]FORTUNATO S Community detection in graphs[J].Physics Reports,2010,486(3-5):75-174.
[43]CAI Q,MA L J,GONG M G,et al.A survey on network community detection based on evolutionary computation.[J].Int J Bio-Inspired Computation,2016,8(2):84-98.
[44]FLAKE G W,LAWRENCE S,GILES C L,et al.Self-organization and identification of web communities[J].Computer,2002,35(3):66-70.
[45]TAYLOR D,SHAI S,STANLEY N,et al.Enhanced detectability of community structure in multilayer networks through layer aggregation[J].Physical review letters,2016,116(22):228301.
[46]BAZZI M,PORTER M A,WILLIAMS S,et al.Community detection in temporal multilayer networks,with an application to correlation networks[J].Multiscale Modeling&Simulation,2016,14(1):1-41.
[47]THAKUR S,DHIMAN M,TELL G,et al.A review on protein-protein interaction network of APE1/Ref-1 and its associated biological functions[J].Cell Biochemistry&Function,2015,33(3):101-112.
[48]李晓佳,张鹏,狄增如,等.复杂网络中的社团结构[J].复杂系统与复杂性科学,2008,5(3):19-42.LI Xiao-jia,ZHANG Peng,DI Zeng-ru,et al.Community structure in complex networks[J].Complex Systems And Complexity Science,2008,5(3):19-42.
[49]CUI W K,SHANG K K,ZHANG Y J,et al.Constructing null networks for community detection in complex networks[J].European Physical Journal B,2018,91(7):145.
[50]LENG Z F.Community detection in complex networks based on greedy optimization[J].Acta Elecronic Sinica,2014,42(4):723-728.
[51]刘亚冰.复杂网络中的社团结构特性研究[D].上海:上海交通大学,2010.LIU Ya-bing.Analysis of community structure in complex networks[D].Shanghai:Shanghai Jiao Tong University,2010.
[52]唐明,崔爱香,袭凯.关注耦合网络及其传播动力学研究[J].复杂系统与复杂性科学,2011,8(2):87-91.TANG Ming,CUI Ai-xiang,XI Kai.On spreading dynamics on coupled networks[J].Complex Systems and Complexity Science,2011,8(2):87-91.
[53]汪小帆,李翔,陈关荣.复杂网络引论--模型、结构与动力学[M].北京:高等教育出版社,2012:217-218.WANG Xiao-fan,LI Xiang,CHEN Guan-rong.Introduction to complex networks:models,structures and dynamics[M].Beijing:Higher Education Press,2012:217-218.
[54]SHANG Ke-ke,YAN W S,SMALL M.Evolving networks-using past structure to predict the future[J].Physica A:Statistical Mechanics and Its Applications,2016,455:120-35.
[55]SHANG Ke-ke,SMALL M,XU X K,et al.The role of direct links for link prediction in evolving networks[J].EPL(Europhysics Letters),2017,117(2):28002.
[56]FOETER J G,FOSTER D V,GRASSBERGER P.Edge direction and the structure of networks[J].Proceedings of the National Academy of Sciences,2010,107(24):10815-10820.
[2]MAHADEVAN P,HUBBLE C,KRIOUKOV D V,et al.Orbis:Rescaling degree correlations to generate annotated internet topologies[J].ACM Special Interest Group on Data Communication,2007,37(4):325-336.
[3]MAHADEVAN P,KRIOUKOV D V,FALL K R,et al.Systematic topology analysis and generation using degree correlations[J].ACM Special Interest Group on Data Communication,2006,36(4):135-146.
[4]ORSINI C,DANKULOV M M,et al.Quantifying randomness in real networks[J].Nature Communications,2015,6:8627.
[5]BOLLOBAS B.Random graphs[M].England:Cambridge University Press,2001.
[6]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.
[7]BARABáSI A,ALBERT R.Statistical mechanics of complex networks[J].Reviews of Modern Physics,2002,74(1):47-97.
[8]MOLLOY M,REED B.The size of the giant component of a random graph with a given degree sequence[J].Combinatorics,Probability and Computing,1998,7(3):295-305.
[9]尚可可,许小可.基于置乱算法的复杂网络零模型构造及其应用[J].电子科技大学学报,2014,43(1):7-20.SHANG Ke-ke,XU Xiao-ke.Construction and application for null models of complex networks based on randomized algorithms[J].Journal of University of Electronic Science and Technology of China,2014,43(1):7-20.
[10]尚可可.在线社交网络的零模型构造和行为预测研究[D].青岛:青岛理工大学,2013.SHANG Ke-ke,The study of null model construction and user behavior prediction for online social networks[D].Qingdao:Qingdao Technological University,2013.
[11]MOLLOY M,REED B.A critical point for random graphs with a given degree sequence[J].Random Structures and Algorithms,1995,6(2-3):161-180.
[12]NEWMAN M E J,SRROGATZ S H,WATTS D J.Random graphs with arbitrary degree distributions and their applications[J].Physical Review E,2001,64(2):26118.
[13]WATTS D J,STROGATZ S H.Collective dynamics of‘small-world’networks[J].Nature,1998,393(6684):440-442.
[14]BARABASI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.
[15]明均仁,党永杰.基于科研贡献度加权的作者合作网络对比研究[J].数字图书馆论坛,2016(1):34-40.MING Jun-ren,DANG Yong-jie.Comparative study of author collaboration network based on scientific contribution degree[J].Digital Library Forum,2016(1):34-40.
[16]李慧嘉,李慧颖,李爱华.多尺度的社团结构稳定性分析[J].计算机学报,2015,38(2):301-312.LI Hui-jia,LI Hui-ying,LI Ai-hua.Analysis of multi-scale stability in community structure[J].Chonese Journal of Computers,2015,38(2):301-312.
[17]王林,戴冠中.复杂网络的度分布研究[J].西北工业大学学报,2006,24(4):405-409.WANG Lin,DAI Guan-zhong.On degree distribution of complex network[J].Journal of Northwestern Polytechnical University,2006,24(4):405-409.
[18]陈庆华.无标度网络的相关性和联合度分布[J].福建师大学报(自然科学版),2006,22(1):1-6.CHEN Qing-hua.Correlations and joint degree distributions of scale-free networks[J].Journal of Fujian Normal University(Natural Science Edition),2006,22(1):1-6.
[19]NEWMAN M E J.Clustering and preferential attachment in growing networks[J].Physical Review E Statistical Nonlinear&Soft Matter Physics,2001,64(2):025102.
[20]NEWMAN M E J.Random graphs with clustering[J].Physical Review Letters,2009,103(5):58701.
[21]NEWMAN M E J,KARRER B.Random graphs containing arbitrary distributions of subgraphs[J].Physical Review E,2010,82(6):66118.
[22]NEWMAN M E J.Networks:an introduction[M].郭世泽,陈哲,译.北京:电子工业出版社,2010.NEWMAN M E J.Networks:an introduction[M].Translated by GUO Shi-ze,CHEN Zhe.Beijing:Publishing House of Electronics Industry,2010.
[23]HOLME P.Network reachability of real-world contact sequences[J].Physical Review E,2005,71(4):46119.
[24]MASLOV S,SNEPPEN K.Specificity and stability in topology of protein networks[J].Science,2002,296(5569):910-913.
[25]李欢,卢罡,郭俊霞.复杂网络零模型的量化评估[J].计算机应用,2015,35(6):1560-1563.LI Huan,LU Gang,GUO Jun-xia.Quantitative evaluation for null models of complex networks[J].Journal of Computer Applications,2015,35(6):1560-1563
[26]曾进群,杨建梅,陈泉,等.基于零模型的开源社区大众生产合作网络结构研究[J].华南理工大学学报(社会科学版),2013(2):29-34.ZENG Jin-qun,YANG Jian-mei,CHEN Quan,et al.Research of the open source community cooperation network structure of the mass production based on null model[J].Journal of South China University of Technology(Social Science Edition),2013(2):29-34.
[27]陈泉,杨建梅,曾进群.零模型及其在复杂网络研究中的应用[J].复杂系统与复杂性科学,2013(1):8-17.CHEN Quan,YANG Jian-mei,ZENG Jin-qun.Null model and its application in the reserch of complex nexworks[J].Complex Systems and Complexity Science,2013(1):8-17.
[28]MILO R,SHEN-ORR S,ITZKOVITZ S,et al.Network motifs:Simple building blocks of complex networks[J].Science,2002,298(5594):824-827.
[29]SHEN-ORR S,MILO R,MANGAN S,et al.Network motifs in the transcriptional regulation network of escherichia coli[J].Nature Genetics,2002,31(1):64-68.
[30]MILO R,ITZKOVITZ S,KASHTAN N,et al.Superfamilies of evolved and designed networks[J].Science,2004,303(5663):1538-1542.
[31]MASLOV S,SNEPPEN K,ZALIZNVAK A.Detection of topological patterns in complex networks:correlation profile of the internet[J].Physica A:Statistical Mechanics and its Applications,2004,333:529-540.
[32]ZHOU S,MONDRAGON R J.The rich-club phenomenon in the internet topology[J].IEEE Communications Letters,2004,8(3):180-182.
[33]COLIZZA V,FLAMMINI A,SERRANO M A,et al.Detecting rich-club ordering in complex networks[J].Nature Physics,2006,2(2):110-115.
[34]AMARAL N L A,GUIMERA R.Complex networks:Lies,damned lies and statistics[J].Nature Physics,2006,2(2):75-76.
[35]ZHOU S,MONDRAGON R J.Structural constraints in complex networks[J].New Journal of Physics,2007,9(6):173.
[36]XU Xiao-ke,ZHANG J,SMALL M.Rich-club connectivity dominates assortativity and transitivity of complex networks[J].Physical Review E,2010,82(4):46117.
[37]NEWMAN M E J.Assortative mixing in networks[J].Physical Review Letters,2002,89(20):208701.
[38]NEWMAN M E J.Mixing patterns in networks[J].Physical Review E,2003,67(2):26126.
[39]XU Xiao-ke,ZHANG J,SUN J,et al.Revising the simple measures of assortativity in complex networks[J].Physical Review E,2009,80(5):56106.
[40]NEWMAN M E J.Detecting community structure in networks[J].The European Physicial Journal B-Condensed Matter and Complex Systems,2004,38(2):321-330.
[41]DANON L,DIZA-GUILERA A,DUCH J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005(9):P09008.
[42]FORTUNATO S Community detection in graphs[J].Physics Reports,2010,486(3-5):75-174.
[43]CAI Q,MA L J,GONG M G,et al.A survey on network community detection based on evolutionary computation.[J].Int J Bio-Inspired Computation,2016,8(2):84-98.
[44]FLAKE G W,LAWRENCE S,GILES C L,et al.Self-organization and identification of web communities[J].Computer,2002,35(3):66-70.
[45]TAYLOR D,SHAI S,STANLEY N,et al.Enhanced detectability of community structure in multilayer networks through layer aggregation[J].Physical review letters,2016,116(22):228301.
[46]BAZZI M,PORTER M A,WILLIAMS S,et al.Community detection in temporal multilayer networks,with an application to correlation networks[J].Multiscale Modeling&Simulation,2016,14(1):1-41.
[47]THAKUR S,DHIMAN M,TELL G,et al.A review on protein-protein interaction network of APE1/Ref-1 and its associated biological functions[J].Cell Biochemistry&Function,2015,33(3):101-112.
[48]李晓佳,张鹏,狄增如,等.复杂网络中的社团结构[J].复杂系统与复杂性科学,2008,5(3):19-42.LI Xiao-jia,ZHANG Peng,DI Zeng-ru,et al.Community structure in complex networks[J].Complex Systems And Complexity Science,2008,5(3):19-42.
[49]CUI W K,SHANG K K,ZHANG Y J,et al.Constructing null networks for community detection in complex networks[J].European Physical Journal B,2018,91(7):145.
[50]LENG Z F.Community detection in complex networks based on greedy optimization[J].Acta Elecronic Sinica,2014,42(4):723-728.
[51]刘亚冰.复杂网络中的社团结构特性研究[D].上海:上海交通大学,2010.LIU Ya-bing.Analysis of community structure in complex networks[D].Shanghai:Shanghai Jiao Tong University,2010.
[52]唐明,崔爱香,袭凯.关注耦合网络及其传播动力学研究[J].复杂系统与复杂性科学,2011,8(2):87-91.TANG Ming,CUI Ai-xiang,XI Kai.On spreading dynamics on coupled networks[J].Complex Systems and Complexity Science,2011,8(2):87-91.
[53]汪小帆,李翔,陈关荣.复杂网络引论--模型、结构与动力学[M].北京:高等教育出版社,2012:217-218.WANG Xiao-fan,LI Xiang,CHEN Guan-rong.Introduction to complex networks:models,structures and dynamics[M].Beijing:Higher Education Press,2012:217-218.
[54]SHANG Ke-ke,YAN W S,SMALL M.Evolving networks-using past structure to predict the future[J].Physica A:Statistical Mechanics and Its Applications,2016,455:120-35.
[55]SHANG Ke-ke,SMALL M,XU X K,et al.The role of direct links for link prediction in evolving networks[J].EPL(Europhysics Letters),2017,117(2):28002.
[56]FOETER J G,FOSTER D V,GRASSBERGER P.Edge direction and the structure of networks[J].Proceedings of the National Academy of Sciences,2010,107(24):10815-10820.