Node-grained incremental community detection for streaming networks

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

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

Fingerprint

Complex networks
Processing

Keywords

  • Community detection
  • Complex network
  • Incremental algorithm
  • Modularity

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
Yin, Siwen ; Chen, Shizhan ; Feng, Zhiyong ; Huang, Keman ; He, Dongxiao ; Zhao, Peng ; Yang, Michael Ying. / Node-grained incremental community detection for streaming networks. Proceedings - 2016 IEEE 28th International Conference on Tools with Artificial Intelligence, ICTAI 2016. editor / Anna Esposito ; Miltos Alamaniotis ; Amol Mali ; Nikolaos Bourbakis. IEEE, 2017. pp. 585-592
@inproceedings{2707ffe939eb4f3ab34004eb6e873db1,
title = "Node-grained incremental community detection for streaming networks",
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.",
keywords = "Community detection, Complex network, Incremental algorithm, Modularity",
author = "Siwen Yin and Shizhan Chen and Zhiyong Feng and Keman Huang and Dongxiao He and Peng Zhao and Yang, {Michael Ying}",
year = "2017",
month = "1",
day = "11",
doi = "10.1109/ICTAI.2016.0095",
language = "English",
pages = "585--592",
editor = "Anna Esposito and Miltos Alamaniotis and Amol Mali and Nikolaos Bourbakis",
booktitle = "Proceedings - 2016 IEEE 28th International Conference on Tools with Artificial Intelligence, ICTAI 2016",
publisher = "IEEE",
address = "United States",

}

Yin, S, Chen, S, Feng, Z, Huang, K, He, D, Zhao, P & Yang, MY 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., 7814655, IEEE, pp. 585-592, 28th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2016, San Jose, United States, 6/11/16. https://doi.org/10.1109/ICTAI.2016.0095

Node-grained incremental community detection for streaming networks. / Yin, Siwen; Chen, Shizhan; Feng, Zhiyong; Huang, Keman; He, Dongxiao; Zhao, Peng; Yang, Michael Ying.

Proceedings - 2016 IEEE 28th International Conference on Tools with Artificial Intelligence, ICTAI 2016. ed. / Anna Esposito; Miltos Alamaniotis; Amol Mali; Nikolaos Bourbakis. IEEE, 2017. p. 585-592 7814655.

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

TY - GEN

T1 - Node-grained incremental community detection for streaming networks

AU - Yin, Siwen

AU - Chen, Shizhan

AU - Feng, Zhiyong

AU - Huang, Keman

AU - He, Dongxiao

AU - Zhao, Peng

AU - Yang, Michael Ying

PY - 2017/1/11

Y1 - 2017/1/11

N2 - 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.

AB - 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.

KW - Community detection

KW - Complex network

KW - Incremental algorithm

KW - Modularity

UR - https://ezproxy2.utwente.nl/login?url=https://library.itc.utwente.nl/login/2016/chap/yang_nod.pdf

UR - https://ezproxy2.utwente.nl/login?url=https://doi.org/10.1109/ICTAI.2016.0095

U2 - 10.1109/ICTAI.2016.0095

DO - 10.1109/ICTAI.2016.0095

M3 - Conference contribution

SP - 585

EP - 592

BT - Proceedings - 2016 IEEE 28th International Conference on Tools with Artificial Intelligence, ICTAI 2016

A2 - Esposito, Anna

A2 - Alamaniotis, Miltos

A2 - Mali, Amol

A2 - Bourbakis, Nikolaos

PB - IEEE

ER -

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