最短路径的教学

最短路径的教学（共4篇）

最短路径的教学 篇1

0. 前言

《数据结构》课程是计算机类信息类专业的基础核心课程, 这门课程掌握的程度影响到其它后续课程的学习, 相关知识也会应用在实际的软件开发中。大多数院校在低年级开设这门课程, 低年级的学生一般只学过一门高级程序设计语言, 如C语言, 对面向对象程序设计、面向对象编程思想、抽象类型、数学模型、解决实际问题的算法了解甚少。笔者长期从事《数据结构》课程的教学, 对这门课程的教学有一套自己的方法。本文以最短路径的教学为例, 论述了《数据结构》中抽象类型--图的教学思路。

1. 问题的提出

随着生活水平的提高, 汽车已经进入千家万户, 工薪阶层拥有汽车已经成为可能。假期上班族开着自己的汽车到外地旅游已经成为一种时尚。在旅游的过程中, 如何缩短路程减少费用, 成了人们关心的问题。如, 旅客要自己开车从福州到乌鲁木齐, 怎样选择线路, 才能使路径的总和最短, 从而费用总和最少。

2. 数学模型

在上面的问题中, 可以把城市看成顶点, 城市之间若有路可到达的话, 在城市对应的顶点之间加上一条边, 在边上加上权值表示两个城市之间的距离, 这样可以构成一个图 (我们称为无向网络) 。在构造无向网络的过程中, 只要考虑感兴趣的城市 (也就是说只要把感兴趣城市对应的顶点加入到无向网络中) , 同样道理, 也只要把感兴趣的线路加入到无向网络中。

3. 存储结构

G.kind存储的值有四种DG, DN, UDG, UDN。DG表示有向图, DN表示有向网络, UDG表示无向图, UDN表示无向网络。G.vertexnum存储的值表示顶点的个数 (或者说是城市的个数) 。G.edgenum存储的值表示边的条数 (或者说是线路的条数) 。G.edges[j][k]存储的值表示两个城市之间的距离。G.vertexs[i]存储的值是城市的名称。

最终, D[j][k]存放从第j个顶点到第k个顶点的最短距离, P[j][k][t]存放从第j个顶点到第k个顶点的最短路径上的顶点的下标, N[j][k]存放从第j个顶点到第k个顶点的最短路径上的顶点的个数。

4. 实现算法

5. 问题的解决

调试过程如下 (带下划线的字符为从键盘输入的数据) :

要创建图, 请输入图的类型,

0表示有向图 (DG) , 1表示有向网络 (DN) , 2表示无向图 (UDG) , 3表示无向网络 (UDN) :3

要创建无向网络 (UDN) , 请输入顶点的数目:25

要创建无向网络 (UDN) , 请输入边的数目:30

要创建无向网络 (UDN) , 请输入25个顶点:

福州南昌上海徐州天津大连沈阳长春哈尔滨北京郑州武汉株州广州深圳南宁柳州贵阳昆明成都西安呼和浩特兰州西宁乌鲁木齐 (回车)

要创建无向网络 (UDN) , 请输入25*25的矩阵, 有边用权值, 无边用0:

请输入起点城市:

请输入终点城市:

从福州到乌鲁木齐的最短路径为:福州---南昌---株州---武汉---郑州---西安---兰州---乌鲁木齐 (5011)

继续吗?请输入 (Y或y表示继续, N或n表示终止) :

请输入起点城市:

请输入终点城市:

从南宁到乌鲁木齐的最短路径为:南宁---柳州---株州---武汉---郑州---西安---兰州---乌鲁木齐 (4949)

继续吗?请输入 (Y或y表示继续, N或n表示终止) :

摘要：本文论述了《数据结构》图论部分最短路径这一小节教学过程当中的一些体会。从实际问题出发, 提出相关的数学模型, 建立相应的存储结构, 在建立的结构上编写算法, 从而达到解决实际问题。

