计算机科学 ›› 2018, Vol. 45 ›› Issue (2): 76-83.doi: 10.11896/j.issn.1002-137X.2018.02.013
• 2017年中国计算机学会人工智能会议 • 上一篇 下一篇
郑文萍,曲瑞,穆俊芳
ZHENG Wen-ping, QU Rui and MU Jun-fang
摘要: 近年来,生成图模型在复杂网络研究中的作用越来越重要。图的生成过程对于研究疾病的蔓延和信息的传播具有重大意义,同时图模型的生成也有助于更深入地研究复杂网络的特性。为了能够生成既符合真实网络特征又具有结构多样性的复杂网络,提出了一种具有社区结构的可调节聚集系数和模块性的无标度网络生成算法——TCMSN(Scale Free Network with Tunable Clustering Coefficient and Modularity)。通过调节混合参数可以调节生成网络的模块性,通过调节社区内连边的概率和混合参数可以对网络聚集系数进行调节。TCMSN采用了合理的连边策略,在不破坏网络结构多样性的情况下,能尽可能维持网络的无标度特性。人工构造数据和真实网络数据的对比实验结果表明,TCMSN算法能够生成可调节聚集系数和模块性的无标度网络模型,且能够生成最接近真实网络社区结构特征的网络模型。
[1] YANG B,LIU D Y,JIN D,et al.Complex network clustering algorithms[J].Journal of Software,2009,20(1):54-66.(in Chinese) 杨博,刘大有,金弟,等.复杂网络聚类方法[J].软件学报,2009,0(1):54-66. [2] WANG J,LIANG J Y,ZHENG W P.A graph clustering me-thod for detecting protein complexes [J].Journal of Computer Research and Development,2015,52(8):1784-1793.(in Chinese) 王杰,梁吉业,郑文萍.一种面向蛋白质复合体检测的图聚类方法[J].计算机研究与发展,2015,52(8):1784-1793. [3] XING Y K,MA S P.A clustering algorithm based on markov chain models [J].Journal of Computer Research and Development,2003,40(2):129-135.(in Chinese) 邢永康,马少平.一种基于Markov链模型的动态聚类方法[J].计算机研究与发展,2003,40(2):129-135. [4] ZHOU S G,ZHOU A Y,CAO J,et al.A fast density-based clustering algorithm [J].Journal of Computer Research and Development,2000,37(11):1287-1292.(in Chinese) 周水庚,周傲英,曹晶,等.一种基于密度的快速聚类算法[J].计算机研究与发展,2000,37(11):1287-1292. [5] LANCICHINETTI A,FORTUNATO S,KERTSZ J.Detec-ting the overlapping and hierarchical community structure in complex networks [J].New Journal of Physics,2009,11(3):033015. [6] WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ networks [J].Nature,1998,393(6684):440-442. [7] BARABSI A,ALBERT R.Emergence of scaling in randomnetworks [J].Science,1999,286(5439):509-512. [8] HOLME P,KIM B J.Growing scale-free networks with tunable clustering [J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2002,65(2):26017. [9] DOROGOVTSEV S N,MENDES J F F.Evolution of networks [J].Advances in Physics,2001,51(4):1079-1187. [10] LIU J G,DANG Y Z,WANG Z T.Multistage random growing small-world networks with power-law degree distribution[J].Chinese Physics Letters,2006,23(3):746-749. [11] ZHANG L H.Simulation and application researchers on complex network modeling [D].Dalian:Dalian University of Technology,2013.(in Chinese) 张兰华.复杂网络建模的仿真与应用研究[D].大连:大连理工大学,2013. [12] CUI A X.Research on modeling and spreading dynamics of complex networks[D].Chengdu:University of Electronic Science and Technology of China,2014.(in Chinese) 崔爱香.复杂网络建模及其传播动力学研究[D].成都:电子科技大学,2014. [13] LIU S J.Construction of complex network models and analysis of their properties [D].Chengdu:Southwest Jiaotong University,2015.(in Chinese) 刘胜久.复杂网络模型构建及特性分析[D].成都:西南交通大学,2015. [14] FRONCZAK A,FRONCZAK P,HOYST J A.Mean-field theo-ry for clustering coefficients in Barabási-Albert networks [J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2003,68(4):046126. [15] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks [J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826. [16] NEWMAN M E J.Fast algorithm for detecting communitystructure in networks[J].Physical Review E Statistical Nonli-near & Soft Matter Physics,2004,69(6 Pt 2):066133. [17] NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E Statistical Nonlinear &Soft Matter Physics,2004,69(2):026113. [18] LANICHINETTI A,FORTUNATO S,RADICCHI F.Bench-mark graphs for testing community detection algorithms [J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2008,78(4):046110. [19] MOLLOY M,REED B.A critical point for random graphs with a given degree sequence [J].Random Structures & Algorithms,1995,6(2-3):161-180. [20] SESHADHRI C,KOLDA T G,PINAR A.Community structure and scale-free collections of Erds-Rényi graphs[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2012,85(5):056109. [21] KOLDA T G,PINAR A,PLANTENGA T,et al.A scalable generative graph model with community structure[J].Siam Journal on Scientific Computing,2014,36(5),C424-C452. [22] AMARAL L A,SCALA A,BARTHELEMY M,et al.Classes of small-world networks [J].Proceedings of the National Aca-demy of Sciences of the United States of America,2000,97(21):11149-11152. [23] ECKMANN J P,MOSES E.Curvature of co-links uncovers hidden thematic layers in the World Wide Web [J].Proceedings of the National Academy of Sciences of the United States of Ameri-ca,2002,99(9):5825-5829. [24] BARABSI A L,ALBERT R,JEONG H.Scale-free characteris-tics of random networks:the topology of the world-wide Web [J].Physica A Statistical Mechanics & Its Applications,2000,281(1-4):69-77. [25] ALBERT R,JEONG H.Diameter of the World Wide Web [J].Nature,1999,401(6):130-131. [26] DOROGOVTSEV S N,MENDES J F.Language as an evolving word web[J].Proceedings Biological Sciences,2001,268(1485):2603-2606. [27] RIPEANU M,FOSTER I,IAMNITCHI A.Mapping the gnutella network:properties of Large-Scale Peer-to-Peer systems and implications for system design [J].IEEE Internet Computing,2002,6(1):50-57. [28] JEONG H,TOMBOR B,ALERT R,et al.The large-scale organization of metabolic networks [J].Nature,2000,407(6804):651-654. [29] HUXHAM M,RAFFAELLI D.Do parasites reduce the chances of triangulation in a real food web [J].Oikos,1996,76(2):284-300. [30] CANCHO R F I,JANSSEN C,SOL R V.Topology of techno-logy graphs:small world patterns in electronic circuits [J].Phy-sical Review E,2001,64(4):046119. [31] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks [J].Journal of Statistical Mechanics Theory & Experiment,2008,2008(10):155-168. |
No related articles found! |
|