WHU Bruisefree分享 http://blog.sciencenet.cn/u/bruisefree Link together

博文

中介中心性的快速计算方法

已有 25012 次阅读 2013-12-11 21:03 |系统分类:科研笔记

中介中心性的定义是在路径基础之上的。从节点s到节点t的路径是指通过边连接一个节点序列,每一个节点连接了其前一个节点和后一个节点。路径的长度是指路径上所有边的权重之和,用d(s,t)表示,也称为节点s到节点t的距离。在图论中,一般使用最短路径计算各种指标。σst表示节点s到节点t的最短路径数量,σst(v)表示节点s到节点t的最短路径中经过节点v的数量。根据Freeman(1977)的定义,中介中心性是指经过节点v的所有最短路径的数量,若节点s到节点t的最短路径有两条,经过节点v的路径只有一条,那么节点v所得值normalize1/2


        根据最短路径和中介中心性的定义,有:

        Bellman标准:如果节点v在节点st的最短路径上,那么d(s,t)= d(s,v)+d(v,t)。即svvt都需要是最短路径。

        节点v来自于节点对<s,t>最短路径的中介中心性δst(节点对依赖值),其所获取的最短路径数量:


      那么节点v的最终中介中心性是网络中所有节点对的最短路径经过该节点的δst之和。

      因此,中介中心性的计算方法一般分为两步:

      1)计算所有节点对的最短路径数和最短路径长度;

      2)针对单个节点,加总其所有节点对依赖值。

       

l  最短路径数量计算

        从一个起点s开始搜寻,在无权网络中使用广度优先算法和在加权网络中使用Dijkstra算法开始计算。在每一步,选择到已发现节点集合中最近的节点,其目的是寻找到该起点s的所有最短路径。节点v的直接前序节点集合为:      

      那么,根据节点v的前序节点可以算出经过该节点的最短路径数:


l  汇总节点对依赖值

定义节点v来自于节点s的中介中心性依赖值为所有以节点s为起点经过节点v的节点对的节点对依赖值之和。

下图可以形象地表示该定义:

        如果s,t之间仅有一条最短路径,则可以将vs的依赖值,转化为其前序节点对s的依赖值:


为什么括号中要加1?是因为w,v之间也是一条最短路径,需要加总到v上。

        去除只有一条最短路径的限制,则:

根据以上公式,算法描述如下:    

CB[v]=0, vV ;//初始化所有节点的中介中心性值为0

for  sV do//依次将节点作为源节点

S=empty stack;//初始化空堆,作于寻找s的连通片

P[w]=empty list, wV ;//初始化空列表数组,节点w的前序节点集合,

σ[t]=0, tV ; σ[s]=1;//初始化st的最短路径数

d[t]=-1, tV ; d[s]=0;//初始化st的最短路径长度

Q=empty queue;//该队列用于广度优先搜索

enqueue sàQ;//s加入到队列中

while Q not  empty do//如果队列不为空

dequeue vßQ;//从队列中取出一个节点v

push vàS;//v加入到堆中,加入到s的连通片中

foreach neighbor w of v do//取出节点v的所有邻居节点

// w found for the first time?

if d[w] < 0 then//如果sw还没有计算过,那么其值为-1,则初始计算d(s,w)=d(s,v)+1

enqueue wàQ;//取出w到队列中

d[w]=d[v] +  1;

end

// shortest path to w via v?判断sw的最短路径是否经过v, 如果是那么到w的依赖最短路径数需要加上经过v的最短路径数。

if d[w] = d[v] + 1 then

σ[w]=σ[w] + σ[v];

append vàP[w];//v加入到w的前序节点集合中

end

end

end

δ[v]=0, vV ;//初始化所有节点依赖于s的中介中心性值

// S returns vertices in order of non-increasing  distance from s

while S not  empty do//S不为空时,S的连通片不为空

pop wßS;//S中取出一个节点w

//取出w的前序节点集合,计算其依赖于s的中介中心性值

for vP[w] do

δ[v]=δ[v] +σ[v]/σ[w](1+δ[w]);//参见上文公式

if ws then CB[w]=CB[w] +δ[w];//w的依赖中介中心性值汇总到其中介中心性值上

end

end

 

算法空间复杂度O(n + m),无权网络的时间复杂度O(nm),加权网络的时间复杂度O(nm + n2 log n)

该方法是用于计算节点的中介中心性值,边的中介中心性也可以相应的得到。

 

参考文献

[1]Ulrik Brandes: A Faster Algorithm forBetweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001.




http://wap.sciencenet.cn/blog-563898-749040.html

上一篇:Indri多索引文件创建、合并及使用
下一篇:Girvan-Newman社群发现算法

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-11-27 10:30

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部