A maximal clique based multiobjective evolutionary algorithm for overlapping community detection

Xuyun Wen, Wei Neng Chen, Ying Lin, Tianlong Gu, Huaxiang Zhang, Yun Li, Yilong Yin, Jun Zhang

Research output: Contribution to journalArticle

46 Citations (Scopus)

Abstract

Detecting community structure has become one important technique for studying complex networks. Although many community detection algorithms have been proposed, most of them focus on separated communities, where each node can belong to only one community. However, in many realworld networks, communities are often overlapped with each other. Developing overlapping community detection algorithms thus becomes necessary. Along this avenue, this paper proposes a maximal clique based multiobjective evolutionary algorithm (MOEA) for overlapping community detection. In this algorithm, a new representation scheme based on the introduced maximal-clique graph is presented. Since the maximalclique graph is defined by using a set of maximal cliques of original graph as nodes and two maximal cliques are allowed to share the same nodes of the original graph, overlap is an intrinsic property of the maximal-clique graph. Attributing to this property, the new representation scheme allows MOEAs to handle the overlapping community detection problem in a way similar to that of the separated community detection, such that the optimization problems are simplified. As a result, the proposed algorithm could detect overlapping community structure with higher partition accuracy and lower computational cost when compared with the existing ones. The experiments on both synthetic and real-world networks validate the effectiveness and efficiency of the proposed algorithm.

LanguageEnglish
Article number7558207
Pages363-377
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Volume21
Issue number3
Early online date1 Sep 2016
DOIs
Publication statusPublished - 1 Jun 2017

Fingerprint

Maximal Clique
Community Detection
Multi-objective Evolutionary Algorithm
Evolutionary algorithms
Overlapping
Clique Graphs
Community Structure
Graph in graph theory
Vertex of a graph
Complex networks
Complex Networks
Computational Cost
Overlap
Partition
Optimization Problem
Necessary
Experiment
Community
Costs
Experiments

Keywords

  • clique-based representation
  • maximal-clique graph
  • multiobjective evolutionary algorithm (MOEA)
  • overlapping community detection

Cite this

Wen, Xuyun ; Chen, Wei Neng ; Lin, Ying ; Gu, Tianlong ; Zhang, Huaxiang ; Li, Yun ; Yin, Yilong ; Zhang, Jun. / A maximal clique based multiobjective evolutionary algorithm for overlapping community detection. In: IEEE Transactions on Evolutionary Computation. 2017 ; Vol. 21, No. 3. pp. 363-377.
@article{bc0faa624bff4ac9b30f8b51ba0a7796,
title = "A maximal clique based multiobjective evolutionary algorithm for overlapping community detection",
abstract = "Detecting community structure has become one important technique for studying complex networks. Although many community detection algorithms have been proposed, most of them focus on separated communities, where each node can belong to only one community. However, in many realworld networks, communities are often overlapped with each other. Developing overlapping community detection algorithms thus becomes necessary. Along this avenue, this paper proposes a maximal clique based multiobjective evolutionary algorithm (MOEA) for overlapping community detection. In this algorithm, a new representation scheme based on the introduced maximal-clique graph is presented. Since the maximalclique graph is defined by using a set of maximal cliques of original graph as nodes and two maximal cliques are allowed to share the same nodes of the original graph, overlap is an intrinsic property of the maximal-clique graph. Attributing to this property, the new representation scheme allows MOEAs to handle the overlapping community detection problem in a way similar to that of the separated community detection, such that the optimization problems are simplified. As a result, the proposed algorithm could detect overlapping community structure with higher partition accuracy and lower computational cost when compared with the existing ones. The experiments on both synthetic and real-world networks validate the effectiveness and efficiency of the proposed algorithm.",
keywords = "clique-based representation, maximal-clique graph, multiobjective evolutionary algorithm (MOEA), overlapping community detection",
author = "Xuyun Wen and Chen, {Wei Neng} and Ying Lin and Tianlong Gu and Huaxiang Zhang and Yun Li and Yilong Yin and Jun Zhang",
year = "2017",
month = "6",
day = "1",
doi = "10.1109/TEVC.2016.2605501",
language = "English",
volume = "21",
pages = "363--377",
journal = "IEEE Transactions on Evolutionary Computation",
issn = "1089-778X",
number = "3",

}

