计算机科学 ›› 2018, Vol. 45 ›› Issue (2): 76-83.doi: 10.11896/j.issn.1002-137X.2018.02.013

• 2017年中国计算机学会人工智能会议 • 上一篇    下一篇

具有社区结构的无标度网络生成算法

郑文萍,曲瑞,穆俊芳   

  1. 山西大学计算机与信息技术学院 太原 030006;山西大学计算智能与中文信息处理教育部重点实验室 太原 030006;大数据挖掘与智能技术山西省协同创新技术中心山西大学 太原 030006,山西大学计算机与信息技术学院 太原 030006,山西大学计算机与信息技术学院 太原 030006
  • 出版日期:2018-02-15 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金(61572005),山西省回国留学人员科研基金(2017-014)资助

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

摘要: 近年来,生成图模型在复杂网络研究中的作用越来越重要。图的生成过程对于研究疾病的蔓延和信息的传播具有重大意义,同时图模型的生成也有助于更深入地研究复杂网络的特性。为了能够生成既符合真实网络特征又具有结构多样性的复杂网络,提出了一种具有社区结构的可调节聚集系数和模块性的无标度网络生成算法——TCMSN(Scale Free Network with Tunable Clustering Coefficient and Modularity)。通过调节混合参数可以调节生成网络的模块性,通过调节社区内连边的概率和混合参数可以对网络聚集系数进行调节。TCMSN采用了合理的连边策略,在不破坏网络结构多样性的情况下,能尽可能维持网络的无标度特性。人工构造数据和真实网络数据的对比实验结果表明,TCMSN算法能够生成可调节聚集系数和模块性的无标度网络模型,且能够生成最接近真实网络社区结构特征的网络模型。

关键词: 网络生成模型,BA无标度网络,聚集系数,社区结构

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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!