Computer Science ›› 2018, Vol. 45 ›› Issue (2): 76-83.doi: 10.11896/j.issn.1002-137X.2018.02.013

Previous Articles     Next Articles

Generation Algorithm for Scale-free Networks with Community Structure

ZHENG Wen-ping, QU Rui and MU Jun-fang   

  • Online:2018-02-15 Published:2018-11-13

Abstract: Generating complex network models can help researchers to understand network behaviors and simulate the transmission processes of disease epidemics and information diffusion.It is also important to generate complex networks meeting the characteristics of real networks and having structural diversity.A network generation algorithm TCMSN (Scale-free Network with Tunable Clustering Coefficient and Modularity) was proposed to generate scale-free complex networks with tunable clustering coefficient and modularity.TCMSN can adjust modularity by changing the mixing parameter and adjust clustering coefficient by changing the global preferential attachment probability and mixing parameter of the network.It adopts a reasonable strategy about adding edges in networks to maintain the scale-free characteristics,as much as possible without destroying network diversity.Experimental results on artificial data sets and real networks show that the proposed TCMSN algorithm can not only generate scale-free network model with tunable clustering coefficient and modularity,but also generate network model closed to the community structure of the real networks.

Key words: Network generation models,BA scale free network,Clustering coefficient,Community structure

[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,KERTSZ 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] BARABSI 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,HOYST 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 Erds-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] BARABSI 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!
Full text



No Suggested Reading articles found!