TY - JOUR
T1 - A Novel Method for Detecting New Overlapping Community in Complex Evolving Networks
AU - Cheng, Jiujun
AU - Wu, Xiao
AU - Zhou, Mengchu
AU - Gao, Shangce
AU - Huang, Zhenhua
AU - Liu, Cong
N1 - Funding Information:
Manuscript received August 7, 2017; accepted November 17, 2017. Date of publication January 5, 2018; date of current version August 16, 2019. This work was supported in part by the National Natural Science Foundation of China (Key Program) under Grant 61331009, in part by the National Natural Science Foundation of China under Grant 61472284 and Grant 61772366, in part by the Deanship of Scientific Research (DSR) at King Abdulaziz University, Jeddah, under Grant G-415-135-38, and in part by JSPS KAKENHI under Grant JP17K12751. This paper was recommended by Associate Editor E. Herrera-Viedma. (Corresponding authors: Mengchu Zhou; Shangce Gao; Zhenhua Huang.) J. Cheng, X. Wu, and Z. Huang are with the Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 200092, China (e-mail: chengjj@tongji.edu.cn; smfwux-iao@163.com; huangzhenhua@tongji.edu.cn).
Publisher Copyright:
© 2018 IEEE.
PY - 2019/9
Y1 - 2019/9
N2 - It is an important challenge to detect an overlapping community and its evolving tendency in a complex network. To our best knowledge, there is no such an overlapping community detection method that exhibits high normalized mutual information (NMI) and F-score, and can also predict an overlapping community's future considering node evolution, activeness, and multiscaling. This paper presents a novel method based on node vitality, an extension of node fitness for modeling network evolution constrained by multiscaling and preferential attachment. First, according to a node's dynamics such as link creation and destruction, we find node vitality by comparing consecutive network snapshots. Then, we combine it with the fitness function to obtain a new objective function. Next, by optimizing the objective function, we expand maximal cliques, reassign overlapping nodes, and find the overlapping community that matches not only the current network but also the future version of the network. Through experiments, we show that its NMI and F-score exceed those of the state-of-the-art methods under diverse conditions of overlaps and connection densities. We also validate the effectiveness of node vitality for modeling a node's evolution. Finally, we show how to detect an overlapping community in a real-world evolving network.
AB - It is an important challenge to detect an overlapping community and its evolving tendency in a complex network. To our best knowledge, there is no such an overlapping community detection method that exhibits high normalized mutual information (NMI) and F-score, and can also predict an overlapping community's future considering node evolution, activeness, and multiscaling. This paper presents a novel method based on node vitality, an extension of node fitness for modeling network evolution constrained by multiscaling and preferential attachment. First, according to a node's dynamics such as link creation and destruction, we find node vitality by comparing consecutive network snapshots. Then, we combine it with the fitness function to obtain a new objective function. Next, by optimizing the objective function, we expand maximal cliques, reassign overlapping nodes, and find the overlapping community that matches not only the current network but also the future version of the network. Through experiments, we show that its NMI and F-score exceed those of the state-of-the-art methods under diverse conditions of overlaps and connection densities. We also validate the effectiveness of node vitality for modeling a node's evolution. Finally, we show how to detect an overlapping community in a real-world evolving network.
KW - Evolving network
KW - fitness function
KW - maximal clique
KW - multiscaling
KW - node fitness
KW - node vitality
KW - overlapping community
KW - shared community degree
UR - http://www.scopus.com/inward/record.url?scp=85040621628&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85040621628&partnerID=8YFLogxK
U2 - 10.1109/TSMC.2017.2779138
DO - 10.1109/TSMC.2017.2779138
M3 - Article
AN - SCOPUS:85040621628
SN - 2168-2216
VL - 49
SP - 1832
EP - 1844
JO - IEEE Transactions on Systems, Man, and Cybernetics: Systems
JF - IEEE Transactions on Systems, Man, and Cybernetics: Systems
IS - 9
M1 - 8248661
ER -