Node-grained incremental community detection for streaming networks

Siwen Yin, Shizhan Chen, Zhiyong Feng, Keman Huang, Dongxiao He*, Peng Zhao, Michael Ying Yang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

Community detection has been one of the key research topics in the analysis of networked data, which is a powerful tool for understanding organizational structures of complex networks. One major challenge in community detection is to analyze community structures for streaming networks in real-Time in which changes arrive sequentially and frequently. The existing incremental algorithms are often designed for edge-grained sequential changes, which are sensitive to the processing sequence of edges. However, there exist many real-world networks that changes occur on node-grained, i.e., node with its connecting edges is added into network simultaneously and all edges arrive at the same time. In this paper, we propose a novel incremental community detection method based on modularity optimization for node-grained streaming networks. This method takes one vertex and its connecting edges as a processing unit, and equally treats edges involved by same node. Our algorithm is evaluated on a set of real-world networks, and is compared with several representative incremental and non-incremental algorithms. The experimental results show that our method is highly effective for discovering communities in an incremental way. In addition, our algorithm even got better results than Louvain method (the famous modularity optimization algorithm using global information) in some test networks, e.g., citation networks, which are more likely to be node-grained. This may further indicate the significance of the node-grained incremental algorithms.

Original languageEnglish
Title of host publicationProceedings - 2016 IEEE 28th International Conference on Tools with Artificial Intelligence, ICTAI 2016
EditorsAnna Esposito, Miltos Alamaniotis, Amol Mali, Nikolaos Bourbakis
PublisherIEEE
Pages585-592
Number of pages8
ISBN (Electronic)9781509044597
DOIs
Publication statusPublished - 11 Jan 2017
Event28th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2016 - San Jose, United States
Duration: 6 Nov 20168 Nov 2016
Conference number: 28

Conference

Conference28th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2016
Abbreviated titleICTAI 2016
CountryUnited States
CitySan Jose
Period6/11/168/11/16

Keywords

  • Community detection
  • Complex network
  • Incremental algorithm
  • Modularity

Fingerprint Dive into the research topics of 'Node-grained incremental community detection for streaming networks'. Together they form a unique fingerprint.

  • Cite this

    Yin, S., Chen, S., Feng, Z., Huang, K., He, D., Zhao, P., & Yang, M. Y. (2017). Node-grained incremental community detection for streaming networks. In A. Esposito, M. Alamaniotis, A. Mali, & N. Bourbakis (Eds.), Proceedings - 2016 IEEE 28th International Conference on Tools with Artificial Intelligence, ICTAI 2016 (pp. 585-592). [7814655] IEEE. https://doi.org/10.1109/ICTAI.2016.0095