复杂网络社区的分形聚类检测方法

doi:10.13229/j.cnki.jdxbgxb201605037

摘要/Abstract

摘要： 提出了两阶段盒子覆盖法,并且以两阶段盒子覆盖法作为节点聚类方法,提出了分形聚类社区检测算法FCUC。FCUC算法将分形聚类过程映射到树型结构,通过对树型结构进行分割得到复杂网络的社区结构。在人造网络和现实网络上对FCUC算法进行了测试,实验结果表明:FCUC算法可以有效地检测出社区结构。

关键词: 计算机应用, 复杂网络社区, 分形聚类, 盒子覆盖方法, 分形树

Abstract: Box-counting algorithm is an important approach to inspect the fractal property of complex networks. However, it neglects the weight of edges. To address this problem, a novel two-step box-counting algorithm is proposed, which is a clustering method. The proposed algorithm is applied to Fractal Cluster for Uncovering Community (FCUC). In FCUC, the nodes are clustered by two-step covering-box algorithm, and the fractal tree progress is mapped to a tree structure. Community structure can be uncovered through cutting the fractal tree according to evaluation function. Extensive tests on artificial networks and real networks give excellent results.

Key words: computer application, community of complex networks, fractal cluster, box-covering algorithm, fractal tree

中图分类号:

TP391

郭玉泉, 李雄飞. 复杂网络社区的分形聚类检测方法[J]. 吉林大学学报(工学版), 2016, 46(5): 1633-1638.

GUO Yu-quan, LI Xiong-fei. Fractal clustering method for uncovering community of complex network[J]. 吉林大学学报(工学版), 2016, 46(5): 1633-1638.

参考文献

[1] Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[2] Watts D J, Strogatz S H. Collective dynamics of 'small-world'networks[J]. Nature, 1998, 393(6684): 440-442.
[3] Song C, Havlin S, Makse H A. Self-similarity of complex networks[J]. Nature, 2005, 433(7024): 392-395.
[4] 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.
[5] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):066133.
[6] Barber M J, Clark J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E, 2009, 80(2): 026129.
[7] 郭玉泉,李雄飞,刘昕. 谱分析与启发式遗传算法相结合的多尺度社区检测方法[J]. 吉林大学学报:工学版,2015, 45(5): 1592-1600.
Guo Yu-quan, Li Xiong-fei, Liu Xin. Heuristic genetic algorithm associated with spectral analysis uncovering multi-scale community of complex networks[J]. Journal of Jilin University(Engineering and Technology Edition, 2015, 45(5): 1592-1600.
[8] Shen H W, Cheng X Q, Cai K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica a-Statistical Mechanics and Its Applications, 2009, 388(8): 1706-1712.
[9] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
[10] Jin D, Yang B, Baquero C, et al. A Markov random walk under constraint for discovering overlapping communities in complex networks[J]. Journal of Statistical Mechanics-Theory and Experiment. doi:10.1088/1742-5468/2011/05/P05031
[11] Newman M E J. Detecting community structure in networks[J]. European Physical Journal B, 2004, 38(2): 321-330.
[12] Gallos L K, Song C, Makse H A. A review of fractality and self-similarity in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2007, 386(2): 686-691.
[13] 王江涛, 杨建梅. 复杂网络的分形研究方法综述[J].复杂系统与复杂性科学, 2013, 10(4): 1-7.
Wang Jiang-tao, Yang Jian-mei.The review on fractal research of complex network[J]. Complex System and Complexity Science,2013,10(4):1-7.
[14] 孙延维,彭智明,李健波.基于粒子群优化与模糊聚类的社区发现算法[J].重庆邮电大学学报:自然科学版,2015,27(5):660-666.
Sun Yan-wei,Peng Zhi-ming,Li Jian-bo.Community detection algorithm based on particle swarm optimization and fuzzy clustering[J].Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition),2015,27(5):660-666.
[15] 陈新泉.基于单元网格近邻势的聚类方法[J].重庆邮电大学学报:自然科学版,2014,26(6):771-777.
Chen Xin-quan.Clustering method based on near neighbour influence of grid cells [J].Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition),2014,26(6):771-777.
[16] Wu Z, Lin Y, Wan H, et al. Efficient overlapping community detection in huge real-world networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012, 391(7): 2475-2490.
[17] Song C, Gallos L K, Havlin S, et al. How to calculate the fractal dimension of a complex network: the box covering algorithm[J]. Journal of Statistical Mechanics: Theory and Experiment, 2007, 2007(3): P03006.
[18] Zachary W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[19] Lusseau D. The emergent properties of a dolphin social network[J]. Proceedings of the Royal Society of London Series B: Biological Sciences, 2003, 270(Sup.2): 186-188.

相关文章 15

[1]	刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2]	王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3]	金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5]	刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6]	欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7]	刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9]	刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10]	车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11]	赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12]	黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13]	傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14]	曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15]	侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed