论文标题
使用快速低核电性半决赛编程的社区检测
Community detection using fast low-cardinality semidefinite programming
论文作者
论文摘要
模块化最大化一直是理解网络社区结构的基本工具，但是潜在的优化问题是可以解决的NONCEVEX和NP-HARD。 Louvain或Leiden方法之类的最先进的算法集中于不同的启发式方法，以帮助逃避本地Optima，但它们仍然取决于贪婪的步骤，该步骤在本地移动节点分配，并且容易被困。在本文中，我们提出了一种新的低心电图算法，该算法概括了局部更新，以最大程度地提高源自Max-k-Cut的半决赛放松。该提出的算法是可扩展的，从经验上可以实现针对小病例的全局半菲尼特最优性，并且在现实世界数据集中胜过最先进的算法，而额外的时间成本很少。从算法的角度来看，当解决方案稀疏而不是低级时，它也开辟了一种新的途径，用于扩展半决赛编程。
Modularity maximization has been a fundamental tool for understanding the community structure of a network, but the underlying optimization problem is nonconvex and NP-hard to solve. State-of-the-art algorithms like the Louvain or Leiden methods focus on different heuristics to help escape local optima, but they still depend on a greedy step that moves node assignment locally and is prone to getting trapped. In this paper, we propose a new class of low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from max-k-cut. This proposed algorithm is scalable, empirically achieves the global semidefinite optimality for small cases, and outperforms the state-of-the-art algorithms in real-world datasets with little additional time cost. From the algorithmic perspective, it also opens a new avenue for scaling-up semidefinite programming when the solutions are sparse instead of low-rank.