关键词：数据结构,抽象类型,最短路径,教学方法

参考文献

[1]《数据结构 (C语言版) 》, 严蔚敏吴伟民编著, 清华大学出版社, 1997.4

[2]《C程序设计 (第三版) 》, 谭浩强著, 清华大学出版社, 2005.7

几种最短路径的算法及比较 篇2

为了方便我们对最短路径问题的研究, 下面给出其定义。

定义:在最短路径问题中, 给出的是一张有向加权图G= (V, E) , 在其上定义的加权函数w:E→R为边到实型权值的映射。路径p= (v0, v1, …vk) 的权指的是其组成边的所有权值之和:

定义从u到v的最短路径的权为:

2. 单源最短路径算法

单源最短路径问题所求的是:从某结点s到其它所有结点的最短路径。这是最短路径问题的基础问题, 其它的最短路径问题都可以转化为单源最短路径问题进行求解。

2.1 松弛技术 (Relax) [1]

在每个单源最短路径算法中都运用了松弛技术。松弛一条边就是试图找到一条比当前已知路径更短的边。对每一结点v∈S, 我们用d[v]来表示从源s到v当前已知的最短路径的权的上界, 称之为最短路径估计。用pre[v]来表示当前最短路径估计中v前面的点。

松弛一条边 (u, v) 的过程包括测试我们是否可能通过结点u对迄今找出的到v的最短路径估计进行改进, 如果可能则更新d[v]和pre[v]。

注意:单源最短路径的每个算法都要先调用初始化过程, 然后重复松弛过程。

2.2 Dijkstra算法[2]

Dijkstra算法解决了有向加权图的最短路径问题, 它可以解决单源最短路径问题, 如果以每个点作为源都做一次Dijkstra算法, 则可以求出每对结点间的最短路径。该算法的条件是所有边的权值都非负, 这个重要的条件使得我们用贪心得到该算法。

2.2.1 算法描述

设置一结点集合S, 从源s到集合S中所有点的最短路径均已求出。算法反复挑选出最短路径估计为最小的结点u加入S集合, 并对所有离开结点u的边进行松弛操作, 直到所有结点进入集合。

2.2.2 算法分析

这里的D要用优先队列实现, 需用到删除最小 (Delete Min) 与减值 (Decrease Key) 的操作。假设用普通的队列实现则算法复杂度为O (V2) 。如果用Fibonacci堆来实现优先队列则算法复杂度为O (|E|+|V|lg|V|) 。

2.3 Bell Man-Ford算法[3]

如果一个图包含负权圈, 那么这个图就不存在最短路径。在Dijkstra算法中我们假定不存在负权边, 而在Bellman-Ford算法中则可以存在负权边:找到从源s到所有点的最短路径或确定存在负权圈。

2.3.1 算法描述

对于每一结点s∈S, 逐步减小从源s到v的最短路径估计d[v]直至其到达实际最短路径的权。最多进行|V[G]|-1次松弛操作。算法返回True当且仅当图中不存在负权圈。

2.3.2 算法分析

该算法的时间复杂度为O (VE) 。

2.3.3 算法优化

该算法名为Shortest path faster algorithm4, SPFA其实就是Bellman-Ford的一种队列实现, 减少了冗余, 即松驰的边至少不会以一个d为∞的点为起点。

2.3.4 复杂度分析

SPFA在形式上和宽度优先搜索非常类似, 不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列, 但是SPFA中一个点可能在出队列之后再次被放入队列, 也就是一个点改进过其它的点之后, 过了一段时间可能本身被改进, 于是再次用来改进其它的点, 这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k, 有办法证明对于通常的 (不含负圈, 较稀疏) 情况, k在2左右。算法复杂度理论上同Bellman-Ford, O (VE) , 但实际上却是O (k E) 。

4. 每对结点间的最短路径算法