A maximal clique based multiobjective evolutionary algorithm for overlapping community detection. / Wen, Xuyun; Chen, Wei Neng; Lin, Ying; Gu, Tianlong; Zhang, Huaxiang; Li, Yun; Yin, Yilong; Zhang, Jun.

In: IEEE Transactions on Evolutionary Computation, Vol. 21, No. 3, 7558207, 01.06.2017, p. 363-377.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A maximal clique based multiobjective evolutionary algorithm for overlapping community detection

AU - Wen, Xuyun

AU - Chen, Wei Neng

AU - Lin, Ying

AU - Gu, Tianlong

AU - Zhang, Huaxiang

AU - Li, Yun

AU - Yin, Yilong

AU - Zhang, Jun

PY - 2017/6/1

Y1 - 2017/6/1

N2 - Detecting community structure has become one important technique for studying complex networks. Although many community detection algorithms have been proposed, most of them focus on separated communities, where each node can belong to only one community. However, in many realworld networks, communities are often overlapped with each other. Developing overlapping community detection algorithms thus becomes necessary. Along this avenue, this paper proposes a maximal clique based multiobjective evolutionary algorithm (MOEA) for overlapping community detection. In this algorithm, a new representation scheme based on the introduced maximal-clique graph is presented. Since the maximalclique graph is defined by using a set of maximal cliques of original graph as nodes and two maximal cliques are allowed to share the same nodes of the original graph, overlap is an intrinsic property of the maximal-clique graph. Attributing to this property, the new representation scheme allows MOEAs to handle the overlapping community detection problem in a way similar to that of the separated community detection, such that the optimization problems are simplified. As a result, the proposed algorithm could detect overlapping community structure with higher partition accuracy and lower computational cost when compared with the existing ones. The experiments on both synthetic and real-world networks validate the effectiveness and efficiency of the proposed algorithm.

AB - Detecting community structure has become one important technique for studying complex networks. Although many community detection algorithms have been proposed, most of them focus on separated communities, where each node can belong to only one community. However, in many realworld networks, communities are often overlapped with each other. Developing overlapping community detection algorithms thus becomes necessary. Along this avenue, this paper proposes a maximal clique based multiobjective evolutionary algorithm (MOEA) for overlapping community detection. In this algorithm, a new representation scheme based on the introduced maximal-clique graph is presented. Since the maximalclique graph is defined by using a set of maximal cliques of original graph as nodes and two maximal cliques are allowed to share the same nodes of the original graph, overlap is an intrinsic property of the maximal-clique graph. Attributing to this property, the new representation scheme allows MOEAs to handle the overlapping community detection problem in a way similar to that of the separated community detection, such that the optimization problems are simplified. As a result, the proposed algorithm could detect overlapping community structure with higher partition accuracy and lower computational cost when compared with the existing ones. The experiments on both synthetic and real-world networks validate the effectiveness and efficiency of the proposed algorithm.

KW - clique-based representation

KW - maximal-clique graph

KW - multiobjective evolutionary algorithm (MOEA)

KW - overlapping community detection

UR - http://www.scopus.com/inward/record.url?scp=85021762386&partnerID=8YFLogxK

U2 - 10.1109/TEVC.2016.2605501

DO - 10.1109/TEVC.2016.2605501

M3 - Article

VL - 21

SP - 363

EP - 377

JO - IEEE Transactions on Evolutionary Computation

T2 - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

SN - 1089-778X

IS - 3

M1 - 7558207

ER -