Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs
Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs
复制标题
鲁棒聚类预言机和图聚类结构的局部重构器
DOI：
10.1137/1.9781611975994.179
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Pan Peng
中科院分区：
文献类型：
--
作者：
Pan Peng
由于现代网络数据的巨大规模，用于分析图的簇结构的在次线性时间内运行的局部算法受到越来越多的关注。两个典型的例子是局部图聚类算法，它从种子节点中找到一个簇，运行时间与输出集的大小成正比，以及可聚类性测试算法，它决定一个图是否可以在属性测试的框架中划分为几个簇。
在这项工作中，我们开发了次线性时间算法分析图的聚类结构与噪声部分信息。通过使用电导为基础的定义来衡量质量的集群和集群结构，我们正式定义的噪声聚类图有界的最大程度。该算法被赋予查询访问这样的图的邻接表。然后，我们形式化了噪声可聚类图的鲁棒聚类预言机的概念，并给出了一个在次线性时间内构建这种预言机的算法，该算法可以进一步用于支持典型查询（例如，IsOutlier（$s$），SameCluster（$s，t$））表示图在次线性时间内的簇结构。所有的答案都与G的一个划分相一致，其中除了一小部分顶点之外，所有的顶点都属于某个好的簇。我们还给出了一个本地重建的嘈杂的可聚类图，提供查询访问重建的图，保证是可聚类的次线性时间。所有的查询答案都与一个可聚类图一致，该可聚类图保证接近原始图。
Due to the massive size of modern network data, local algorithms that run in sublinear time for analyzing the cluster structure of the graph are receiving growing interest. Two typical examples are local graph clustering algorithms that find a cluster from a seed node with running time proportional to the size of the output set, and clusterability testing algorithms that decide if a graph can be partitioned into a few clusters in the framework of property testing.
In this work, we develop sublinear time algorithms for analyzing the cluster structure of graphs with noisy partial information. By using conductance based definitions for measuring the quality of clusters and the cluster structure, we formalize a definition of noisy clusterable graphs with bounded maximum degree. The algorithm is given query access to the adjacency list to such a graph. We then formalize the notion of robust clustering oracle for a noisy clusterable graph, and give an algorithm that builds such an oracle in sublinear time, which can be further used to support typical queries (e.g., IsOutlier($s$), SameCluster($s,t$)) regarding the cluster structure of the graph in sublinear time. All the answers are consistent with a partition of $G$ in which all but a small fraction of vertices belong to some good cluster. We also give a local reconstructor for a noisy clusterable graph that provides query access to a reconstructed graph that is guaranteed to be clusterable in sublinear time. All the query answers are consistent with a clusterable graph which is guaranteed to be close to the original graph.
普通树木着色的芒硝动力学混合时间
影响因子：
1
作者：
Goldberg L
通讯作者：
Goldberg L