基于最短路径的随机游走的图聚类算法

牛品菽　徐保民

摘要：现实世界中的许多系统都以网络图形式存在，并且近年来图聚类作为一种重要的分析手段已经得到越来越多的关注。在众多图聚类算法中，谱图聚类算法以其高效性、易于实现以及坚实的理论基础等特性已经得到越来越多的关注。本文提出一种基于最短路径的随机游走的谱图聚类算法。该算法利用基于最短路径的局部随机游走模型将数据点之间的距离转化为随机游走的转移概率，通过随机游走的转移概率构造相似矩阵，最后利用谱方法得到聚类结果。实验结果表明，使用本文所提出的聚类方法可以有效提高聚类效果。

关键字：随机游走；图聚类；最短距离；谱聚类

中图分类号：TP311文献标识码：A文章编号：2095-2163（2015）06-

Abstract：There are many systems exiting in the form of network in the real world. And the graph clustering as an important analysis method has gained more and more attention in recent years. The spectral graph clustering algorithm is more popular because of its high efficiency， easy to implement and solid theory foundation. This paper proposes a Graph Clustering Algorithm based on Random Walk Model of the Shortest Path. This algorithm uses the random walk model based on the shortest path to transfer the distance between two data points to the transition probability， and structures the similarity matrix by the transition probability. Then the paper gets the result by using the spectral clustering algorithm. The experimental results show that using the presented clustering method can effectively improve the clustering effect.

Keywords： Random Walk； Graph Clustering； Shortest Distance； Spectral Clustering

0引言

聚类是最常用的数据分析技术之一，已经被广泛地应用到模式识别、数据挖掘和图像处理等领域。聚类分析是一个将数据样本划分为由相似对象组成的分组的过程。每一个组称为一个簇，每个簇中的数据对象的相似度大，而不同簇中的对象相似度小。从机器学习的角度来看，搜索簇就是一个无监督学习的过程。大数据图有很多内部具有实际意义的数据对象组成，两个数据对象间的相似关系可以转化成图模型。现实世界中的许多系统都是由网络图形来进行表示的，比如Facebook上的朋友关系网、生物上的蛋白质互质网络、科学家合著网络以及网页之间的超链接都是常见的网络图模型。近年来图聚类作为一种重要的分析手段已经得到越来越多的关注。图聚类[1]主要是将图上的节点划分为一些子图，使得这些节点在类内具有较强的连接而类间的连接则相对较弱。图聚类不仅有助于可视化和发现层次结构[2]，还具有实际的意义，比如社区发现[3-4]、孤立点检测[5]等，此外聚类的结果也可以用来构建模块，使得在一些算法中可以降低图或模块的复杂度[6-7]。

谱分析方法已经成功地运用在解决数据聚类和图划分的问题方面。谱聚类是一种基于图论的聚类分析方法，近几年，由于谱聚类的高效性、易于实现以及成熟的理论基础等特性已经得到越来越多的关注，并被广泛应用在图像处理、计算机视觉、数据挖掘、机器学习等领域[8]。其基本思想是通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。关于谱聚类算法已经有很多人做了研究，其中经典的算法有Perona和Freeman提出的PF算法[9]、Shi和Malik提出的SM算法[10]、Ng和Jordan等人提出的NJW算法[11]以及Meila提出的MS算法[12]等。譜聚类克服了传统聚类方法仅在凸球形状数据集上效果很好和会陷入局部最优解的局限性，其在任意形状数据集的聚类效果都比较理想且可以收敛到全局最优解。

本文将提出一个新的高效的基于最短路径的随机游走的图聚类算法（DWSC）。利用基于最短路径的局部随机游走模型将数据点之间的距离转化为随机游走的转移概率，通过随机游走的转移概率构造相似矩阵，最后利用谱方法得到聚类结果。

1相关工作

1.1谱聚类

谱聚类算法的思想来自谱图划分理论，谱聚类将聚类问题转化为一个无向图的多路划分问题。谱方法类属一种基于优化的聚类方法，最早用于解决图分割的问题，谱方法具有坚实的数学理论基础，已发展成一种重要的聚类方法。该方法主要利用图的特征分解和拉普拉斯矩阵进行聚类的。常见的图分割准则有以下几种。

