Please wait a minute...
Data Analysis and Knowledge Discovery  2018, Vol. 2 Issue (10): 84-94    DOI: 10.11925/infotech.2096-3467.2018.0542
Current Issue | Archive | Adv Search |
Comparing on Community Detection Algorithms for Information Mining
Yunwei Chen1(),Ruihong Zhang1,2
1Chengdu Library and Information Center, Chinese Academy of Sciences, Chengdu 610041, China
2University of Chinese Academy of Sciences, Beijing 101408, China
Download: PDF(1869 KB)   HTML ( 1
Export: BibTeX | EndNote (RIS)      
Abstract  

[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.

Key wordsComplex Network      Community      Collaboration Network      Citation Network     
Received: 14 May 2018      Published: 12 November 2018

Cite this article:

Yunwei Chen,Ruihong Zhang. Comparing on Community Detection Algorithms for Information Mining. Data Analysis and Knowledge Discovery, 2018, 2(10): 84-94.

URL:

http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2018.0542     OR     http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2018/V2/I10/84

[1] 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.
[3] Fildler M.Algebraic Connectivity of Graphs[J]. Czechoslovak Mathematical Journal, 1973, 23(98): 298-305.
[4] 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.
[5] Boccaletti S, Latora V, Moreno Y, et al.Complex Networks: Structure and Dynamics[J]. Physics Reports, 2006, 424(4-5): 175-308.
[6] 时京晶. 三种经典复杂网络社区结构划分算法研究[J]. 电脑与信息技术, 2011, 19(4): 42-43, 79.
[6] (Shi Jingjing.The Research of Three Typical Community Detection Algorithmsin Complex Networks[J]. Computer and Information Technology, 2011, 19(4): 42-43, 79.)
[7] Girvan M, Newman M E J. Community Structure in Social and Biological Networks[J]. PNAS, 2002, 99(12): 7821-7826.
[8] Newman M E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E, 2004, 69(6): 066133.
[9] Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks[J]. Physical Review E, 2004, 69(2): 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.
[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.
[13] 吴卫江, 李沐南, 李国和. Louvain算法的并行化处理[J]. 计算机与数字工程, 2016, 44(8): 1402-1406.
[13] (Wu Weijiang, Li Munan, Li Guohe.Parallel Processing of the Louvain Algorithm[J]. Computer & Digital Engineering, 2016, 44(8): 1402-1406.)
[14] 吴祖峰, 王鹏飞, 秦志光, 等. 改进的Louvain社团划分算法[J]. 电子科技大学学报, 2013, 42(1): 105-108.
[14] (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.)
[15] 夏玮, 杨鹤标. 改进的Louvain算法及其在推荐领域的研究[J]. 信息技术, 2017(11): 125-128.
[15] (Xia Wei, Yang Hebiao.Optimization of Louvain Algorithm and Its Application in Personalized Recommendation[J]. Information Technology, 2017(11): 125-128.)
[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.
[18] Newman M E J. Scientific Collaboration Networks. II. Shortest Paths, Weighted Networks, and Centrality[J]. Physical Review E, 2001, 64(1): 016132.
[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.
[20] 陈云伟. 引文网络演化研究进展分析[J]. 情报科学, 2016, 34(8): 171-176.
[20] (Chen Yunwei.Development of Evolving Citation Network Analysis[J]. Information Science, 2016, 34(8): 171-176.)
[1] Liqing Qiu,Wei Jia,Xin Fan. Influence Maximization Algorithm Based on Overlapping Community[J]. 数据分析与知识发现, 2019, 3(7): 94-102.
[2] Ming Yi,Tingting Zhang. Ranking Answer Quality of Popular Q&A Community[J]. 数据分析与知识发现, 2019, 3(6): 12-20.
[3] Xiaolan Wu,Chengzhi Zhang. Analysis of Knowledge Flow Based on Academic Social Networks:
A Case Study of ScienceNet.cn
[J]. 数据分析与知识发现, 2019, 3(4): 107-116.
[4] Quan Lu,Anqi Zhu,Jiyue Zhang,Jing Chen. Research on User Information Requirement in Chinese Network Health Community: Taking Tumor-forum Data of Qiuyi as an Example[J]. 数据分析与知识发现, 2019, 3(4): 22-32.
[5] Xiang Li,Xiaodong Qian. Research on Impact of Commodity Online Evaluation for Consumption Convergence[J]. 数据分析与知识发现, 2019, 3(3): 102-111.
[6] Xiwei Wang,Duo Wang,Qingxiao Zheng,Ya’nan Wei. Information Interaction Between User and Enterprise in Online Brand Community: A Study of Virtual Reality Industry[J]. 数据分析与知识发现, 2019, 3(3): 83-94.
[7] Yanshuang Mei,Hengmin Zhu,Jing Wei. A Study on the Mechanism of Media Collaboration on the Spread of Internet Public Opinion[J]. 数据分析与知识发现, 2019, 3(2): 65-71.
[8] Xiaodong Qian,Min Li. Identifying E-commerce User Types Based on Complex Network Overlapping Community[J]. 数据分析与知识发现, 2018, 2(6): 79-91.
[9] Junwan Liu,Bo Yang,Feifei Wang. Ranking Scholarly Impacts Based on Citations and Academic Similarity[J]. 数据分析与知识发现, 2018, 2(4): 59-70.
[10] He Li,Linlin Zhu,Min Yan,Jincheng Liu,Chuang Hong. Identifying Useful Information from Open Innovation Community[J]. 数据分析与知识发现, 2018, 2(12): 12-22.
[11] Xiufeng Cheng,Xinyi Zhang,Ning Wang. Identifying Trending Topics in Q&A Community with CART Decision Tree[J]. 数据分析与知识发现, 2018, 2(12): 52-59.
[12] Xiaohua Shi,Hongtao Lu. Detecting Community in Scientific Collaboration Network with Bayesian Symmetric NMF[J]. 数据分析与知识发现, 2017, 1(9): 49-56.
[13] Chuanming Yu,Yutian Gong,Xiaoli Zhao,Lu An. Collaboration Recommendation of Finance Research Based on Multi-feature Fusion[J]. 数据分析与知识发现, 2017, 1(8): 39-47.
[14] Yaxian Qing,Rui Li,Huayi Wu. Analyzing Academic Community Based on Co-author Network[J]. 数据分析与知识发现, 2017, 1(4): 20-29.
[15] Weimin Lv,Xiaomei Wang,Tao Han. Recommending Scientific Research Collaborators with Link Prediction and Extremely Randomized Trees Algorithm[J]. 数据分析与知识发现, 2017, 1(4): 38-45.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626,82624938   E-mail:jishu@mail.las.ac.cn