Predicting Community Numbers with Network Bayesian Information Criterion
Li Wenzheng1,Gu Yijun1(),Yan Hongli2
1 School of Information Technology and Cyber Security, People’s Public Security University of China, Beijing 100038, China 2 School of National Security and Counter Terrorism, People’s Public Security University of China, Beijing 100038, China
[Objective] This paper proposes an algorithm to predict the number of communities, aiming to improve the issues facing community detection algorithms. [Methods] First, we modified the Bayesian information criterion with characteristics of overlapping and non-overlapping community detection algorithms. Then, we constructed the Network Bayesian Information Criterion Algorithm to predict the number of communities. [Results] The accuracy and stability of the proposed algorithm were better than those of the Silhouette and Modularity algorithms. The accuracy of the former was 18% higher than those of the latter at least. [Limitations] Our new algorithm only includes the network structures. [Conclusions] The proposed algorithm based on Bayesian information criterion could effectively predict the number of network communities.
李文政,顾益军,闫红丽. 基于网络贝叶斯信息准则算法的社区数量预测研究*[J]. 数据分析与知识发现, 2020, 4(4): 72-82.
Li Wenzheng,Gu Yijun,Yan Hongli. Predicting Community Numbers with Network Bayesian Information Criterion. Data Analysis and Knowledge Discovery, 2020, 4(4): 72-82.
( Fu Shunshun, Gu Yijun, Zhang Dahan , et al. Overlapping Community Detection Algorithm Based on Improved MCMC Method[J]. Netinfo Security, 2017(9):138-142.)
( Zhan Wenwei, Xi Jingke, Wang Zhixiao . Hierarchical Agglomerative Community Detection Algorithm Based on Similarity Modularity[J]. Journal of System Simulation, 2017,29(5):1028-1032.)
[3]
Girvan M, Newman M E J. Community Structure in Social and Biological Networks[J]. Proceedings of the National Academy of Sciences, 2002,99(12):7821-7826.
doi: 10.1073/pnas.122653799
( Wang Yuhuan . Study on the Overlapping Community Detection Algorithm in Online Social Network and Application[D]. Shenyang: Northeastern University, 2014.)
[5]
Newman M E J . Finding and Evaluating Community Structure in Networks[J]. Physical Review E, 2004,69(2):026113.
doi: 10.1103/PhysRevE.69.026113
[6]
Newman M E J. C Community Detection and Graph Partitioning[J]. EPL (Europhysics Letters), 2013, 103(2): Article No. 28003.
[7]
Ma T, Xia Z . An Improved Label Propagation Algorithm Based on Node Importance and Random Walk for Community Detection[J]. Modern Physics Letters B, 2017,31(14):1750162.
doi: 10.1142/S0217984917501627
[8]
De Meo P, Ferrara E, Fiumara G, et al. Generalized Louvain Method for Community Detection in Large Networks[C]// Proceedings of the 11th International Conference on Intelligent Systems Design and Applications. IEEE, 2011: 88-93.
[9]
McAuley J, Leskovec J. Learning to Discover Social Circles in Ego Networks[C]// Proceedings of the 25th International Conference on Neural Information Processing Systems. 2012: 539-547.
[10]
Narantsatsralt U U, Kang S. Social Network Community Detection Using Agglomerative Spectral Clustering[J]. Complexity, 2017: Article ID 3719428.
[11]
Maulik U, Bandyopadhyay S . Performance Evaluation of Some Clustering Algorithms and Validity Indices[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(12):1650-1654.
doi: 10.1109/TPAMI.2002.1114856
[12]
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
[13]
桂春 . 复杂网络中的社团发现与链路预测[D]. 兰州: 兰州大学, 2018.
[13]
( Gui Chun . Community Detection and Link Prediction of Complex Networks[D]. Lanzhou: Lanzhou University, 2018.)
[14]
Rousseeuw P J . Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis[J]. Journal of Computational and Applied Mathematics, 1987,20:53-65.
doi: 10.1016/0377-0427(87)90125-7
[15]
Arnaboldi V, Passarella A, Conti M , et al. Online Social Networks: Human Cognitive Constraints in Facebook and Twitter Personal Graphs[M]. Elsevier, 2015: 59-62.
( Du Wenju, Zhang Jian’gang, Yu Jianning . Research on Stability of Complex Bus Community Network Model[J]. Computer Engineering and Applications, 2017,53(23):39-46.)
( Cai Biao, Tuo Xianguo, Sang Qiang , et al. Community Detection in Complex Network Based on Triangle Clique Attractors[J]. Computer Engineering, 2016,42(9):197-201.)
doi: 10.3969/j.issn.1000-3428.2016.09.035
[18]
Pelleg D, Moore A W. X-means: Extending K-means with Efficient Estimation of the Number of Clusters[C]// Proceedings of the 17th International Conference on Machine Learning. 2000,1:727-734.
( Chu Yuezhong . An k Means Clustering Algorithm Based on Bayesian Information Criterion[J]. Journal of Anhui University of Technology: Natural Science, 2010,27(4):409-412.)
[20]
Chakrabarti S, Khanna R. Structured Learning for Non-Smooth Ranking Losses[C]// Proceedings of SIGKDD Conference, ACM, 2008: 88-96.
[21]
Kass R E, Wasserman L . A Reference Bayesian Test for Nested Hypotheses and Its Relationship to the Schwarz Criterion[J]. Publications of the American Statistical Association, 1995,90(431):928-934.
( Yu Jian, Cheng Qiansheng . Search Range of Optimal Cluster Number in Fuzzy Clustering Method[J]. Scientia Sinica:Technologica, 2002,32(2):274-280.)
[24]
Syakur M A, Khotimah B K, Rochman E M S, et al. Integration K-Means Clustering Method and Elbow Method for Identification of the Best Customer Profile Cluster[J]. IOP Conference Series: Materials Science and Engineering, 2018,336(1):012017.
doi: 10.1088/1757-899X/336/1/012017