KDD 2017 Research Paper                  KDD’17, August 13–17, 2017,Halifax, NS, Canada

Local Higher-Order Graph Clustering

局部高阶图聚类

Hao Yin  Stanford University  [email protected]

AustinR. Benson  Stanford University  [email protected]

JureLeskovec  Stanford University  [email protected]

David F.Gleich  Purdue University  [email protected]

 

本文讲了什么问题？

图形聚类的目的是找到将图中节点紧密联系起来的聚集，而现在使用的方法大多是以全局聚类为主并且按照图中的边来进行聚类。

但本文讲了局部高阶图聚类的方法。局部图聚类方法旨在通过探索图的一个小区域来找到一簇节点；这些方法先进在可以围绕给定的种子节点进行定向聚类并且比传统的全局图聚类方法更快，因为它们的运行时间不依赖于输入图形的大小。然而，目前的局部图分区方法并不是为了解释网络中至关重要的高阶结构而设计的，它们也不能有效的处理定向网络。本文引入了一类新的局部图聚类方法，这些方法通过融入更高阶的网络信息来解决上述问题。

 

解决问题方法

本文开发了Motif-basedApproximate Personalized PageRank(MAPPR) algorithm，即基于motif的近似个性化PageRank（MAPPR）算法，此算法大致过程如下：给定一个图G和motif M,该算法旨在找到一组具有良好的motif conductance (对于M)的节点S（例如种子节点）。本文还开发了一个节点邻域的理论用于发现包含小的motif conductance的集合，并应用这些集合结果找到良好的种子节点作为MAPPR算法输入使用。下图1描绘了motif conductance的概念。

如下图所示，原先是靠边聚类，现在换成了靠三角形聚类，conductance也由原先的1/5变成1/11，小的conductance代表好的聚集。本文中定义motif M为任何可以互联的小图（本文中是三角形）

 

 

图1

 

 

 

上图中各变量的描述如下，conductance中的M在此图中是边或三角形。

 

下图是找到聚集S的具体算法：

 

局部聚类在生物信息学中的应用

局部聚类在生物信息学中有广泛应用，例如在分析蛋白质 - 蛋白质相互作用网络时，局部聚类有助于确定蛋白质复合物的其他成员。