最直接的方法是把每个结点都作为源做一次单源最短路径算法, 我们用Floyd-Warshall算法来解决这类问题。Floyd算法是一种用来解决关于图G (V, E) 间每对结点间的最短路径问题的算法, 可以存在负权边, 但我们假定不存在负权圈。

4.1 算法描述

本质就是用动态规划:

Gk (u, v) 表示u到v的不经过k, k+1, ..., n结点 (除u, v外) 时, 从u到v的最短路长。下面用归纳法证明:

k=1显然成立。

假设对k成立, 下面考虑k+1的情况;

从u到v且不通过k+1, ..., n

节点的最短路有两种可能: (1) 不经过k节点, 即为Gk (u, v) ; (2) 经过k节点, 即为Gk (u, k) +Gk (K, v)

由于第k+1次迭代过程中, 不会影响k次的迭代结果, 使用O (V2) 的空间即可。二维数组pre (u, v) , 记录u到v, 最后经过哪个k的迭代。

4.2 算法分析

时间复杂度为O (V3) , 空间复杂度为O (V2) 。

5. Johnson算法

5.1 算法描述

本算法适用于稀疏图。它是Dijkstra和Bellman-Ford算法的综合应用。

本算法用了权值改造 (reweighting) 技术。若图的权值非负, 则对于每个结点用一次Dijkstra算法, 就可以求出所有顶点对间最短路。若图中有负权, 但没有负圈, 则可以把权值W改造成W', W'非负, 使得能够使用Dijkstra算法。

(1) 给图G, 加一个新结点v0。对v0用Bellman-Ford, 若有负, 则结束;否则可以得到h (v) , 即v到v的最短路长。O (VE)

(2) 对于所有边 (u, v) , 权值改造, 即令w' (u, v) =w (u, v) +h (u) -h (v) 。O (m)

(3) 对于每个结点, 用一次以Fibonacci Heap为优先队列的Dijkstra算法, 可求出v与其他顶点的最短路。O (Vlog V+E) *O (V)

权值改造满足两个原则: (1) W'非负; (2) 对于任意顶点u, v, p是在W上的u到v的最短路当且仅当p是在W'上的u到v的最短路。下证w' (u, v) =w (u, v) +h (u) -h (v) , 满足以上两个原则:

(1) 由于h是v0到v的最短路长, h (u) +w (u, v) ≥h (v) , 所以w' (u, v) =w (u, v) +h (u) -h (v) ≥0。

(2) 令路径p= (v1, v2, L, vn) , 则

w' (p) 只与w (p) 以及首尾的标号h有关, 不影响w' (p) 的决策。所w (p) 是最短路长当且仅当w' (p) 是最短路长, 且不影响最短路p。

6.结论

在单源最短路径问题中, Dijkstra算法适合于处理权值都为正的图, 而Bellman则适用于含有负权的图, 并且可以处理负权圈。改进后的SPFA是最快的。

在有向无环图中有特殊的算法, 可以在的时间内实现。

在所有点之间的最短路径问题中, 我们可以多次运行SPFA算法。但在完全图中Floyd算法则更为优秀, 并且实现简单。

摘要：最短路径问题是图论中一个非常有实际意义的问题, 在实际生活中的各种规划设计问题中及数据挖掘中都有重要的作用。本文着重介绍了用计算机编程语言实现单源最短路径算法与每对结点间的最短路径算法, 并作了简单比较。

关键词：Relax,Dijkstra,Bellman,有向无环图上的最短路,Floyd-Warshall,Johnson

参考文献

[1].Herbert S.Wilf.Algorithms and Complexity.University of Pennsylvania, 1994

[2].Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, and Clifford Stein.Introduction to Algorithms.MIT Press, Cam bridge, MA, 2001

[3].Michael Sipser.Introduction to the Theory of Computation, second edi-tion.Thomson, USA, 2006.

最短路径的教学 篇3