（1）最小割集准则（Minimum-Cut）[13]

给定一个图G，构建其划分的最简单直接的方法是解决最小割问题。定义 ，并且 是A的补集。对于给定的子集数目k，寻找划分 的问题为最小化目标函数：

当k=2时，最小割是一种简单有效的方法。然而，这种方法并不是总能得到一个满意的划分，因为当k的取值不为2时，划分容易发生倾斜，即使得一个单独的顶点从整个图中分离出来。显然这不是研究想要的结果，聚类结果应该是由大量点组成的图。

（2）比例割集准则（Ratio-Cut）[10]

Hagen和Kahng提出了比利割集准则，在该准则中 为第i类的节点个数，其目标函数为：

比例割集准则通过引入类中的节点数作为类平衡的条件，可以避免最小割集引起的划分倾斜问题，但运行速度较慢。

（3）规范割集准则（Normalized-cut）[14]

Shi和Malik根据谱图理论提出了2-way划分的规范割集准则，在该准则中 为第i类中所有顶点的度之和，其目标函数为：

（4）最小最大割集准则（Min-max-cut）[15]

Ding提出了最小最大割集準则，该准则要求在最小化 的同时，最大化 ，其目标函数为：

由于构造相似矩阵的构造函数不同，使用的特征向量矩阵不同以及图划分准则不同等因素，谱图聚类算法也存在着差异。由Perona和Freeman提出的PF算法[9]，是一种简单的谱聚类算法。利用相似矩阵中最大特征值所对应的特征向量进行聚。对于块对角相似矩阵，特征向量中非零元素对应的点为一类，零元素对应的点为另一类。由Shi和Malik提出的SM算法[10]目标函数定义为：

将x松弛到[-1，1]之间，根据Rayleigh熵原理，将最小化目标函数的问题转化为求解 的第二小特征值问题。利用特征值计算相应的Fiedler特征向量，并根据启发式规则在向量中寻找划分点，使得在该点上得到的Ncut（A，B）值最小，将Fiedler向量中大于该点值的归为一类，小于该点值的为另一类。SM算法的效率明显优于PF算法。由Scott等人提出的SLH算法[16]对相似矩阵求其前k个特征值对应的特征向量构造特征向量矩阵V。对V的行向量进行规范化得到 ，若Q（i，j）=1则表示顶点i，j为同一类。KVV[17]算法利用比例分割准则，同SM算法一样利用Fiedler向量寻找划分点。该算法可以有效避免算法的过分倾斜，但是运算速度较慢。由于2-way划分准则包含特征向量比较少，很容易丢失一些有用的信息，且算法不稳定。Ng等人提出一种采用多路划分准则的NJW算法[11]。该算法选取拉普拉斯矩阵的前k最大特征值对应的特征向量构造特征矩阵，将特征矩阵行向量变换为单位向量。矩阵中每一行看作一个数据点并使用k-means算法或其他简单聚类算法进行聚类得到聚类结果。Meila提出了一种基于Markov链的随机游走的聚类算法[12]。该算法利用随机游走构造相似矩阵，并对其求前k个特征值对应的特征向量构造特征向量矩阵。将矩阵中每一行看作一个数据点，在此基础上使用k-means算法或其他简单聚类算法进行聚类得到聚类结果。

1.2基于最短路径的随机游走模型

给定一个无环无向图 ，其中 和 分别表示节点集和边集。在LRW[18]中，游走者从一个节点按照概率 游走到相应的任意一个邻居节点。 代表节点的度。如此可以得到邻接矩阵即一步转移概率矩阵P。 表示从节点 到节点 的概率。如果两节点直接相连则 的值是 ，否则为0。同时，研究还给出 阶向量 。 表示经过 步节点 到节点 的概率。初始转移向量 表示游走者在节点 的初始概率为1。节点间转移概率为

假如让每个节点随机游走的步数就是相互之间的最短距离。即没有必要让整个网络采取统一的最优步数。此时假设 为经过 步节点 到节点 的概率。 为节点 到节点 的最终概率。定义 为节点 和 间的最短距离。显然，当 时， 的值为零，所以节点间首次接触的概率为 。用 去近似 就得到

