吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (5): 1633-1638.doi: 10.13229/j.cnki.jdxbgxb201605037

Previous Articles     Next Articles

Fractal clustering method for uncovering community of complex network

GUO Yu-quan, LI Xiong-fei   

  1. College of Computer Science and Technology, Jilin University, Changchun 130012,China
  • Received:2015-05-19 Online:2016-09-20 Published:2016-09-20

RICH HTML

0   

PDF (PC)

198

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

CLC Number: 

  • TP391
[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.
[1] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] CHU Liang, WANG Yan-bo, QI Fu-wei, ZHANG Yong-sheng. Control method of inlet valves for brake pressure fine regulation[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[3] LI Jing, WANG Zi-han, YU Chun-xian, HAN Zuo-yue, SUN Bo-hua. Design of control system to follow vehicle state with HIL test beach[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[4] HU Xing-jun, LI Teng-fei, WANG Jing-yu, YANG Bo, GUO Peng, LIAO Lei. Numerical simulation of the influence of rear-end panels on the wake flow field of a heavy-duty truck[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[5] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[6] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[7] MA Wan-jing, XIE Han-zhou. Integrated control of main-signal and pre-signal on approach of intersection with double stop line[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[8] YU De-xin, TONG Qian, YANG Zhao-sheng, GAO Peng. Forecast model of emergency traffic evacuation time under major disaster[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .
[9] XIAO Yun, LEI Jun-qing, ZHANG Kun, LI Zhong-san. Fatigue stiffness degradation of prestressed concrete beam under multilevel amplitude cycle loading[J]. 吉林大学学报(工学版), 2013, 43(03): 665 -670 .
[10] XIAO Rui, DENG Zong-cai, LAN Ming-zhang, SHEN Chen-liang. Experiment research on proportions of reactive powder concrete without silica fume[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd