A one-stage memetic algorithm for jointly detecting hierarchical and overlapping community structures in dynamic social networks

Chun Cheng Lin, Hui Hsin Chin*, Zhen Yin Annie Chen, Jung Chao Wu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Social network characterizes complex relationship among individuals, which further constitute numerous various communities based on some attributes. Furthermore, multiple communities may be of a hierarchical structure, and parts of them are overlapped with each other. Additionally, as time goes by, some individuals or relations in social networks may change, so that it has been challenging to detect hierarchical and overlapping community structures in dynamical social networks. Most previous methods were based on a two-stage strategy, which firstly determines a hierarchical structure for the concerned social network, and then detects overlapping communities at each hierarchical level. However, the detection in the second stage is often restricted to the hierarchical structure determined in the first stage. As a result, this work proposes a one-stage memetic algorithm (MA) for jointly detecting hierarchical and overlapping community structures in dynamic social networks, in which a number of quality evaluation functions and constraints of community capacity as well as number of hierarchical levels are considered to enhance quality of detection. The proposed MA improves the genetic algorithm with local search and immigrant schemes. By simulation, in comparison to previous methods, the proposed MA is shown to have better quality. By visual analysis, the detected community structures look more correctly and can be explained more reasonably. Furthermore, dynamic community structures in different scenarios are analyzed in detail.

Original languageEnglish
JournalWireless Networks
DOIs
StateAccepted/In press - 2023

Keywords

  • Dynamic social network
  • Hierarchical and overlapping community structure
  • Memetic algorithm
  • Social network

Fingerprint

Dive into the research topics of 'A one-stage memetic algorithm for jointly detecting hierarchical and overlapping community structures in dynamic social networks'. Together they form a unique fingerprint.

Cite this