Uncovering the Largest Community in Social Networks at Scale
Uncovering the Largest Community in Social Networks at Scale
复制标题
DOI：
10.24963/ijcai.2023/250
复制
发表时间：
2023-08
期刊：
影响因子：
--
通讯作者：
Shohei Matsugu;Yasuhiro Fujiwara;Hiroaki Shiokawa
中科院分区：
文献类型：
--
作者：
Shohei Matsugu;Yasuhiro Fujiwara;Hiroaki Shiokawa
最大k-Plex搜索（MPS）可以找到最大的k-plex，这是最大团的推广。虽然MPS通常用于人工智能中，以有效地发现社交网络的真实社区，但现有的MPS算法存在高计算成本，因为它们迭代扫描许多节点以找到最大的k-丛。在这里，我们提出了一个高效的MPS算法称为分支合并（BnM），它输出一个确切的最大k-plex。BnM合并不必要的节点，以探索比原始图更小的图。对真实世界社交网络的广泛评估表明，BnM在运行时间方面明显优于其他最先进的MPS算法。
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.