Comparing on Community Detection Algorithms for Information Mining
Chen Yunwei1(), Zhang Ruihong1,2
1Chengdu Library and Information Center, Chinese Academy of Sciences, Chengdu 610041, China 2University of Chinese Academy of Sciences, Beijing 101408, China
[Objective] This paper compares community detection algorithms in the field of complex network analysis, aiming to support related information science studies. [Methods] First, we identified the similarities and differences of several community detection algorithms (i.e. theoretical frameworks and calculation methods). Then, we examined these algorithms with small data sets. Third, we expanded the sample size, and evaluated the performance of Louvain algorithm, Louvain algorithm with multilevel refinement, and the SLM algorithm with the collaboration and citation networks. [Results] On small dataset, the detection results of GN and FN algorithms were similar, and the results of SLM algorithm were better than those of the Louvain algorithm and Louvain algorithm with multilevel refinement. In the field of library and information science, setting the resolution at 0.5 could help us analyze the detection results. The results of SLM algorithm were different to those of the Louvain algorithm or Louvain algorithm with multilevel refinement. Results of the latter two were almost the same, which were different with the resolution of 1.0. [Limitations] The dataset needs to be expanded. [Conclusions] The Louvain algorithm, Louvain algorithm with multilevel refinement and SLM algorithm are better than traditional algorithms. Among them, the SLM algorithm is the best option for us to analyze the community of citation network.
陈云伟, 张瑞红. 用于情报挖掘的典型网络社团划分算法比较研究*[J]. 数据分析与知识发现, 2018, 2(10): 84-94.
Chen Yunwei,Zhang Ruihong. Comparing on Community Detection Algorithms for Information Mining. Data Analysis and Knowledge Discovery, 2018, 2(10): 84-94.
Fortunato S, Castellano C. Community Structure in Graphs [OL]. [2009-03-10]. .
[2]
Kernighan B W, Lin S.An Efficient Heuristic Procedure for Partitioning Graphs[J]. Bell System Technical Journal, 1970, 49(2): 291-307.
doi: 10.1002/bltj.1970.49.issue-2
Phothen A, Simon H D,Liou K P.Partitioning Sparse Matrices with Eigenvectors of Graphs[J]. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452.
doi: 10.1137/0611030
[5]
Boccaletti S, Latora V, Moreno Y, et al.Complex Networks: Structure and Dynamics[J]. Physics Reports, 2006, 424(4-5): 175-308.
doi: 10.1016/j.physrep.2005.10.009
(Shi Jingjing.The Research of Three Typical Community Detection Algorithmsin Complex Networks[J]. Computer and Information Technology, 2011, 19(4): 42-43, 79.)
doi: 10.3969/j.issn.1005-1228.2011.04.014
[7]
Girvan M, Newman M E J. Community Structure in Social and Biological Networks[J]. PNAS, 2002, 99(12): 7821-7826.
doi: 10.1073/pnas.122653799
pmid: 12060727
[8]
Newman M E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E, 2004, 69(6): 066133.
doi: 10.1103/PhysRevE.69.066133
[9]
Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks[J]. Physical Review E, 2004, 69(2): 026113.
doi: 10.1103/PhysRevE.69.026113
[10]
Blondel V D, Guillaume J L, Lambiotte R, et al.Fast Unfolding of Communities in Large Networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008(10): P10008.
[11]
Rotta R, Noack A. Multilevel Local Search Algorithms for Modularity Clustering [J]. Journal of Experimental Algorithmics, 2011, 16(2): Article No. 2.3.
doi: 10.1145/1963190.1970376
[12]
Waltman L, Jan Van Eck N J. A Smart Local Moving Algorithm for Large-scale Modularity-based Community Detection[J]. The European Physical Journal B, 2013, 86(11): 471.
doi: 10.1140/epjb/e2013-40829-0
(Wu Zufeng, Wang Pengfei, Qin Zhiguang, et al.Improved Algorithm of Louvain Communities Dipartition[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(1): 105-108.)
doi: 10.3969/j.issn.1001-0548.2012.06.022
(Xia Wei, Yang Hebiao.Optimization of Louvain Algorithm and Its Application in Personalized Recommendation[J]. Information Technology, 2017(11): 125-128.)
doi: 10.13274/j.cnki.hdzj.2017.11.032
[16]
Zachary W W.An Information Flow Model for Conflict and Fission in Small Groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[17]
Chen P, Redner S.Community Structure of the Physical Review Citation Network[J]. Journal of Informetrics, 2010, 4(3): 278-290.
doi: 10.1016/j.joi.2010.01.001
[18]
Newman M E J. Scientific Collaboration Networks. II. Shortest Paths, Weighted Networks, and Centrality[J]. Physical Review E, 2001, 64(1): 016132.
doi: 10.1103/PhysRevE.64.016132
pmid: 11461356
[19]
Chen Y W, Börner K, Fang S.Evolving Collaboration Networks in Scientometrics in 1978-2010: A Micro-Macro Analysis[J]. Scientometrics, 2013, 95(3): 1051-1070.
doi: 10.1007/s11192-012-0895-2
[20]
陈云伟. 引文网络演化研究进展分析[J]. 情报科学, 2016, 34(8): 171-176.
[20]
(Chen Yunwei.Development of Evolving Citation Network Analysis[J]. Information Science, 2016, 34(8): 171-176.)