计算机科学 ›› 2016, Vol. 43 ›› Issue (Z6): 395-399.doi: 10.11896/j.issn.1002-137X.2016.6A.094
任泺锟,李慧嘉,贾传亮
REN Luo-kun, LI Hui-jia and JIA Chuan-liang
摘要: 探测网络社团结构对于分析、设计复杂的自然或工程网络至关重要,然而现有的探测技术主要依托于最优化和启发式算法,不能兼顾计算效率和准确性。因此提出了一种基于演化迭代技术的动态社团探测算法,它能准确高效地发现网络中的社团结构。首先引入了一个离散时间的动态系统,通过描述社团划分收敛到特定指标最优的演化轨迹来确定社团划分。接着提出了一个一般化的指标函数,以确定网络中最优的社团数量及最稳定的社团结构。该指标函数极具概括性,改变相应的参数即可引申到各种已广泛应用的指标函数。针对参数选择的困难,利用图生成模型自动确定社团划分的指标函数。此算法效率很高,计算复杂度与稀疏网络中的节点数量呈近似线性关系。最后,在人工和真实网络中进行了大量的仿真实验来测试算法表现,结果显示所提算法能够揭示很多有价值的信息。
[1] Wang X F,Chen G.Complex networks:Small-world,scale-free and beyond[J].IEEE Circuits and System Magazine,2003,3(1):6-20 [2] Newman M E J.Networks:an introduction[M].Oxford University Press,2010 [3] Lones M A,Caves A P,Stepney S,et al.Artificial biochemical networks:Evolving dynamical systems to control systems[J].IEEE Transactions on Evolutionary Computation,2012,18(2):145-166 [4] Palafox L,Noman N,Iba H.Reverse engineering of gene regulatory networks using dissipative particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2013,7(4):77-587 [5] Li H J,Daniels J.Social significance of community structure:Statistical view[J].Physical Review E,2015,91(1):012801 [6] Fortunato S.Community detection in graphs[J].Physics Reports,2010,6(3-5):75-174 [7] 李慧嘉.基于信息扩散的多尺度重叠社团快速探测算法[J].计算机科学,2014,1(9):125-131 [8] Pizzuti C.A multi-objective genetic algorithm to find communities in complex networks[J].IEEE Transactions on Evolutio-nary Computation,2012,16(3):418-430 [9] Liu Y,Moer J,Aviyente S.Network Community Structure Detection for Directional Neural Networks Inferred From Multichannel Multisubjective EEG Data[J].IEEE Transactions on Biomedical Engineering,2014,61(7):1919-1930 [10] 李慧嘉,李慧颖,李爱华.多尺度的社团结构稳定性分析[J].计算机学报,2015,8(2):301-312 |
No related articles found! |
|