Testing Cluster Structure of Graphs
Testing Cluster Structure of Graphs
复制标题
测试图的簇结构
DOI：
10.1145/2746539.2746618
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
C. Sohler
中科院分区：
文献类型：
--
作者：
A. Czumaj;Pan Peng;C. Sohler
我们研究了在有界度模型的属性测试框架中识别图的簇结构的问题。给定参数 ε，如果 d 有界度图可以划分为不超过 k 个部分，则定义为 (k, φ) 可聚类，使得每个部分上导出子图的（内部）电导至少为 φ，并且每个部分的（外部）电导至多为 cd,kε4φ2，其中 cd,k 仅取决于 d,k。我们的主要结果是一个运行时间 ~O(√n ⋅ poly(φ,k,1/ε)) 的次线性算法，该算法以最大度数为 d、参数 k、φ、ε 为界的图作为输入，并且概率至少为 2/3，如果该图是 (k,φ)-可聚类的，则接受该图，如果该图是 ε-远离 (k, φ*)-可聚类的，则拒绝该图（对于 φ* = c'd,kφ2） ε4}/log n，其中 c'd,k 仅取决于 d,k。根据测试图扩展所需查询数量的下限 Ω(√n)（对应于我们问题中的 k=1），我们的算法在多对数因子下是渐近最优的。
We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter ε, a d-bounded degree graph is defined to be (k, φ)-clusterable, if it can be partitioned into no more than k parts, such that the (inner) conductance of the induced subgraph on each part is at least φ and the (outer) conductance of each part is at most cd,kε4φ2, where cd,k depends only on d,k. Our main result is a sublinear algorithm with the running time ~O(√n ⋅ poly(φ,k,1/ε)) that takes as input a graph with maximum degree bounded by d, parameters k, φ, ε, and with probability at least 2/3, accepts the graph if it is (k,φ)-clusterable and rejects the graph if it is ε-far from (k, φ*)-clusterable for φ* = c'd,kφ2 ε4}/log n, where c'd,k depends only on d,k. By the lower bound of Ω(√n) on the number of queries needed for testing graph expansion, which corresponds to k=1 in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.