聚类是最常用的数据分析技术之一，已经被广泛地应用到模式识别、数据挖掘和图像处理等领域。聚类分析是一个将数据样本划分为由相似对象组成的分组的过程。每一个组称为一个簇，每个簇中的数据对象的相似度大，而不同簇中的对象相似度小。从机器学习的角度来看，搜索簇就是一个无监督学习的过程。大数据图有很多内部具有实际意义的数据对象组成，两个数据对象间的相似关系可以转化成图模型。现实世界中的许多系统都是由网络图形来进行表示的，比如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，构建其划分的最简单直接的方法是解决最小割问题。定义W(A,B)=∑i∈A,j∈Bwij，并且是A的补集。对于给定的子集数目k，寻找划分A1,A2，…，Ak的问题为最小化目标函数:

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

(2)比例割集准则(Ratio-Cut)[10]

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

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

(3)规范割集准则(Normalized-cut)[14]

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

(4)最小最大割集准则(Min-max-cut)[15]

Ding提出了最小最大割集准则，该准则要求在最小化cut(Ai,)的同时，最大化W(Ai,Ai)，其目标函数为:

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

将x松弛到[-1,1]之间，根据Rayleigh熵原理，将最小化目标函数的问题转化为求解(D-W)x=KDx的第二小特征值问题。利用特征值计算相应的Fiedler特征向量，并根据启发式规则在向量中寻找划分点，使得在该点上得到的Ncut(A,B)值最小，将Fiedler向量中大于该点值的归为一类，小于该点值的为另一类。SM算法的效率明显优于PF算法。由Scott等人提出的SLH算法[16]对相似矩阵求其前k个特征值对应的特征向量构造特征向量矩阵V。对V的行向量进行规范化得到Q=VVT，若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 基于最短路径的随机游走模型

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

LRW定义了一个相似度评分如下:

其中，|E|是边集的数目。

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

其中，dij=dji。

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

1.3 基于随机游走的谱聚类

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

(1)根据数据集构造相似矩阵S和对角矩阵D;

(2)计算转移概率矩阵P=D-1S;

(3)计算P的前k个特征值对应的特征向量u1,u2，…，uk并构造矩阵U;

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

2 算法描述

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

2.1 问题定义

2.2 实验步骤

输入:无向图G={V,E}和聚类数目k;

(1)计算图的顶点间的最短距离，构造距离矩阵distance;

(2)利用LWRD算法计算顶点相似度矩阵Similarity;

(3)计算对角矩阵Diagonal;

(4)计算转移概率矩阵Probability;

(5)对Probability进行特征分解，取前k个特征值对应的特征向量u1,u2，…，uk;

(6)构造矩阵Eigen∈Rn×k，其中ui是Eigen中的第i列;

(7)将Eigen的每一行看做一个顶点，对这n个点(yi)i=1，…，n进行k-means聚类得到结果C1,C2，…，Ck;

输出:聚类结果C1,C2，…，Ck。

3 结果与分析

3.1 实验数据集

3.1.1 美国大学生足球联盟网络(American College Foot-ball)

这个数据集来自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指标都是与正确性相关的评价指标，并且都是对两个数据集相似性作对比，这里即是将聚类后的结果与数据集真实的labe做对比。模块性也是评价聚类好坏常用的一个指标，一个好的聚类结果应该具有较大的聚类内边数和较小的聚类间边数。

3.2.2 实验结果

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

4 结束语

最短路径的教学 篇4

关键词：图,加权属性图,最短路径,聚类

0 引言

近年来,图结构被广泛应用于多个领域来描述数据之间的复杂结构。针对海量图数据的分析和挖掘越来越重要。作为图数据挖掘算法的一种,图聚类算法引起了众多关注[1,2]。图聚类,简单描述就是根据图结构上节点和边的某种相似性,将图上的节点和边划分为不同的组。属性图聚类是图聚类中的一种特殊情况,即在用节点和边表示实体和实体关系的同时,还需要考虑到节点和边的属性。在属性图聚类时,同时考虑节点间结构和属性的相似性,则能够得到更加准确的聚类效果。如何更好地同时结合结构和属性进行聚类是目前图聚类研究的热点和难点。

