Sun, Hanlin, Jie, Wei ORCID: https://orcid.org/0000-0002-5392-0009, Sauer, Christian, Ma, Sugang, Han, Gang, Wang, Zhongmin and Xing, Kui (2017) A parallel self-organizing community detection algorithm based on swarm intelligence for large scale complex networks. In: 41st Annual IEEE Conference on Computers, Software and Applications (IEEE COMPSAC'2017), 04-08 July 2017, Torino, Italy.

Preview

PDF A Parallel Self-Organizing Community Detection Algorithm Based on Swarm Intelligence for Large Scale Complex Networks - COMPSAC 2017.pdf - Accepted Version Download (153kB) | Preview

Abstract

Community detection is a critical task for complex network analysis. It helps us to understand the properties of the system that a complex network represents and has significance to a wide range of applications. Nowadays, the challenges faced by community detection algorithms include overlapping community structure detection, large scale network analysis, dynamic changing of analyzed network topology and many more. In this paper a self-organizing community detection algorithm, based on the idea of swarm intelligence, was proposed and its parallel algorithm was designed on Giraph++ which is a semi-asynchronous parallel graph computation framework running on distributed environment. In the algorithm, a network of large size is firstly divided into a number of small sub-networks. Then, each sub-network is modeled as a self-evolving swarm intelligence sub-system, while each vertex within the sub-network acts iteratively to join into or leave from communities based on a set of predefined vertex action rules. Meanwhile, the local communities of a sub-network are sent to other sub-networks to make their members have a chance to join into, therefore connecting these self-evolving swarm intelligence sub-systems together as a whole, large and evolving, system. The vertex actions during evolution of a sub-network are sent as well to keep multiple community replicas being consistent. Thus network communication efficiency has a great impact on the algorithm’s performance. While there is no vertex changing in its belonging communities anymore, an optimal community structure of the whole network will have emerged as a result. In the algorithm it is natural that a vertex can join into multiple communities simultaneously, thus can be used for overlapping community detection. The algorithm deals with vertex and edge adding or deleting in the same way as the algorithm running, therefore inherently supports dynamic network analysis. The algorithm can be used for the analysis of large scale networks with its parallel version running on distributed environment. A variety of experiments conducted on synthesized networks have shown that the proposed algorithm can effectively detect community structures and its performance is much better than certain popular community detection algorithms.

Item Type:	Conference or Workshop Item (Paper)
ISSN:	0730-3157
ISBN:	9781538603680
Identifier:	10.1109/COMPSAC.2017.31
Page Range:	pp. 806-815
Identifier:	10.1109/COMPSAC.2017.31
Additional Information:	© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Subjects:	Computing
Depositing User:	WEI JIE
Date Deposited:	08 May 2017 07:59
Last Modified:	04 Nov 2024 12:35
URI:	https://repository.uwl.ac.uk/id/eprint/3308

Downloads

Actions (login required)

View Item