LFM Community Detection Algorithm Based on Vertex Similarity
YANG Xiaobo1, CHEN Chuxiang1, WANG Zhiwan2
1.College of Science, The Information Engineering University, Zhengzhou 450000, China; 2.Respiratory Department, the First Affiliated Hospital of Henan University of Traditional Chinese Medicine, Zhengzhou 450000, China
Abstract：In network with fuzzy community structure, precision of the traditional LFM algorithm decreases apparently. In order to solve this problem, an LFMJ algorithm is presented. Using the information of neighbor nodes and improved Jaccard coefficient, this algorithm reconstructed the network structure, and improved the precision of community division results. To validate the algorithm, five algorithms was tested in LFR benchmark and real networks, including LFMJ, traditional LFM, LPA algorithm and WT, FUA algorithm, which have better performance in community detection. The results show that, in LFR network, the accuracy of LFMJ is higher than both LFM and LPA, equaling to WT and FUA algorithm. In real network and LFR network with overlapping community, LFMJ gets the highest accuracy than others. The effectiveness of the algorithm is proved.
杨晓波, 陈楚湘, 王至婉. 基于节点相似性的LFM社团发现算法[J]. 复杂系统与复杂性科学, 2017, 14(3): 85-90.
YANG Xiaobo, CHEN Chuxiang, WANG Zhiwan. LFM Community Detection Algorithm Based on Vertex Similarity. Complex Systems and Complexity Science, 2017, 14(3): 85-90.
[1]高启航,景丽萍,于剑,等. 基于结构和适应度的社区发现[J]. 中国科学技术大学学报, 2014, 44(7): 563569. Gao Qihang, Jing Liping, Yu Jian, et al. Community detection based on structure and fitness [J]. Journal of University of Science and Techno-logy of China, 2014, 44(7): 563569. [2]Girvan M, Newman M E J. Community structure in social and biological networks [J]. P Natl Acad Sci USA, 2002, 99(12): 78217826. [3]Newman M E J. Modularity and community structure in networks [J]. Proc of National Academy of Science, 2006, 103(23): 85778582. [4]Raghavan U N, Albert R, Kumara S. Near linear-time algorithm to detect community structures in large-scale networks [J]. Phys Rev E, 2007, 76(3): 036106. [5]Pascal P, Matthieu L. Computing communities in large networks using random walks [J]. J Graph Algorithms Appl, 2006, 10(2): 191218. [6]Blondel V D, Guillaume J L, Lambiotte R, et al. Fast Unfolding of communites in large networks [J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, (10):155168. [7]刘大有,金弟,何东晓,等. 复杂网络社区挖掘综述[J]. 计算机研究与发展, 2013, 50(10): 21402154. Liu Dayou, Jin Di, He Dongxiao, et al. Community mining in complex networks [J], Journal of Computer Research and Development, 2013, 50(10): 21402154. [8]Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure in complex networks [J]. New Journal of Physics, 2009, 11(3): 033015. [9]李建华,汪晓锋,吴鹏. 基于局部优化的社区发现方法研究现状[J]. 中国科学院院刊, 2015, 30(2): 238247. Li Jianhua, Wang Xiaofeng, Wu Peng. Review on community detection methods based on local optimization [J]. Bulletin of Chinese Academy of Sciences, 2015, 30(2): 238247. [10] 刘倩,刘群. 基于引力度扩展的重叠社区发现算法[J]. 计算机工程与设计, 2014, 35(3): 852856. Liu Qian, Liu Qun. Overlapping community detection algorithm based on expansion of gravitational degree [J]. Computer Engineering and Design, 2014, 35(3): 852856. [11] 张若昕,柴丹炜,熊小峰,等. 基于节点相似度的社团发现算法研究[J]. 电脑知识与技术, 2015, 11(8): 4244. Zhang Ruoxin, Chai Danwei, Xiong Xiaofeng, et al. The research on community detection algorithm based on node similarity [J]. Computer Knowledge and Techonlogy, 2015, 11(8): 4244. [12] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms [J]. Phys Rev E, 2008, 78(4): 046110. [13] Lancichinetti A, Fortunato S. Community detection algorithms: a comparative analysis [J]. Phys Rev E, 2009, 80(5): 056117.