式（8）则为基于最短路径的局部随机游走模型LDRW[19]。其主要特性是将最短路径引入到随机游走中，并引入基于最短路径的首达概率概念。

1.3基于随机游走的谱聚类

图上的随机游走是从一个顶点跳到另一个顶点的随机过程，因此谱聚类的过程可以解释为试图寻找一个图的划分使得随机游走只发生在类内，而类间的游走则相对较少。Meila提出MS算法[12]用Markov链中的随机游走来解释相似性，通过计算转移概率矩阵 的特征向量，以此构造向量空间进行聚类。其主要步骤为：

（1）根据数据集构造相似矩阵S和对角矩阵D；

（2）计算转移概率矩阵 ；

（3）计算P的前 个特征值对应的特征向量 ，并构造矩阵U；

（4）将矩阵E中的每一行看做 空间中的一个数据点，利用k-means或其他经典聚类算法对其进行聚类，得到结果。

2算法描述

本文提出的基于最短路径的随机游走的图聚类算法（DWSC）通过节点间的最短路径的随机游走构造相似矩阵，利用相似矩阵构造转移概率矩阵并对其进行特征分解，取前k个特征值对应的特征向量，对N*K维的特征向量进行k-means得到聚类结果。

2.1问题定义

本文中，定义无向图 ，其中 是顶点集合， 是图的边集。相似度矩阵Similarity，其中 。对角矩阵Diagonal，其中 。概率矩阵Probability，其中 且对于矩阵Probability的任意i行有 。

2.2实验步骤

输入：无向图 和聚类数目 ；

（1）计算图的顶点间的最短距离，构造距离矩阵distance；

（2）利用LWRD算法计算顶点相似度矩阵Similarity；

（3）计算对角矩阵Diagonal；

（4）计算转移概率矩阵Probability；

（5）对Probability进行特征分解，去前k个特征值对应的特征向量 ；

（6）构造矩阵 ，其中 是 中的第i列；

（7）将Eigen的每一行看做一个顶点 ，对这n个点 进行k-means聚类得到结果 ；

输出：聚类结果 。

3结果与分析

3.1实验数据集

3.1.1 美国大学生足球联盟网络（American College Football）

这个数据集来自UCI Network Data Repository（M. Girvan and M. E. J. Newman 2002）[20]，该网络中共有115个节点，615条边。网络中的每个节点表示一支大学足球队，每条边表示两个球队间进行的一场比赛。根据地理位置，全部的足球队组成了12个联盟，因此也用这12个联盟来作为算法划分的结果，如图1所示。

3.1.2 美國政治书籍网络（Books about US Politics）

这个数据集来自UCI Network Data Repository（Adamic and Glance 2005）[21]，该网络包含105个节点，441条边。每个节点代表一本书籍，每条边代表两本书同时被一个购买者所购买。全本书籍总共被分为3类，如图2所示。

3.2实验结果

3.2.1 对比实验及评价标准

本文采用k-means算法和MS算法作为对比实验，评价标准分别有模块性（Modularity）[22]，Normalized Mutual Information（NMI）[23]，Rand Index。其中NMI和Rand Index指标都是与正确性相关的评价指标，并且都是对两个数据集相似性作对比，这里即是将聚类后的结果与数据集真实的label做对比。模块性也是评价聚类好坏常用的一个指标，一个好的聚类结果应该具有较大的聚类内边数和较小的聚类间边数。

3.2.2 实验结果

实验结果分别如表1和表2所示。由表1和表2可以看出，本文所提出的DWSC算法大大提高了聚类的正确性。

4结束语

本文提出了一个新的基于最短路径的随机游走的图聚类算法，可以很好地应用于图聚类的领域。该算法主要利用最短路径的随机游走构造相似矩阵，基于谱图理论，利用特征向量进行聚类得到结果。最后利用k-means算法和MS算法进行校验，实验表明，通过最短路径的随机游走可以更好地发现网络图中的相似性并有利于发现聚类，同时可以提高聚类的准确性。