针对属性图聚类问题,现阶段也有许多研究成果:Tian等人[3]根据聚类中节点和属性相一致的原则,提出了k-SNAP算法,该算法通过用户的下钻和上取,将属性一致的点聚集在一起,实现了多粒度的图聚类。但是此算法仅根据节点属性聚类,会造成聚类结构分散,聚类效果中节点数过多。针对k-SNAP算法存在的问题,Zhang等人[4]改进了该算法,对数值属性分类,并对属性相近对按相似度基于最大恶化程度进行划分。Nevile等人[5]将具有相同属性的属性个数定义为边的权重值,并以此为基础将属性图转化为带权图进行聚类。Steinhaeuser等[6]提出了相似的算法,并将属性扩展到具有连续值域的情况。此类算法由人工定义权重值,虽然算法效率高,但聚类效果和可拓展性差。也有一些算法通过增广属性图[7,8],采用熵的统一模型来衡量图中的同质性,实现属性图的聚类。该方法虽然将图的结构和属性结合起来聚类,但统一聚类超结点中的结点联系并不紧密。还有一些算法把模型的思想[9,10]应用到属性图聚类中,将属性图聚类转化为概率问题,但此类算法需要事先设定好聚类数量,才能达到较好的聚类效果。

针对以上算法的问题,本文提出了一种基于最短路径的加权属性图聚类算法WASP。该算法通过建立加权属性图模型,对图中边和节点的属性设置权值,确定节点相似度,采用最短路径算法计算节点间的距离,确定聚类中心,并在聚类过程中自动更新权重值,以此为基础进行聚类。最后将WASP算法应用在DBLP数据集中,通过实验对比,该算法具有较好的聚类效果。

1 相关定义

1.1 属性加权无向图定义

定义1属性加权无向图G=(V,E,A,ω);其中:

V表示属性图中节点集合:V={v1,v2,…,vn};

E表示属性图中边的集合:E={(vi,vj)(vi,vj)∈R,1≤i,j≤n,i≠j};

A表示图的属性的集合:A={a1,a2,…,am};其中|A|=m';

ω为边的权重值:ω={ω1,ω2,…,ωp},|ω|=p',ωa(ik)表示节点vi的属性ak的权值,若任意两节点vi、vj直接相连,则这两点节点间的权重值为ωi,j=ωq,q∈{1,2…,p};

1.2 节点相似度定义

在社交网络中,如果用户之间的公共朋友越多,则用户之间的联系越大。对于属性图中的节点,如果节点之间联系的公共节点越多,则这些节点位于同一个簇的可能性越大。本文考虑将与节点直接关联的点称为该节点的节点朋友。

定义2属性图G=(V,E),v为图中的节点。定义节点朋友集合为Κ(v):

若v、u之间有边,即<v,u>∈E,则将边的相似度定义为:

2 算法描述

2.1 自动更新属性权重值

为了得到较好的聚类效果,提出了一种自动更新属性权重值的方法,在聚类过程中不断更新属性权重值,来得到较好的聚类效果。

设定初始权重值ω=1.0,在聚类迭代过程中不断更新权重ω={ω1,ω2,…,ωp},设ω'={ω'1,ω'2,…,ω'p}为第n次迭代后的权重值,且初始值都为1。属性am第n次迭代的权值为amn,则属性第n+1次迭代后权值为:ωmn+1=ωmn+Δωmn。若一个簇中多个节点在am上有相同的属性值,则属性am具有较好的聚类效果趋势,则am的权重值将会增加;若在am上有相同属性值的节点很少,则说明属性am聚类效果趋势差,则属性权重值将会减少。用Γ(v,u)来测试节点是否具有相似性。根据式(2),若Γ(v,u)=1,则节点v和u具有相同的属性;若Γ(v,u)=0,则完全不同。Δωmn的值取决于同一簇中Γ(v,u)的数量,Γ(v,u)数量越大,Δωmn越大。则:

