2018, Vol. 29
挖掘网络中的重要节点是图分析领域中的基础问题, 例如在社交网络中, 找到那些影响力大的用户节点可以更有效地实现病毒营销等任务.衡量节点自身重要性的标准有很多, 比如点度中心度(degree centrality)、接近中心度(closeness centrality)、特征向量中心度(eigenvector centrality)和介数中心度(betweenness centrality)[1]等.其中, 节点的介数中心度(betweenness centrality)量化了一个节点作为其他节点之间最短路径上桥梁的能力, 刻画出了社会网络中一个用户对于其他用户之间交流的影响能力, 是一种非常重要的度量指标.于是, 节点介数中心度(本文以下简称为介数中心度)经常被应用于供应链管理、恐怖分子发现和艾滋病网络等诸多领域[2].
近些年来, 作为网络图分析领域的一个研究热点, 涌现出了一批介数中心度计算的优秀成果[2-8].然而, 因为介数中心度的精确计算依赖于图中所有点对间的最短路径, 所以其计算效率依然不高.对于介数中心度精确计算任务, 目前公认的最快方法在无权图上的时间复杂度为Ο(mn), 在有权图上的时间复杂度为Ο(mn+n2logn)[3].显然, 上述效率无法满足现实生活中的大量需求.例如, 在以微博为代表的主流社交网络中, 用户关系是不断变化的.网络中一方面持续产生大量新“网红”; 另一方面, 绝大多数“网红”过一段时间后就人气滑落, 甚至消失.这些“网红”节点的重要性往往存在一个急速上升而后又急速下降的过程.如果在网络每次变化时, 都重新计算所有节点的介数中心度, 那么时间开销显然是巨大的.因此, 本文对动态网络中节点介数中心度的更新进行研究, 尝试寻找一种快速更新的方法, 提高介数中心度精确计算的效率.
除了节点和边, 网络图中通常还存在社区的概念.社区[9]是复杂网络的普遍特征, 可以认为一个网络是由许多社区组成的.社区本身还没有公认的形式化定义.一般认为, 社区就是由一些节点组成的聚合体, 其中, 同一社区内的节点关系相对密切, 而不同社区间的节点关系相对而言比较松散.
社区发现(community detection)对于研究网络的特性具有重要意义.找到那些属于同一社区的相似节点, 可以更加细化地进行用户的特征挖掘、喜好推荐等工作.因此, 近些年许多学者投入到复杂网络中社区的发现与研究中, 并提出了不少社区发现的算法, 社区发现的研究成果也被成功应用于好友推荐、个性化商品推荐、蛋白质功能预测、舆情分析与处理等众多领域[10].受社区概念的启发, 我们考虑借助社区自身的特性, 即社区间、社区内节点的联系, 尝试在动态图上快速、精准地进行节点介数中心度的更新计算.
针对前述问题, 本文提出一种基于社区的节点介数中心度的快速更新算法, 能够有效减少节点介数中心度的计算量, 提高节点介数中心度的更新效率.
本文的主要贡献包括:
(1) 提出了社区与社区间最短距离集合、社区与节点的最短距离集合的概念, 并基于这些概念快速找到图结构变化过程中最短路径改变的点对;
(2) 提出了一种基于社区间最短距离集合的节点介数中心度的快速更新算法CBU(community based node betweenness centrality updating).利用上述概念, 只需要计算那些最短路径改变的点对, 即可提高节点介数中心度的更新效率;
(3) 在真实数据集和合成数据集上进行了大量实验.实验结果表明, 本文所提算法具有良好的加速效果.
本文第1节介绍节点介数中心度计算和社区发现领域的相关研究工作.第2节给出CBU算法所用到的基本概念.第3节给出最短路径数量的计算方法和CBU算法的社区过滤策略.第4节提出基于社区的介数中心度更新算法CBU, 并分析其时间和空间复杂度.第5节给出实验测试结果及分析.第6节总结全文.
1 相关工作 1.1 介数中心度介数中心度是网络图中节点中心度度量的一项重要指标, 它受图中所有点对的最短路径影响.在图中常用的计算所有点对最短路径的Floyd-Warshall算法的时间复杂度为Ο(n3), 这导致基于Floyd-Warshall算法进行节点介数中心度计算的方法时间复杂度均不低于Ο(n3).显然, 这样的计算速度太慢, 无法满足动态网络的需求.因此, 如何减少介数中心度所依赖的最短路径计算量, 从而提高介数中心度的计算效率, 也就成为了研究的重点.具体地, 有如下两种基本的加速思路:
第1种, 减少冗余的计算量.Brandes等人[3]提出了一种基于改进的广度优先搜索和点对依赖的算法, 减少了最短路径不必要的计算, 使无权图上的时间复杂度降低为Ο(mn), 有权图上的时间复杂度也降为Ο(mn+n2logn).这也是目前最常用的介数中心度计算方法.然而, Brandes算法本身仍旧依赖于所有点对间最短路径的计算, 效率依然有限.如何进一步减小介数中心度对于点对最短路径的依赖性, 成为加快介数中心度更新的首要策略.Sariyüce等人[4]提出了一种将图拆分压缩的策略, 通过将复杂的网络图拆分成多个简单的子图, 并将许多作用等价的节点合并, 大大简化原有的网络, 从而加快介数中心度的计算.Lee等人[5, 6]提出了一种利用无向图中的环路的方法, 过滤介数中心度不受边增减操作影响的节点, 从而提高了更新效率.
第2种, 计算介数中心度的近似值, 而不追求其精确值.Brandes等人[7]提出了一种近似算法, 通过选取一些支点, 计算有限数量的单源最短路径, 进而对所有节点的介数中心度进行无偏估计.Bader等人[2]提出了一种基于自适应的采样技术, 显著降低了具有较高中心度的节点单源最短路径计算量.Geisberger等人[8]改进并推广了Brandes的算法, 给出了一个计算框架, 提高了原有的近似比.
然而, 上述两种加速思路都没有充分考虑到网络图中固有的社区特性.
1.2 社区发现社区的概念最早是由Girvan等人[9]于2002年提出, 他们认为:复杂网络除了具有小世界和无标度的特征之外, 还具有社区这种特殊结构.此后, 社区与社区发现逐渐成为热门的研究话题, 来自不同领域的学者们从各自的角度提出了大量的有效方法.
文献[9]提出了社区发现的基本算法G-N, 通过移除具有最大边介数的边来划分社区.该算法将原来的网络直接进行分割, 自上而下形成社区.在此基础上衍生出了许多算法, 例如, Radicchi[11]和Newman[12]分别用边聚类系数和modularity矩阵的特征值代替最大边介数来进行网络分割.整体上看, 这类算法精度很高, 但是速度较慢.例如, G-N的时间复杂度为Ο(n3).
与上述依据分割思想的方法相对应, 自底向上凝聚的方法通过逐步扩展的方式形成最终的社区. Newman[13]提出了一种快速算法NFGA, 其精度比G-N略低, 但时间复杂度减小到了Ο((m+n)n).在此基础上, Clauset等人[14]又给出了改进算法CNM, 时间复杂度仅为Ο(n(logn)2).
另一种主流的社区发现方法通过标签的传播形成社区.Raghavan等人[15]于2007年提出了LPA算法, 首先给每个节点指定唯一的标签, 而后通过异步更新的方式将每个节点的标签赋值为其邻接节点中出现次数最多的标签, 最终将标签一致的节点划为一个社区.在此基础上, Leung等人[16]于2009年提出了HANP算法, 进一步引入标签传播能力衰减的概念和节点获取新标签偏好的概念, 使得社区发现的结果更加稳定与可靠.上述两个算法的时间复杂度均为Ο(T(m+n))(其中, T为迭代次数), 效率相对较高.
除此之外, 还有矩阵分块(DSGE)[17]、脉络图聚类(gCluSkeleton)[18]、图嵌入(Deepwalk)[19]和深度稀疏自动编码器(CoDDA)[20]等不同方法.
结合介数中心度和社区发现的研究目前尚不多见.与本文最相近的工作是文献[21], 该文提出了一种基于社区的最短路径近似算法, 利用社区代替社区内部的具体节点, 维护社区间的最短路径, 近似计算节点间的最短路径.但是该文仅将社区作为一类超节点, 并未考虑网络动态变化对社区结构带来的变更, 不能有效支持动态网络.同时, 该方法得到的只是近似的最短路径, 而非精确的最短路径, 于是也就无法支持节点介数中心度的有效计算.
2 基本概念本节对CBU算法涉及到的概念术语进行定义.
给定复杂网络图G=(V, E), V={v1, v2, …, vn}是节点集合, E={e1, e2, …, em}是边集合.如果没有特别声明, n= |V|表示节点的个数, m=|E|表示边的个数, ω(v, w)表示节点v到节点w的边权值(无权重默认为1).c={v1, v2, …, v|c|}表示由|c|个节点组成的社区.两个节点之间的距离dvv(s, t)指从节点s出发到达节点t的最短路径的长度, 简记为d(s, t).σ(s, t)表示节点s到节点t的最短路径的数量.σ(s, t|v)则表示节点s到节点t的经过节点v的最短路径的数量.于是, 节点v的介数中心度为
定义1(社区到社区的最短距离集合).给定网络图G=(V, E), c1={v1, v2, …, vk}和c2={u1, u2, …, ul}是G中的两个社区.c1到c2的最短距离集合dcc(c1, c2)为c1中所有节点到c2中所有节点的最短距离的集合, 即:
| $ {d_{cc}}\left( {{c_1}, {c_2}} \right) = \left\{ {d\left( {v, u} \right)\left| {v \in {c_1}, u \in {c_2}} \right.} \right\} $ | (1) |
鉴于整个最短距离集合所占据的存储空间较大, 且在计算节点介数中心度的实际应用中, 该集合的边界值比集合内大部分值的作用更大, 于是, 我们仅记录每个最短距离集合中的最小值dcc(c1, c2)min与最大值dcc(c1, c2)max.
定义2(社区与节点的最短距离集合).给定网络图G=(V, E), c={v1, v2, …, vk}是G中一个社区, u是图G中一个节点.社区c到节点u的最短距离集合dcv(c, u)为社区c中所有节点到节点u的最短距离的集合; 同时, 节点u到社区c的最短距离集合dvc(u, c)为节点u到社区c中所有节点的最短距离的集合, 即:
| $ {d_{cv}}\left( {c, u} \right) = \left\{ {d\left( {v, u} \right)\left| {v \in c} \right.} \right\} $ | (2) |
| $ {d_{vc}}\left( {u, c} \right) = \left\{ {d\left( {u, v} \right)\left| {v \in c} \right.} \right\} $ | (3) |
显然, 在无向图中, dcv(c, u)和dvc(u, c)是等价的.而在有向图中, 两者并不相等.同样为了减少存储开销, 对于无向图, 我们只记录dcv(c, u)的最小值dcv(c, u)min和最大值dcv(c, u)max; 对于有向图, 我们则记录dcv(c, u)的最小值dcv(c, u)min和最大值dcv(c, u)max以及dvc(u, c)的最小值dvc(u, c)min和最大值dvc(u, c)max.
例1:如图 1所示, 无向图G中包含16个节点.假定依照虚线将G划分为4个社区.对于左上角的社区c1和右下角的社区c4, 因为c1和c4之间距离最近的点对为(v5, v15), 其最短距离d(v5, v15)=1, 距离最远的点对是(v1, v16), 其最短距离d(v1, v16)=3, 所以可以得到dcc(c1, c4)min=1, dcc(c1, c4)max=3.同理, 社区c1与节点v14的最短距离集合dcv(c1, v14)的最小值dcv(c1, v14)min=3, 最大值dcv(c1, v14)max=4.
|
Fig. 1 An example for the shortest path sets between communities 图 1 社区最短距离集合示意 |
3 点对过滤
本节给出CBU算法中点对间最短路径数量的计算方法以及基于社区的点对过滤策略, 它们是下一节中动态网络节点介数中心度更新算法的基础.
3.1 最短路径从节点介数中心度的定义可知, 介数中心度依赖于点对间的最短路径数量.因此, 我们在本节给出最短路径数量的有效计算方法.
如算法1和算法2所示:本文的最短路径数量计算方法采取深度优先搜索的遍历方式, 对给定点对依次访问源节点所有的邻居节点, 由最短距离判断邻居节点是否出现在给定点对的最短路径中.若出现, 则将给定点对的最短路径数量转化为其邻居节点到目标节点的最短路径数目之和.通过上述方法, 即可得到我们所需点对的最短路径数量.注意到更新两点间最短路径数σ(s, t)时, 会计算一些额外的点对间最短路径数(算法2第7行, 计算出了σ(v, t)), 因此, 我们会在具体实现中维护一个标志位矩阵, 记录哪些点对间的最短路径数已经算出, 以避免重复计算.
算法1.所有点对间最短路径数计算 CountPath.
输入:G=(V, E), d;
输出:σ.
1. for(s, t)∈VxV do
2. σ(s, t)←UpdatePath(G, d, s, t)
3. return σ
算法2.两点间最短路径数更新 UpdatePath.
输入:G=(V, E), d, s, t;
输出:σ(s, t).
1. if s==t
2. σ(s, t)←1
3. else
4. σ(s, t)←0
5. for (s, v)∈E do
6. if d(s, t)==d(s, v)+d(v, t) then
7. σ(v, t)←UpdatePath(G, d, v, t)
8. σ(s, t)←σ(s, t)+σ(v, t)
9. return σ(s, t)
例2:以图 1中节点对(v11, v15)为例, 用算法2计算从v11到v15的最短路径数σ(v11, v15).因为v11和v15不是同一个节点, 所以σ(v11, v15)初始化为0.注意到节点v11有邻居节点v9、v13和v14.对于节点v9, 因为d(v11, v15)=2= d(v11, v9)+d(v9, v15)=1+1, 所以存在经过节点v9的从节点v11到节点v15的最短路径, 用UpdatePath(G, d, v9, v15)计算出σ(v9, v15)=1, 因此σ(v11, v15)=σ(v11, v15)+σ(v9, v15)=0+1=1.对于节点v13, 因为d(v11, v15)=2=d(v11, v13)+d(v13, v15)=1+1, 所以也存在经过节点v13的从节点v11到节点v15的最短路径, 用UpdatePat(G, d, v13, v15)计算出σ(v13, v15)=1, 因此σ(v11, v15)=σ(v11, v15)+σ(v13, v15)=1+1=2.而对于节点v14, d(v11, v15)=2 < d(v11, v14)+d(v14, v15)=1+2, 所以不存在经过节点v14的从节点v11到节点v15的最短路径, σ(v11, v15)不变.综上所述, 从节点v11到节点v15的最短路径数s(v11, v15)=2.
以上计算了给定网络图中两点间的最短路径数量σ(s, t), 接下来考虑如何计算经过任意节点的最短路径数量σ(s, t|v).最朴素的方法是记录每一条最短路径经过的所有节点, 进而逐个节点进行统计.但是这样需要维护所有最短路径的信息, 不仅占用的空间巨大, 而且时间开销也较长.因此, 我们考虑通过定理1将其转化为更容易计算的形式:
定理1[22].给定图G=(V, E), 若图上节点v至少在节点s到节点t的一条最短路径上出现, 则s到t的经过v的最短路径个数σ(s,t|v), s到v的最短路径个数σ(s, v), v到t的最短路径个数σ(v, t), 三者满足性质:
σ(s,t|v)=σ(s,v)xσ(v,t).
基于定理1, 可将经过某点的最短路径数量转化成对应的最短路径数量的乘积, 提高计算效率.
3.2 社区过滤引理1.给定有向网络图G=(V, E), s, t, u, v为图G中的4个节点.令u→v是在节点u和v之间添加的一条边, 权重为ω.s到t的最短路径发生改变, 当且仅当d(s, t)≥d(s, u)+d(v, t)+ω(u, v).
证明:
(⇐必要性):假设d(s, t)≥d(s, u)+d(v, t)+ω.设s到u的一条最短路径为(s…u), v到t的一条最短路径为(v…t), 则s到t的新路径(s…u, v…t)的长度为d(s, u)+d(v, t)+ω.根据假设有d(s, u)+d(v, t)+ω≤s到t的原最短路径的长度d(s, t), 因此(s…u, v…t)成为了新的最短路径, 即s到t的最短路径发生改变.
(⇒充分性):反证法.假设d(s, t) < d(s, u)+d(v, t)+ω.若最短路径s到t发生改变, 则新的最短路径P必经过添加的边(u, v).于是, P的长度d(s, u)+d(v, t)+ω≤s到t的原最短路径的长度d(s, t), 这与原假设矛盾.于是, d(s, t)≥d(s, u)+ d(v, t)+ω (u, v).
在引理1的基础上, 可以得到定理2.
定理2.给定有向网络图G=(V, E), c1={s1, s2, …, sk}和c2={t1, t2, …, tl}是G中的两个社区, u和v为G中两个节点.令u→v是在节点u和v之间添加的一条权重为ω的边.当dcc(c1, c2)max < dcv(c1, u)min+dvc(v, c2)min+ω时, 社区c1内的点到社区c2内的点的最短路径均不变; 当dcc(c1, c2)min > dcv(c1, u)max+dvc(v, c2)max+ω时, 社区c1内的点到社区c2内的点的最短路径均改变.
证明:
● 当 dcc(c1, c2)max < dcv(c1, u)min+dvc(v, c2)min+ω时, 对于∀s∈c1, ∀t∈c2, d(s, t)≤dcc(c1, c2)max < dcv(c1, u)min+ dvc(v, c2)min+ω≤d(s, u)+d(v, t)+ω.由引理1, s到t的最短路径不变;
● 当 dcc(c1, c2)min > dcv(c1, u)max+dvc(v, c2)max+ω时, 对于∀s∈c1, ∀t∈c2, d(s, t)≥dcc(c1, c2)min > dcv(c1, u)max+ dvc(v, c2)max+ω≥d(s, u)+d(v, t)+ω.由引理1, s到t的最短路径均改变.
证毕.
同理, 我们可以得到定理3~定理5.
定理3.给定有向网络图G=(V, E), c1={s1, s2, …, sk}和c2={t1, t2, …, tl}是G中的两个社区, u和v为G中两个节点.令u→v是在节点u和v之间删除的一条权重为ω的边.当dcc(c1, c2)max < dcv(c1, u)min+dvc(v, c2)min+ω时, 社区c1内的点到社区c2内的点的最短路径均不变; 当dcc(c1, c2)min > dcv(c1, u)max+dvc(v, c2)max+ω时, 社区c1内的点到社区c2内的点的最短路径均改变.
定理4.给定无向网络图G=(V, E), c1={s1, s2, …, sk}和c2={t1, t2, …, tl}是G中的两个社区, u和v为G中两个节点.令(u, v)是在节点u和v之间添加的一条权重为ω的边.当dcc(c1, c2)max < dcv(c1, u)min+dcv(v, c2)min+ω且dcc(c1, c2)max < dcv(c1, v)min+dcv(u, c2)min+ω时, 社区c1内的点到社区c2内的点的最短路径均不变; 当dcc(c1, c2)min > dcv(c1, u)max+ dcv(v, c2)max+ω或dcc(c1, c2)min > dcv(c1, v)max+dcv(u, c2)max+ω时, 社区c1内的点到社区c2内的点的最短路径均改变.
定理5.给定无向网络图G=(V, E), c1={s1, s2, …, sk}和c2={t1, t2, …, tl}是G中的两个社区, u和v为G中两个节点.令(u, v)是在节点u和v之间删除的一条权重为ω的边.当dcc(c1, c2)max < dcv(c1, u)min+dcv(v, c2)min+ω且dcc(c1, c2)max < dcv(c1, v)min+dcv(u, c2)min+ω时, 社区c1内的点到社区c2内点的最短路径均不变; 当dcc(c1, c2)min > dcv(c1, u)max+ dcv(v, c2)max+ω或dcc(c1, c2)min > dcv(c1, v)max+dcv(u, c2)max+ω时, 社区c1内的点到社区c2内的点的最短路径均改变.
基于上述定理, 我们可以对更新操作后的不同情况进行具体分析.
在有向图上, 增删一条边后有如下3种情况.
(1)如果dcc(c1, c2)max < dcv(c1, u)min+dvc(v, c2)min+ω(u, v), 由定理2和定理3可知, 这两个社区间的点对最短路径均不发生变化, 可以全部忽略;
(2) 如果dcc(c1, c2)min > dcv(c1, u)max+dvc(v, c2)max+ω(u, v), 由定理2和定理3可知, 这两个社区间的点对最短路径均发生变化;
(3) 如果dcc(c1, c2)max≥dcv(c1, u)min+dvc(v, c2)min+ω(u, v)且dcc(c1, c2)min≤dcv(c1, u)max+dvc(v, c2)max+ω(u, v), 我们无法从这两个社区整体的最短距离数据上得到结果, 需要对其点对进行逐一判断, 从而确定每组点对最短路径的变化情况.
在无向图上, 增删一条边后有如下两种情况.
(1) 如果dcc(c1, c2)max < dcv(c1, u)min+dcv(v, c2)min+ω(u, v)且dcc(c1, c2)max < dcv(c1, v)min+dcv(u, c2)min+ω(u, v), 由定理4和定理5可知, 这两个社区间的点对最短路径均不发生变化, 全部忽略;
(2) 反之, 我们也无法从这两个社区整体的最短距离数据上得到结果, 需要对其点对进行逐一判断, 从而确定每组点对最短路径的变化情况.
综合以上分析, 通过社区的筛选, 我们可以从整体上过滤掉最短路径不受增加或删除操作所影响的点对, 而后对剩余的点对再进行详细分析, 减少最短路径的计算量, 从而提高介数中心度的更新效率.
4 介数中心度更新算法本节首先给出基于社区的节点介数中心度更新算法CBU(由算法3和算法4组成)的具体步骤, 然后对算法复杂度进行分析.为了便于读者理解, 本节余下部分以无向图为例进行讨论, 通过删减相关步骤易得有向图的对应版本.
4.1 边添加操作后的更新算法我们先讨论边的添加操作后的介数中心度更新情况, 见算法3.该算法分为4个步骤:首先, 通过社区与社区、社区与节点的最短距离集合进行过滤, 利用定理4快速找到那些最短路径发生变化的点对, 即待更新的点对, 并计算出其新的最短距离和最短路径数(第1行~第15行); 其次, 利用定理1计算出待更新点对在更新前的最短路径对介数中心度的影响, 并删去这些影响(第16行~第19行); 然后, 更新最短距离和最短路径数(第20行、第21行); 最后, 利用定理1计算待更新点对间新的最短路径对节点介数中心度的影响, 并更新社区与社区、社区与节点的最短距离集合(第22行~第27行).
算法3.插入边操作下的介数中心度更新算法.
输入:G=(V, E), d, dcv, dcc, σ, cB, (u, v, ω), C;
输出:新的cB.
1. for (ci, cj) CxC do
2. if dcc(ci, cj)max≥dcv(ci, u)min+dcv(v, cj)min+ω or dcc(ci, cj)max≥dcv(ci, v)min+dcv(u, cj)min+ω then
3. for (s, t)∈cixcj do
4. if d(s, t) < d(s, u)+d(v, t)+ω and d(s, t) < d(s, v)+d(u, t)+ω then
5. continue
6. else
7. 将点对(s, t)加入集合NodePair, 所属的社区对(ci, cj)加入集合 ComPair
8. if d(s, t)=d(s, u)+d(v, t)+ω then
9. σ'(s, t)← σ(s, t)+σ(s, u)×σ(v, t), d'(s, t)← d(s, t)
10. else if d(s, t)=d(s, v)+d(u, t)+ω then
11. σ'(s, t)←σ(s, t)+σ(s, v)xσ(u, t), d'(s, t)←d(s, t)
12. else if d(s, u)+d(v, t) < d(s, v)+d(u, t) then
13. σ'(s, t)← σ(s, u)×σ(v, t), d'(s, t)←d(s, u)+d(v, t)+ω
14. else then
15. σ'(s, t)←σ(s, v)×σ(u, t), d'(s, t)←d(s, v)+d(u, t)+ω
16. for (s, t)∈NodePair do
17. for r∈V do
18. if d(s, t)=d(s, r)+d(r, t) then
19. cB(r)←cB(r)-σ(s, r)×σ(r, t)÷ σ(s, t)
20. for (s, t)∈NodePair do
21. σ(s, t)←σ'(s, t), d(s, t)←d'(s, t)
22. for (s, t)∈NodePair do
23. for r∈V do
24. if d(s, t)=d(s, r)+d(r, t) then
25. cB(r)←cB(r)+σ(s, r)×σ(r, t)÷ σ(s, t)
26. 基于 ComPair 更新dcv, dcc
27. return cB
例3:在图 2中, 我们插入一条边v3v10, 在更新节点介数中心度时, 有些社区对可以直接过滤, 而有的社区对不能过滤掉.对于社区c2, c4来说:dcc(c2, c4)max=4 < dcv(c2, v3)min+dcv(v10, c4)min+1=2+2+1=5, dcc(c2, c4)max < dcv(c2, v10)min+ dcv(v3, c4)min+1=2+3+1=6.所以社区c2, c4间节点构成的点对最短路径不变, 直接过滤, 不用进一步计算.而对于社区c1, c3, 则无法通过社区层面直接过滤, 需对每一组点对依次过滤, 比如:点对v2, v13, d(v2, v13)=2 < d(v2, v3)+ d(v10, v13)+1=1+2+1=4, d(v2, v13)= 2 < d(v2, v10)+d(v3, v13)+1=4+1+1=6, v2, v13的最短路径不变, 不用进一步计算.而点对v1, v9, d(v1, v9)=3=d(v1, v3)+ d(v10, v9)+1=1+1+1=3, 其最短路径距离不变, 最短路径数量增多, 需要更新这些新增最短路径对节点介数中心度的影响.我们考虑v1, v9的最短路径对于节点v13的介数中心度的影响.在插入边v3v10之前, v1, v9的最短路径只有v1v3v13v9, 经过节点v13, v1, v9的最短路径对于节点v13的介数中心度的影响为1;在插入边v3v10之后, v1, v9的最短路径增加了v1v3v10v9, 不经过节点v13, v1, v9的最短路径对于节点v13的介数中心度的影响变成了1/2.因此更新之后, 点对v1, v9的最短路径的变化使得节点v13的介数中心度减少了1-1/2=1/2.其他社区对也可以照上述方法分析, 这里不再赘述.
|
Fig. 2 Anexample for adding an edge 图 2 添加边操作示意图 |
4.2 边删除操作后的更新算法
如算法4所示, 删除边后的介数中心度更新算法也分为4个步骤:首先, 通过社区与社区、社区与节点的最短距离集合进行过滤, 利用定理5快速找到那些最短路径发生变化的点对, 即待更新的点对(第1行~第5行); 其次, 利用定理1计算出待更新点对在更新前的最短路径对介数中心度的影响, 并删去这些影响(第6行~第9行); 然后, 利用算法2和算法5计算待更新点对新的最短路径和最短距离(第10行), 若更新前点对有最短路径不经过被删除的边, 则这些路径仍是最短路径, 该点对的最短距离不变, 最短路径数也可直接算出; 最后, 利用定理1计算待更新点对间新的最短路径对节点介数中心度的影响, 并更新社区与社区、社区与节点的最短距离集合(第11行~第16行).
算法4.删除边操作下的介数中心度更新算法.
输入:G=(V, E), d, dcv, dcc, σ, cB, (u, v, ω), C;
输出:新的cB.
1. for (ci, cj)∈C×C do
2. if dcc(ci, cj)max≥dcv(ci, u)min+dcv(v, cj)min+ω or dcc(ci, cj)max≥dcv(ci, v)min+dcv(u, cj)min+ω then
3. for (s, t)∈cixcj do
4. if d(s, t)≥d(s, u)+d(v, t)+ω or d(s, t)≥d(s, v)+d(u, t)+ω then
5. 将点对(s, t)加入集合NodePair, 所属的社区对(ci, cj)加入集合 compare
6. for (s, t)∈ NodePair do
7. for r∈ V do
8. if d(s, t)=d(s, r)+d(r, t) then
9. cB(r)←cB(r)-σ(s, r)×σ(r, t)÷σ(s, t)
10. 利用后文算法5更新d(s, t), 利用算法2重新计算σ(s, t).
11. for (s, t)∈NodePair do
12. for r∈V do
13. if d(s, t)=d(s, r)+d(r, t) then
14. cB(r)←cB(r)+σ(s, r)xσ(r, t)÷σ(s, t)
15. 基于 compare 更新dcv, dcc
16. return cB
需要注意的是:在计算新的最短路径时, 删除边的操作要比添加边的操作复杂.对于某些点对, 它们原有最短路径经过被删除的边, 这些点对的最短路径数和最短距离都需重新计算(算法4第10行).其中, 点对间的最短路径数量可由算法2得到.因此, 需要解决的问题是:在已知图上部分节点的最短距离的情况下, 如何获取其他点对的最短距离.虽然我们可以使用朴素的Floyd算法, 但是这样做耗时巨大.因此, 我们对Floyd算法进行一些修改.算法5中, 我们改进的Floyd算法仍然采用动态规划的思路, 但是通过避免无需改动点对的最短距离的冗余计算, 实现了降低部分点对最短距离更新的时间开销.
算法5.改进的Floyd-Warshall算法.
输入:G=(V, E), d, NodePair∈ VxV;
输出:新的d.
1. for (s, t)∈ NodePair do
2. d(s, t)← min(INT_MAX, ω(s, t))
3. for u∈V do
4. for (s, t)∈ NodePair do
5. d(s, t)← min(d(s, u)+d(u, t), d(s, t))
6. return d
例4:在图 3中, 我们删除边v11v13, 在更新节点介数中心度时, 有些社区对可以直接过滤, 而有的社区对不能过滤掉.对于社区c2, c4, dcc(c2, c4)max=4 < dcv(c2, v11)min+dcv(v13, c4)min+1=3+1+1=5, dcc(c2, c4)max < dcv(c2, v13)min+ dcv(v11, c4)min+1=2+2+1=5.所以社区c2, c4间节点构成的点对最短路径不变, 直接过滤, 不用进一步计算; 而对于社区c1, c3, 则无法通过社区层面直接过滤, 需对每一组点对依次过滤, 比如:点对v2, v12, d(v2, v12)=3 < d(v2, v11)+ d(v13, v12)+1=3+1+1=5, d(v2, v12)=3 < d(v2, v13)+d(v11, v12)+1=2+2+1=5, v2, v12的最短路径不变, 不用进一步计算; 而点对v2, v14, d(v2, v14)=4=d(v2, v13)+ d(v11, v14)+1=2+1+1=4, 其最短路径减少, 需要更新这些减少的最短路径对节点介数中心度的影响.我们考虑v2, v14的最短路径对于节点v15的介数中心度的影响.在删除边v11v13之前, v2, v14的最短路径有v2v3v13v9v14, v2v3v13v11v14, v2v3v13v12v14, v2v5v15v9v14和v2v8v15v9v14, 其中:有2条经过节点v15, v2, v14的最短路径对于节点v15的介数中心度的影响为2/5;在删除边v11v13之后, v2, v14中最短路径减少了v2v3v13v11v14这一条, 余下的4条中, 有2条经过节点v15, v2, v14的最短路径对于节点v15的介数中心度的影响变为2/4.因此更新之后, 点对v2, v14的最短路径的变化使得节点v15的介数中心度增加了2/4-2/5=1/10.其他社区对也可以按照上述方法分析, 这里不再赘述.
|
Fig. 3 Anexample for deleting an edge 图 3 删除边操作示意图 |
4.3 复杂度分析
由介数中心度的定义
在空间复杂度方面, CBU算法自身需要维护的数据包括网络图、节点最短距离d、节点最短路径数σ、社区间最短距离dcc等相关数据.于是, 其空间复杂度为Ο(|V|+|E|+2×|V|2+|C|2+2×|C||V|)=Ο(|V|2).
在时间复杂度方面, 首先, CBU算法需要使用社区进行过滤, 找出需要计算的点对.这一步消耗的时间为Ο(|C|2+ρ1×|V|2), 其中, ρ1是社区过滤后仍需检测的点对数占总点对数量的比值; 接下来, 我们要对找到的点对重新计算最短路径, 更新介数中心度, 每个点对消耗的时间可以认为是Ο(|V|), 因此, 更新的时间复杂度为Ο(ρ2× |V|2×|V|)=Ο(ρ2×|V|3), 其中, ρ2是最终待更新的点对占总点对数量的比值.最终, 一次更新操作的时间复杂度为Ο(|C|2+ρ1×|V|2+ρ2×|V|3)=Ο(ρ2×|V|3).最坏情况下, ρ2=1, 即:所有点对都需要重新进行计算, 消耗时间Ο(|V|3).而实际网络中, 这种极端情况发生的概率比较小.通常情况下, 社区内节点联系密切, 社区间节点关系较弱, 甚至不连通, 可以认为ρ2 ≪ ρ2 < 1, 因此, CBU消耗的时间是可接受的.
5 实验结果与分析本节使用真实数据集和合成数据集对所提算法进行实验验证和结果分析.首先介绍实验环境、数据集、评价标准, 然后进行性能对比实验和参数敏感性实验.
5.1 实验准备实验所用操作系统是Windows Server 2008, CPU是Intel Xeon E5-2650, 内存为256GB.本文所提算法及实验代码都基于C++语言和VS 2012实现.
本实验数据集分为合成数据集和真实数据集两部分, 见表 1.其中, 合成数据集包括:ER随机图[23], 实验中, ER_10000平均度数为10, ER_100000平均度数20;WS小世界网络[24], 实验中, WS_10000平均度数为10, 重新连接的概率为0.5, WS_100000平均度数为20, 重新连接的概率为0.5;BA无标度网络[25], 实验中, BA_10000平均度数为10, BA_100000平均度数为20;社区基准图ben_10000[26], 平均度数为10;真实数据集[27]包括:来自社交网络Facebook上的真实数据集ego-Facebook; 俄勒冈2001年路由网络的信息Oregon; 来自基于位置的社区网络的用户关系gowalla; Wikipedia在2008年1月前的投票关系图wiki-vote; 来自消费者评论网站Epinions的真实用户网络soc-Epininos1;2002年8月时, Gnutella对等文件共享网络的一份快照数据p2p-Gnutella25.其中, 数据集合ER_100000, WS_100000, BA_100000和gowalla的数据规模(节点和边的总和)均达到百万.
|
Table 1 Datasets information 表 1 数据集的统计信息 |
在实验中, 我们通过随机增减边的方式来实现网络的动态变化.每次随机增加或删除一条边, 我们对得到的新网络计算节点介数中心度, 并取计算的平均时间作为算法所消耗的时间.
5.2 评价标准为了更好地评价本文所提出的CBU算法的有效性, 针对有向图, 我们选择目前最主流的Brandes算法[3]作为基准算法; 针对无向图, 我们选择Brandes算法[3]和Lee等人[6]提出的无向图上的算法(以下简记为Lee)当作基准算法.
同时, 本文考虑如下3个评价指标.
(1) 时间.CBU算法的目标在于减小动态网络中节点介数中心度的更新计算开销, 于是, 计算所用时间T就成为第1个指标;
(2) 加速比.为了更直观地呈现本文所提算法与基准算法的差异, 我们用加速比Ra的概念来刻画算法效率.加速比指基准算法所用时间与CBU算法所用时间的比值, 值越大, 意味着CBU算法的效果越好;
(3) 过滤比.CBU算法的核心是:利用社区的整体性过滤掉那些不会因为边的增删而在最短路径方面受到影响的点对, 从而最终提高介数中心度的计算效率.因此, 我们基于定理2~定理5, 使用过滤比ρ来衡量经过社区这层过滤后, 所剩点对占总点对的比值.过滤比的值越小, 表明算法的过滤效果越好.
5.3 对比实验社区过滤算法CBU和基准算法在不同数据集上的效率对比情况见表 2, 其中, Ra为加速比, T是计算时间开销(单位为s).初始计算社区时, 本部分采用的社区发现算法是HANP.由于Brandes算法并未从流程上严格区分增加边和删除边, 对应这两种操作的计算相同, 所以其对应的时间开销也一致, 故表 2在Brandes算法的时间开销方面只列出一个值.对于CBU算法和Lee算法, 我们分别给出其在增加与删除边操作下所用的更新时间.需要注意的是:因为Lee算法仅适用于无向图, 所以在有向图上该算法对应的数据项为空.
|
|
Table 2 Efficiency of updating in different datasets 表 2 不同数据集更新效率 |
表 2中, CBU算法显著提高了动态网络中节点介数中心度的更新效率.在合成数据集上, CBU算法的效率大约是Brandes算法的30倍, 大约是Lee算法的10倍.其中, 添加一条边之后的更新效率略高于删除边之后的更新效率.在ER和WS中, 节点与边的分布比较均匀; ben对应的分布虽然不够均匀, 整个网络是连通的, 每个节点都至少与一定数量的边相关联.因此, 在这3类数据集上添加或删除边所影响的点对数量是相对固定的, 且差异不大, 即, 需要重新计算的点对数量大致相当.考虑到在添加边操作后, 可以直接得到点对的新最短路径, 耗时较短; 而在删除边操作后, 可能需要遍历整张图来获得点对的新最短路径, 耗时较长.这样的差异导致添加边操作后的更新一般快于删除边操作后的更新.而对于BA数据集, 整个网络类似一棵树, 添加操作影响到的点对少于删除操作影响的点对, 添加操作后的更新效率明显更高.
在真实数据集上, CBU算法在效率上也有明显提高.添加操作和删除操作后, 更新效率没有明显的规律.这主要是因为真实数据集中, 节点与边的分布不均匀.对于ego-Facebook和soc-Epininos1数据集, 节点平均度数比较高, 且聚集系数不低, 网络中存在若干规模较大的紧密社区.因此在进行边的添加操作时, 容易将这些大的社区连接, 使得受影响的点对较多.与此相比, 删除操作更容易发生在社区内部, 其影响范围有限.这使得添加边操作后的更新效率低于删除边操作后的更新效率.对于p2p-Gnutella25和Oregon数据集, 节点平均度数较低, 同时, 网络中的边集中于有限的节点上, 这使得图中存在大量孤立节点.因此在添加边操作时, 容易处理到孤立节点, 受影响点对较少, 加速效果明显.而删除边的操作则基本出现在网络的核心区域, 节点之间联系紧密, 于是, 删除操作所影响的点对较多, 更新效率也随之变慢.对于wiki-Vote数据集, 有向边的目标节点较为集中, 大量节点不存在入边, 只有少量出边.于是在添加边操作时, 易处理到这些度数较低的节点, 受影响的点对较少; 而删除边操作会涉及到那些入度较高的节点, 受影响的点对偏多, 因此, 添加边操作的效率高于删除边操作.对于gowalla数据集, 因为删除边操作后需要遍历整张图来获得受影响点对的新最短路径, 同时, gowalla节点数较大, 受影响的点对较多, 遍历整张图的成本也就较高, 所以删除边操作耗时较增加边操作明显增多.
图 4则是在数据集ben_10000上进行200次插入操作后的更新效率.我们将200次操作分为10个区间, 纵坐标为每个区间内更新节点介数中心度所消耗的平均时间, 横坐标为更新次数.从图中可以看出, CBU算法的更新效率比较稳定且明显优于Brandes算法和Lee算法.
|
Fig. 4 Comparison of the speed after adding edgeson the dataset ben_10000 图 4 在ben_10000数据集上插入边效率比较 |
接下来, 我们探究社区过滤效果对于介数中心度更新计算的影响.表 3展示了CBU算法的过滤能力.无论是合成数据集还是真实数据集, 社区过滤效果均在0.25以下.在合成数据集上, 删除操作的社区过滤效果略好, 但是无法弥补删除操作后寻找最短路径过程所消耗的时间.在真实数据集ego-Facebook上, 边添加操作后的社区过滤比高于边删除操作后的社区过滤比; 在真实数据集p2p-Gnutella25上, 边删除操作后的社区过滤比高于边添加操作后的社区过滤比.这与我们之前对于这两个数据集更新操作花费时间的分析是一致的.在真实数据集gowalla上, 社区过滤效果比较突出, 但是由于数据集节点数较大, 受影响的点对仍然很多, 更新速度的提高实际有限.整体上看, CBU算法提高了介数中心度的更新速度, 其采用的社区过滤策略是有效的.
|
|
Table 3 Filtration ratio of community in different datasets 表 3 不同数据集社区过滤比 |
5.4 参数实验
本节分析节点数量n以及社区发现的精度对实验结果的影响.
(1) 节点数量n
针对ER合成图, 设置节点的平均度数为10, 分析不同节点数量下, CBU算法的加速效率.
从图 5和图 6可以看出:随着节点数的增加, 3种算法所消耗的时间也在不断增大.但是对于添加操作和删除操作, CBU算法的时间开销均明显少于Brandes算法和Lee算法, 效率至少提升了一个数量级.这表明, CBU算法可以很好地提高节点介数中心度的更新效率.
|
Fig. 5 Comparison of the speed after adding an edge 图 5 插入边效率比较 |
|
Fig. 6 Comparison of the speed after deletingan edge 图 6 删除边效率比较 |
(2) 社区精度的影响
针对表 1中的合成图ben_10000, 采用不同的社区发现算法, 计算出社区结果的精度.然后, 在这些不同的社区结果上运行CBU算法, 分析社区精度对于CBU算法效率的影响.
对于社区精度, 我们采用的指标是Modularity, 这是Newman[28]于2004年提出的一个定义在[-0.5, 1)区间内的指标, 由网络图中每个社区内连边数与期待值之差决定.Modularity越大, 社区内部实际连边越是高于随机期望, 说明节点越有集中在某些社区内的趋势, 即网络的模块化结构越明显, 社区划分的精度越高.
从表 4可以看出:随着社区精度的提高, CBU算法的效率越高, 耗时越少.当Modularity较大时, 提升更为明显, 在CNM算法得到的社区上进行更新的耗时只有HANP的一半.总的来说, 社区发现的精度越高, CBU基于社区的过滤算法效果越好.
|
|
Table 4 Efficiency of updating with different communities 表 4 不同社区下的更新效率 |
6 结束语
为了解决在实际应用场景中节点介数中心度更新缓慢的问题, 本文提出了基于社区的节点介数中心度更新算法CBU, 通过维护社区间最短距离集合、社区与节点的最短距离集合, 快速过滤掉在网络更新过程中最短路径不变的点对, 大大提高了节点介数中心度的更新效率.未来, 我们将尝试利用社区的性质, 对节点介数中心度进行近似计算.
| [1] |
Merrer EL, Tredan G. Centralities: Capturing the fuzzy notion of importance in social graphs. In: Proc. of the European Conf. on Computer Systems. 2009. 33-38. [doi: 10.1145/1578002.1578008] |
| [2] |
Bader DA, Kintali S, Madduri K, Mihail M. Approximating betweenness centrality. In: Proc. of the Workshop on Algorithms and Models for the Web Graph. 2007. 124-137. [doi: 10.1007/978-3-540-77004-6_10] |
| [3] |
Brandes U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 2001, 25(2): 163–177.
[doi:10.1080/0022250X.2001.9990249] |
| [4] |
Sariyüce AE, Saule E, Kaya K, Çatalyürek ÜV. Shattering and compressing networks for centrality analysis. In: Proc. of the Computer Science. 2012. . |
| [5] |
Lee MJ, Lee J, Park JY, Choi RH, Chung CW. QUBE: A quick algorithm for updating betweenness centrality. In: Proc. of the Int'l Conf. on World Wide Web. ACM Press, 2012. 351-360. [doi: 10.1145/2187836.2187884] |
| [6] |
Lee MJ, Choi S, Chung CW. Efficient algorithms for updating betweenness centrality in fully dynamic graphs. In: Proc. of the Information Sciences. 2016. 278-296. [doi: 10.1016/j.ins.2015.07.053] |
| [7] |
Brandes U, Pich C. Centrality estimation in large networks. Int'l Journal of Bifurcation and Chaos, 2007, 17(07): 2303–2318.
[doi:10.1142/S0218127407018403] |
| [8] |
Geisberger R, Sanders P, Schultes D. Better approximation of betweenness centrality. In: Proc. of the Algorithm Engineering and Experimentation. 2008. 90-100. [doi: 10.1137/1.9781611972887.9] |
| [9] |
Girvan M, Newman ME. Community structure in social and biological networks. Proc. of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821–7826.
[doi:10.1073/pnas.122653799] |
| [10] |
Huang FL, Zhang SC, Zhu XF. Discovering network community based on multi-objective optimization. Ruan Jian Xue Bao/Journal of Software, 2013, 24(9): 2062–2077(in Chinese with English abstract).
http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=4400&flag=1 [doi:10.3724/SP.J.1001.2013.04400] |
| [11] |
Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. Proc. of the National Academy of Sciences of the United States of America, 2004, 101(9): 2658.
[doi:10.1073/pnas.0400054101] |
| [12] |
Newman ME. Modularity and community structure in networks. Proc. of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577–8352.
[doi:10.1073/pnas.0601602103] |
| [13] |
Newman ME. Fast algorithm for detecting community structure in networks. Physical Review E, 2004, 69(6).
[doi:10.1103/PhysRevE.69.066133] |
| [14] |
Clauset A, Newman ME, Moore C. Finding community structure in very large networks. Physical Review E, 2004, 70(6).
[doi:10.1103/PhysRevE.70.066111] |
| [15] |
Raghavan UN, Albert R, Kumara SR. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007, 76(3).
[doi:10.1103/PhysRevE.76.036106] |
| [16] |
Leung IX, Hui P, Lio P, Crowcroft J. Towards real-time community detection in large networks. Physical Review E, 2009, 79(6).
[doi:10.1103/PhysRevE.79.066107] |
| [17] |
Chen J, Saad Y. Dense subgraph extraction with application to community detection. IEEE Trans. on Knowledge and Data Engineering, 2012, 24(7): 1216–1230.
[doi:10.1109/TKDE.2010.271] |
| [18] |
Huang J, Sun H, Song Q, Deng H, Han J. Revealing density-based clustering structure from the core-connected tree of a network. IEEE Trans. on Knowledge and Data Engineering, 2013, 25(8): 1889.
[doi:10.1109/TKDE.2012.100] |
| [19] |
Perozzi B, Alrfou R, Skiena S. DeepWalk: Online learning of social representations. In: Proc. of the Knowledge Discovery and Data Mining. 2014. 701-710. [doi: 10.1145/2623330.2623732] |
| [20] |
Shang JW, Wang CK, Xin X, Ying X. Community detection algorithm based on deep sparse autoencoder. Ruan Jian Xue Bao/Journal of Software, 2017, 28(3): 648–662(in Chinese with English abstract).
http://www.jos.org.cn/1000-9825/5165.htm [doi:10.13328/j.cnki.jos.005165] |
| [21] |
Gong M, Li G, Wang Z, Ma L, Tian D. An efficient shortest path approach for social networks based on community structure. CAAI Trans. on Intelligence Technology, 2016, 1(1): 114–123.
[doi:10.1016/j.trit.2016.03.011] |
| [22] |
Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. The MIT Press, 2001.
|
| [23] |
Erdős P, Rényi A. On random graphs I. Publicationes Mathematicae, 1959, 6: 290–297.
http://citeseerx.ist.psu.edu/showciting?cid=1938645 |
| [24] |
Watts DJ, Strogatz SH. Collective dynamics of 'small-world' networks. Nature, 1998, 393(6684): 440–442.
[doi:10.1038/30918] |
| [25] |
Barabasi A, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509–512.
[doi:10.1126/science.286.5439.509] |
| [26] |
Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E, 2008, 78(4).
[doi:10.1103/PhysRevE.78.046110] |
| [27] |
SNAP datasets. http://snap.stanford.edu/data |
| [28] |
Newman ME, Girvan M. Finding and evaluating community structure in networks. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2): 26–113.
[doi:10.1103/PhysRevE.78.046110] |
| [10] |
黄发良, 张师超, 朱晓峰. 基于多目标优化的网络社区发现方法. 软件学报, 2013, 24(9): 2062–2077.
http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=4400&flag=1 [doi:10.3724/SP.J.1001.2013.04400]
|
| [20] |
尚敬文, 王朝坤, 辛欣, 应翔. 基于深度稀疏自动编码器的社区发现算法. 软件学报, 2017, 28(3): 648–662.
http://www.jos.org.cn/1000-9825/5165.htm [doi:10.13328/j.cnki.jos.005165]
|