参考文献：

[1] SCHAEFFER S E. Graph clustering[J]. Computer Science Review， 2007， 1（1）：27–64.

[2]HERMAN I， MELANCON G， MARSHALL M S. Graph visualization and navigation in information visualization： A survey[J]. Visualization & Computer Graphics IEEE Transactions on， 2000， 6（1）：24-43.

[3] FORTUNATO S. Community detection in graphs[J]. Physics Reports， 2009， 486（3-5）：75-174.

[4] WHITE S， SMYTH P. A spectral clustering approach to finding communities in graph[C]// Siam International Conference on Data Mining，Newport Beach， CA， USA： .[s.n.]，2005：76-84.

[5] GUPTA M， GAO J， SUN Y， et al. Integrating community matching and outlier detection for mining evolutionary community outliers[J]. Kdd， 2012：859--867.

[6] SONG Y， ZHUANG Z， LI H， et al. Real-time automatic tag recommendation[C]// Proc. of the 31st Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval （SIGIR）， New York， NY， USA： ACM，2008：515–522.

[7] DALVI B B， KSHIRSAGAR M， SUDARSHAN S. Keyword search on external memory data graphs.[J]. Keyword search on external memory data graphs. - ResearchGate， 2008， 1（1）：1189-1204.

[8] LUXBURG U V. A tutorial on spectral clustering[J]. Statistics & Computing， 2007， 17（4）：395-416.

[9]Perona P， Freeman W. A factorization approach to grouping[M]//

H Burkhardt，B Neumann. Computer Vision — ECCV'98.Berlin Heidelberg： Springer， 1998：655-670.

[10] SHI J， MALIK J. Normalized cuts and image segmentation[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on， 2000， 22（8）：888-905.

[11] NG A Y， JORDAN M I， WEISS Y. On spectral clustering： Analysis and an algorithm[J]. Advances in Neural Information Processing Systems， 2002， 14：849-856.

[12] MEILA M， SHI J. Learning segmentation by random walks[C]. NIPS， Den，Co，USA：MIT Press，2000：873-879.

[13]WU Z， LEAHY R. An optimal graph theoretic approach to data clustering： theory and its application to image segmentation [J]. IEEE Transactions on PAMI，1993，15（11）：1101-1113.

[14] WANG S， SISKIND J M. Image segmentation with ratio cut [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2003，25（6）：675-690.

[15] DING C H Q， HE X， ZHA H， et al. A Min-max Cut Algorithm for Graph Partitioning and Data Clustering[C]// 2013 IEEE 13th International Conference on Data Mining. Dallas， TX， USA： IEEE Computer Society， 2001：107.

[16] SCOTT G L， LONGUET H C. Feature grouping by "relocalisation " of eigenvectors of the proximity matrix[C]// Proceedings of the British Machine Vision Conference， Oxford UK：BMVA Press， 1990：103--108.

[17] KANNAN R， VEMPALA S， VETA A. On clusterings-good， bad and spectral[C]// 2013 IEEE 54th Annual Symposium on Foundations of Computer Science， [s.l.]： IEEE Computer Society， 2000：367-367.

[18] LüLinyuan ， ZHOU A T. Link prediction in weighted networks： The role of weak ties[J]. Epl， 2010， 89（1）：18001.

[19] BAOMIN XU， TINGLIN XIN， YUNFENG WANG， et al. Local Random Walk with Distance Measure[J]. Modern Physics Letters B， 2013， 27（8）：269-275.

[20] GIRVAN M， NEWMAN ME J. Community structure in social and biological networks[J]. ProcNatl. Acad. Sci. USA 99， 2002， 99（12）：7821-7826.

[21]ADAMIC L A， GLANCE N. The political blogosphere and the 2004 U.S. Election： Divided They Blog[C]// Proceedings of the 3rd international workshop on Link discovery，New York， NY， USA： ACM， 2005：36--43.

[22]NEWMAN M E， GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2004， 69（2Pt2）：026113-026113.

[23]RAND W M. Objective criteria for the evaluation of clustering methods[J]. Journal of the American Statistical Association， 1971， 66（336）：846-850.