因此更新后的权重值:

由于ωmn+1的增大,这些节点划分到同一簇的可能性就越大,聚类效果就越好。

2.2 最短路径算法

为了发现图中高关联度的边,考虑到边的权重和相似度,设定参数α、β,且α+β=1。任意一条边上的关联度为:

两个节点间路径越长,则关联度越小,若要取得最大关联度的节点,则相邻节点直接取节点间最短距离,非相邻节点取节点之间最短距离的和。最大关联度的和为:

其中,Z是节点va、ub中间节点的集合。本文采用最短路径算法中的经典算法Dijkstra算法。

根据最短路径的最优子结构性质,如果存在一条从i到j的最短路径(vi,…,vk,vj),vk是vj前面的一顶点,那么(vi,…,vk)也必定是从i到j的最短路径。为了求出最短路径,Dijkstra提出了以最短路径长度递增,逐次生成最短路径的算法。例如对于源顶点v0,首先选择其直接相邻的顶点中长度最短的顶点vi,那么当前已知可得从v0到达vj顶点的最短距离:

根据这种思路,假设存在图G=(V,E,ω),源顶点为v0,U={v0},dist[i]记录v0到vi的最短距离,path[i]记录从v0到vi路径上的i前面的一个顶点,则算法过程为:

1)从{V-U}中选择使dist[i]值最小的顶点i,将i加入到U中;

2)更新与i直接相邻顶点的dist值,即dist[j]=min{dist[j],dist[i]+matrix[i][j]};

3)直到U=V。

2.3 聚类算法描述

基于最短路径的图聚类算法,就是在计算最大关联度时采用最短路径算法,选取相应的节点并划分到同一簇中。具体算法步骤如下:

输入:属性加权无向图G=(V,E,A,ω),初始权重值ω=1.0,聚类数量k,参数α=0.4,β=0.6;

输出:划分的不同的簇;

1)计算边的相似度Γ(v,u);

2)在初始聚类数量k中选择节点作为初始聚类中心Vstart,且Vstart不能为空集。定义剩余节点Vleft=V-Vstart;

3)选取Vleft中的任意节点vr,并分别判断与Vstart中的节点的最短距离dist[j],选择距离最近的节点划分在一起,并更新权重值ωmn+1;

4)在划分好的节点中,根据更新的权重值,得到L(va,ub),并将关联度大且距离短的的节点划分为一簇;

5)若Vleft=Ø,则聚类结束,所有节点划分完毕,若Vleft≠Ø且Vleft<k则继续执行步骤3)。

WASP算法是一种基于最短路径对图的结构和属性聚类的算法。在算法时间复杂度方面,第1步,计算边的相似度,时间复杂度为Ο(n);第2、3步,选择聚类中心的,时间复杂度为Ο(n3),第3-5步,计算最短路径,划分节点到不同的簇,时间复杂度为Ο(kn-n2),其中k为初始聚类数量。该算法总体时间复杂度为Ο(n3)。

3 实验与分析

3.1 实验数据集

本次实验采用DBLP数据集。这是一个学术合作关系的网络。由德国的特里尔大学创建的发表在计算机期刊、杂志和会议论文的数据库系统。该网络包括一万多个节点和两万多条无向边。其中节点表示论文作者,边代表作者们合作完成的论文。本次实验选择了该网络提供的在数据挖掘、数据库、人工智能、信息检索等相关领域发表论文最多的5000名作者英文单位。

作者单位的中英文要完全对应,每个实词的首字母大写。在部门名称和单位名称之间、在单位名称和城市名之间使用英文逗号隔开,城市名和邮编之间使用一个英文空格隔开,不能用逗号。

