An Effective Algorithm for Optimizing Surprise in Network Community Detection

IEEE Access

Shi Chen¹  Yong-Jun Chen²  Yong-Hong Tang²  Yuan-Yuan Gao³  Yan-Ni Tang³  Ju Xiang³  Jian-Ming Li³  Yan Zhang⁴  Hui-Jia Li⁵  Zhi-Zhong Wang⁶ 

[1] Department of Information Science and Engineering, Changsha Medical University, Changsha, China;Department of Neurology, Nanhua Affiliated Hospital, University of South China, Hengyang, China;Neuroscience Research Center, School of Basic Medical Sciences, Changsha Medical University, Changsha, China;School of Computer Science and Engineering, Central South University, Changsha, China;School of Science, Beijing University of Posts and Telecommunications, Beijing, China;South City College, Hunan First Normal University, Changsha, China;

关键词: Complex networks;    community detection;    Surprise;    disease module;    disease gene;   

DOI  :  10.1109/ACCESS.2019.2946080

来源: DOAJ

【 摘 要 】

Many methods have been proposed to detect communities/modules in various networks such as biological molecular networks and disease networks, while optimizing statistical measures for community structures is one of the most popular ways for community detection. Surprise, which is a statistical measure of interest for community detection, has good performance in many networks, but it still encounters the resolution limit in some cases and it is hard to be optimized due to its strong nonlinearity. Here, we discussed the resolution limit of Surprise by a phase diagram in community-partition transition, and then proposed an improved algorithm for Surprise optimization by introducing three effective strategies: a pre-processing of topological structure based on local random walks (Pre_TS), a pre-processing of community partition (Pre_CS), and a post-processing of community partition (Post_CS). By a series of experimental tests in various networks, we show that Pre_TS can effectively enhance the resolution of Surprise, Pre_CS and Post_CS can improve the optimization performance in different aspects, and as expected, the combination of these strategies can more effectively enhance the ability of Surprise to detect communities in complex networks. Finally, we displayed the effectiveness of the improved algorithm for Surprise optimization in several real-world networks, and applied the algorithm to the analysis of disease-related networks in computational biology.

【 授权许可】

Unknown