IncNSA: Detecting communities incrementally from time-evolving networks based on node similarity

Xing Su (), Jianjun Cheng, Haijuan Yang, Mingwei Leng (), Wenbo Zhang () and Xiaoyun Chen
Additional contact information
Xing Su: School of Information Science and Engineering, Lanzhou University, No. 222, Tianshui South Road, Lanzhou 730000, P. R. China
Jianjun Cheng: School of Information Science and Engineering, Lanzhou University, No. 222, Tianshui South Road, Lanzhou 730000, P. R. China
Haijuan Yang: School of Information Science and Engineering, Lanzhou University, No. 222, Tianshui South Road, Lanzhou 730000, P. R. China†Department of Electronic Information Engineering, Lanzhou Vocational Technical College, No. 37, Liusha Road, Lanzhou 730070, P. R. China
Mingwei Leng: #x2021;School of Education Science and Technology, Northwest Minzu University, No. 1, Xibei Xincun, Lanzhou 730030, P. R. China
Wenbo Zhang: School of Information Science and Engineering, Lanzhou University, No. 222, Tianshui South Road, Lanzhou 730000, P. R. China
Xiaoyun Chen: School of Information Science and Engineering, Lanzhou University, No. 222, Tianshui South Road, Lanzhou 730000, P. R. China

International Journal of Modern Physics C (IJMPC), 2020, vol. 31, issue 07, 1-19

Abstract: Many real-world systems can be abstracted as networks. As those systems always change dynamically in nature, the corresponding networks also evolve over time in general, and detecting communities from such time-evolving networks has become a critical task. In this paper, we propose an incremental detection method, which can stably detect high-quality community structures from time-evolving networks. When the network evolves from the previous snapshot to the current one, the proposed method only considers the community affiliations of partial nodes efficiently, which are either newborn nodes or some active nodes from the previous snapshot. Thus, the first phase of our method is determining active nodes that should be reassigned due to the change of their community affiliations in the evolution. Then, we construct subgraphs for these nodes to obtain the preliminary communities in the second phase. Finally, the final result can be obtained through optimizing the primary communities in the third phase. To test its performance, extensive experiments are conducted on both some synthetic networks and some real-world dynamic networks, the results show that our method can detect satisfactory community structure from each of snapshot graphs efficiently and steadily, and outperforms the competitors significantly.

Keywords: Incremental community detection; time-evolving network; active node; node similarity; most similar neighbor (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183120500941
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:31:y:2020:i:07:n:s0129183120500941

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183120500941

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().