Uncovering the Largest Community in Social Networks at Scale

Shohei Matsugu; Yasuhiro Fujiwara; Hiroaki Shiokawa

IJCAI 2023poster9 citations

Uncovering the Largest Community in Social Networks at Scale

Shohei Matsugu, Yasuhiro Fujiwara, Hiroaki Shiokawa

Abstract

The Maximum k-Plex Search (MPS) can find the largest k-plex, which is a generalization of the largest clique. Although MPS is commonly used in AI to effectively discover real-world communities of social networks, existing MPS algorithms suffer from high computational costs because they iteratively scan numerous nodes to find the largest k-plex. Here, we present an efficient MPS algorithm called Branch-and-Merge (BnM), which outputs an exact maximum k-plex. BnM merges unnecessary nodes to explore a smaller graph than the original one. Extensive evaluations on real-world social networks demonstrate that BnM significantly outperforms other state-of-the-art MPS algorithms in terms of running time.

Data Mining: DM: Mining text, web, social mediaData Mining: DM: Applications

BibTeX

@inproceedings{ijcai2023p250,
  title     = {Uncovering the Largest Community in Social Networks at Scale},
  author    = {Matsugu, Shohei and Fujiwara, Yasuhiro and Shiokawa, Hiroaki},
  booktitle = {Proceedings of the Thirty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-23}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Edith Elkind},
  pages     = {2251--2260},
  year      = {2023},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2023/250},
  url       = {https://doi.org/10.24963/ijcai.2023/250},
}