|
|
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 |
|
|
Abstract [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.
|
Received: 26 May 2019
Published: 01 June 2020
|
|
Corresponding Authors:
Gu Yijun
E-mail: guyijun@ppsuc.edu.cn
|
[1] |
付顺顺, 顾益军, 张大瀚 , 等. 基于改进MCMC方法的重叠社区发现算法[J]. 信息网络安全, 2017(9):138-142.
|
[1] |
( Fu Shunshun, Gu Yijun, Zhang Dahan , et al. Overlapping Community Detection Algorithm Based on Improved MCMC Method[J]. Netinfo Security, 2017(9):138-142.)
|
[2] |
占文威, 席景科, 王志晓 . 基于相似性模块度的层次聚合社区发现算法[J]. 系统仿真学报, 2017,29(5):1028-1032.
|
[2] |
( 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
|
[4] |
王宇欢 . 在线社会网络中基于属性的重叠社区发现算法研究与应用[D]. 沈阳: 东北大学, 2014.
|
[4] |
( 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.
|
[16] |
杜文举, 张建刚, 俞建宁 . 复杂公交社团网络模型的稳定性研究[J]. 计算机工程与应用, 2017,53(23):39-46.
|
[16] |
( 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.)
|
[17] |
蔡彪, 庹先国, 桑强 , 等. 复杂网络中基于三角环吸引子的社区检测[J]. 计算机工程, 2016,42(9):197-201.
doi: 10.3969/j.issn.1000-3428.2016.09.035
|
[17] |
( 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.
|
[19] |
储岳中 . 一类基于贝叶斯信息准则的k均值聚类算法[J]. 安徽工业大学学报: 自然科学版, 2010,27(4):409-412.
|
[19] |
( 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.
|
[22] |
侯作勋, 韩培, 张宏伟 , 等. 一种硬件友好型自适应K-均值学习算法[J]. 航天返回与遥感, 2017,38(3):68-77.
|
[22] |
( Hou Zuoxun, Han Pei, Zhang Hongwei , et al. An Hardware-friendly Adaptive K-means Learning Algorithm[J]. Spacecraft Recovery & Remote Sensing, 2017,38(3):68-77.)
|
[23] |
于剑, 程乾生 . 模糊聚类方法中的最佳聚类数的搜索范围[J]. 中国科学E辑:技术科学, 2002,32(2):274-280.
|
[23] |
( 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
|
[25] |
吴广建, 章剑林, 袁丁 . 基于K-means的手肘法自动获取K值方法研究[J]. 软件, 2019,40(5):167-170.
|
[25] |
( Wu Guangjian, Zhang Jianlin, Yuan Ding . Automatically Obtaining K Value Based on K-means Elbow Method[J]. Computer Engineering & Software, 2019,40(5):167-170.)
|
[26] |
Stanford Network Analysis Project. Stanford Large Network Dataset Collection[EB/OL]. [ 2019- 01- 15]. http://snap.stanford.edu/data/index.html.
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|