Finding a Dense Subgraph with Sparse Cut
Finding a Dense Subgraph with Sparse Cut
复制标题
DOI：
10.1145/3269206.3271720
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Atsushi Miyauchi;Naonori Kakimura
中科院分区：
文献类型：
--
作者：
Atsushi Miyauchi;Naonori Kakimura
社区发现是图挖掘的基本任务之一，在不同的领域有着广泛的应用。在这项研究中，我们提出了一个优化模型，找到一个社区，是密集的内部连接，但稀疏连接到图的其余部分。该模型扩展了密度子图问题，在该问题中，我们最大化密度，同时最小化平均切割尺寸。我们首先证明了我们提出的模型可以有效地解决。然后分别设计了基于线性规划的多项式时间精确算法和最大流算法。此外，为了在实践中处理更大尺寸的图，我们提出了一个可扩展的贪婪算法，运行在几乎线性的时间与理论性能保证的输出。此外，由于我们的模型是密切相关的质量函数称为模块密度，我们表明，我们的算法也可以用来找到全球社区结构图。通过使用众所周知的真实世界的图进行彻底的实验，我们证明了我们的算法在图中找到合适的社区是非常有效的。例如，对于网络谷歌，我们的算法找到了一个解决方案，超过99.1%的密度和小于3.1%的切割尺寸，与基线算法获得的解决方案相比，dennial子图的问题。
Community detection is one of the fundamental tasks in graph mining, which has many real-world applications in diverse domains. In this study, we propose an optimization model for finding a community that is densely connected internally but sparsely connected to the rest of the graph. The model extends the densest subgraph problem, in which we maximize the density while minimizing the average cut size. We first show that our proposed model can be solved efficiently. Then we design two polynomial-time exact algorithms based on linear programming and a maximum flow algorithm, respectively. Moreover, to deal with larger-sized graphs in practice, we present a scalable greedy algorithm that runs in almost linear time with theoretical performance guarantee of the output. In addition, as our model is closely related to a quality function called the modularity density, we show that our algorithms can also be used to find global community structure in a graph. With thorough experiments using well-known real-world graphs, we demonstrate that our algorithms are highly effective in finding a suitable community in a graph. For example, for web-Google, our algorithm finds a solution with more than 99.1% density and less than 3.1% cut size, compared with a solution obtained by a baseline algorithm for the densest subgraph problem.