Uncovering the Largest Community in Social Networks at Scale
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.
Cite
Text
Matsugu et al. "Uncovering the Largest Community in Social Networks at Scale." International Joint Conference on Artificial Intelligence, 2023. doi:10.24963/IJCAI.2023/250Markdown
[Matsugu et al. "Uncovering the Largest Community in Social Networks at Scale." International Joint Conference on Artificial Intelligence, 2023.](https://mlanthology.org/ijcai/2023/matsugu2023ijcai-uncovering/) doi:10.24963/IJCAI.2023/250BibTeX
@inproceedings{matsugu2023ijcai-uncovering,
title = {{Uncovering the Largest Community in Social Networks at Scale}},
author = {Matsugu, Shohei and Fujiwara, Yasuhiro and Shiokawa, Hiroaki},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2023},
pages = {2251-2260},
doi = {10.24963/IJCAI.2023/250},
url = {https://mlanthology.org/ijcai/2023/matsugu2023ijcai-uncovering/}
}