测试图的簇结构

《ACM Transactions on Algorithms》：Testing Cluster Structure of Graphs

本研究在性质测试框架下，针对有界度图提出了一种亚线性时间算法，用于识别满足特定导纳条件的k-φ-in/φ-out-聚类可分图，并证明该算法在k=1时接近最优，时间复杂度为O(dk√n·poly(φ,1/ε))。

　　

摘要

我们研究了在有界度模型下，通过属性测试框架来识别图的谱簇结构的问题。一个图被称为$(k,{?}_{\text{in}},{?}_{\text{out}})$-可聚类的，如果它可以被划分为不超过$k$个部分，使得每个部分上诱导子图的（内部）电导至少为${?}_{\text{in}}$，而每个部分的（外部）电导最多为${?}_{\text{out}}$。我们的主要结果是一个亚线性算法，其运行时间为。该算法的输入是一个最大度被限制为$d$的顶点图，参数包括$k$、$?$和$\epsilon$，并且至少以$\frac{2}{}$的概率接受该图：如果该图是可聚类的；如果该图不是$\epsilon$可聚类的，或者与