Robust Densest Subgraph Discovery
Robust Densest Subgraph Discovery
复制标题
DOI：
10.1109/icdm.2018.00157
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Atsushi Miyauchi;A. Takeda
中科院分区：
文献类型：
--
作者：
Atsushi Miyauchi;A. Takeda
稠密子图发现是图挖掘中的一个重要问题，在不同的领域有着广泛的应用。在密度子图问题中，给定一个具有边权重向量w的无向图G =（V，E），我们的目标是找到一个顶点子集S，使密度最大化，即，w（S）/|S|其中w（S）是S诱导的子图中所有边的权和。虽然稠密子图问题是稠密子图发现中研究最多的优化问题之一，但有一个隐含的强假设;假设所有边的权重都确切地知道为输入。在现实世界的应用中，经常有这样的情况，我们只有不确定的信息的边缘权重。在这项研究中，我们提供了一个框架下的边权重的不确定性稠密子图发现。具体来说，我们解决这样的不确定性问题，使用鲁棒优化理论。首先，我们制定了我们的基本问题，强大的denumbersubgraph问题，并提出了一个简单的算法。然后，我们制定了强大的densoring子图问题与采样预言机模型密集子图发现使用边权重采样预言机，并提出了一个算法具有很强的理论性能保证。使用合成图和流行的现实世界的图的计算实验证明了我们所提出的算法的有效性。
Dense subgraph discovery is an important primitive in graph mining, which has a wide variety of applications in diverse domains. In the densest subgraph problem, given an undirected graph G = (V, E) with an edge-weight vector w, we aim to find a subset of vertices S that maximizes the density, i.e., w(S) / |S|, where w(S) is the sum of the weights of the edges in the subgraph induced by S. Although the densest subgraph problem is one of the most well-studied optimization problems for dense subgraph discovery, there is an implicit strong assumption; it is assumed that the weights of all the edges are known exactly as input. In real-world applications, there are often cases where we have only uncertain information of the edge weights. In this study, we provide a framework for dense subgraph discovery under the uncertainty of edge weights. Specifically, we address such an uncertainty issue using the theory of robust optimization. First, we formulate our fundamental problem, the robust densest subgraph problem, and present a simple algorithm. We then formulate the robust densest subgraph problem with sampling oracle that models dense subgraph discovery using an edge-weight sampling oracle, and present an algorithm with a strong theoretical performance guarantee. Computational experiments using both synthetic graphs and popular real-world graphs demonstrate the effectiveness of our proposed algorithms.