3.2 评价标准

本次实验将WASP算法与SCAN算法进行比较,并采用聚类密度和时间作为评价标准来评价聚类效果。定义聚类密度为density[11],density({Gi}ki=1)为聚类密度函数,{Gi}ki=1为算法输出集合,则:

3.3 实验结果

实验时设定聚类初始数量k=5,10,15,20,25,30,图1为WASP算法与SCAN算法在DBLP数据集上的聚类密度效果。由图1可知,在聚类数量较少时,WASP算法与SCAN算法聚类效果没有太大差别,但当聚类数量增多时,WASP算法更具有优势。这是因为WASP算法不但考虑了图的属性和结构,还考虑到了节点间的权重值,在聚类数量增多的时候,节点间的权重值也会增大,此时WASP算法聚类效果更明显。

为了更好地对比两个算法的聚类效率,选择对比两算法的聚类时间。在实验数据集上分别运行WASP算法和SCAN算法各10次,并记录下每次运算所消耗的时间。取10次运算的平均值作为聚类时间。

由图2可知,当聚类数目较小时,WASP算法与SCAN算法聚类时间差距不大。但当聚类数目开始增多时,SCAN算法无明显变化,WASP算法却出现变化。这是因为由于该算法在聚类迭代时,每次都要计算当前聚类中心到所有节点的最短距离。当聚类数量增多,即k的值增加时,由于算法3-5步的时间复杂度为Ο(kn-n2),算法第3-5步所消耗的时间将会增加。因此算法总体时间将会变长,而对于SCAN算法来说,时间复杂度不会有明显变化。在大型图聚类算法中,WASP算法时间会长于SCAN算法,但由于k值对WASP算法时间影响较小,因此具体到实际应用中只有几秒钟时间,且在小型数目集中没有明显区别。

4 结语

本文通过对现有图聚类算法的研究,以加权属性图为模型,提出了基于最短路径的加权属性图算法。该算法结合图的属性和结构进行聚类,实验表明,该算法比一般图聚类算法具有更好的聚类效果。但是该算法在大型图上聚类时间略长于其他聚类算法,需要在今后的工作中进一步的改进。

参考文献

[1]Majumdar D,Kanjilal A,Bhattacharya S.Separation of scattered concerns:a graph based approach for aspect mining[J].ACM SIGSOFTSoftware Engineering Notes,2011,36(2):1-11.

[2]Sengupta S,Kanjilal A,Bhattacharya S.Measuring complexity of component based architecture:a graph based approach[J].ACM SIGSOFTSoftware Engineering Notes,2011,36(1):1-10.

[3]Tian Y,Hankins R A,Patel J M.Efficient aggregation for graph summarization[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data.ACM,2008:567-580.

[4]Zhang N,Tian Y,Patel J M.Discovery-driven graph summarization[C]//Data Engineering(ICDE),2010 IEEE 26th International Conference on.IEEE,2010:880-891.

[5]Neville J,Adler M,Jensen D.Clustering relational data using attribute and link information[C]//Proceedings of the text mining and link analysis workshop,18th international joint conference on artificial intelligence.2003:9-15.

[6]Steinhaeuser K,Chawla N V.Community detection in a large real-world social network[M]//Social computing,behavioral modeling,and prediction.Springer US,2008:168-175.

[7]Cheng H,Zhou Y,Yu J X.Clustering large attributed graphs:A balance between structural and attribute similarities[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2011,5(2):12.

[8]Liu Z,Yu J X,Cheng H.Approximate homogeneous graph summarization[J].Information and Media Technologies,2012,7(1):32-43.

[9]Xu Z,Ke Y,Wang Y,et al.A model-based approach to attributed graph clustering[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.ACM,2012:505-516.

[10]Zanghi H,Volant S,Ambroise C.Clustering based on random graph model embedding vertex features[J].Pattern Recognition Letters,2010,31(9):830-836.