Zhao Chao, Al-Bashabsheh Ali, Chan Chung
Department of Computer Science, City University of Hong Kong, Hong Kong, China.
School of General Engineering, Beihang University, Beijing 100191, China.
Entropy (Basel). 2024 Mar 18;26(3):268. doi: 10.3390/e26030268.
We address the challenge of identifying meaningful communities by proposing a model based on convex game theory and a measure of community strength. Many existing community detection methods fail to provide unique solutions, and it remains unclear how the solutions depend on initial conditions. Our approach identifies strong communities with a hierarchical structure, visualizable as a dendrogram, and computable in polynomial time using submodular function minimization. This framework extends beyond graphs to hypergraphs or even polymatroids. In the case when the model is graphical, a more efficient algorithm based on the max-flow min-cut algorithm can be devised. Though not achieving near-linear time complexity, the pursuit of practical algorithms is an intriguing avenue for future research. Our work serves as the foundation, offering an analytical framework that yields unique solutions with clear operational meaning for the communities identified.
我们通过提出一种基于凸博弈论和社区强度度量的模型，来应对识别有意义社区的挑战。许多现有的社区检测方法无法提供唯一解，而且这些解如何依赖于初始条件仍不明确。我们的方法识别出具有层次结构的强社区，可直观化为树形图，并能使用次模函数最小化在多项式时间内计算得出。该框架不仅适用于图，还可扩展到超图甚至多拟阵。当模型为图形时，可以设计一种基于最大流最小割算法的更高效算法。尽管未达到近线性时间复杂度，但追求实用算法是未来研究的一个有趣方向。我们的工作奠定了基础，提供了一个分析框架，可为所识别的社区产生具有明确操作意义的唯一解。
