君，已阅读到文档的结尾了呢~~
加权社交网络节点中心性计算模型
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
加权社交网络节点中心性计算模型
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口1986人阅读
昨天面试被问到betweenness的计算方法，很尴尬没有自己实现过。平时用的时候通常用Python的networkx包计算，具体算法之前还没了解过。复杂网络的教材通常就介绍了betweenness的意义与定义，直接从定义出发计算的复杂度达到O(n3)
这里介绍一个2001年brandes提出的算法”A faster algorithm for betweenness centrality”，在无权图上复杂度为O(mn),在有权图上复杂度在O(mn+nlogn),在网络稀疏的时候，复杂度接近O(n2).
betweenness定义
betweenness的直接定义式为：
CB(v)=∑s≠v≠t∈Vσst(v)σst
其中σst(v)表示经过节点v的s→t的最短路径条数,σst表示s→t的最短路径条数。
直观上来说，betweenness反映了节点v作为“桥梁”的重要程度。
为了方便，定义pair-dependency为
δst(v)=σst(v)σst
CB(v)=∑s≠v≠t∈Vδst(v)
如何计算σst
首先引入一个记号
Ps(v)={u∈V:{u,v}∈E,dG(s,v)=dG(s,u)+ω(u,v)}
意思就是从节点s到节点v的最短路径中v的前驱节点集。或者说如果从s→t的最短路径包含边(u,v),那么u属于这个集合。
我们会发现下诉关系式成立：?s≠t,
σsv=∑u∈Ps(v)σsu
理解这个关系式并不难：s→v的最短路径必然先从s→u,再通过边(u,v)到达v,其中u是v的前驱节点。
下面的问题简单多了，对无权图调用BFS算法，对有权图调用Dijkstra’s算法，前者在O(m)时间内算出{σst|t∈V},后者时间为O(m+nlogn)
简单介绍下BFS为什么可以做。我们知道BFS遍历节点的顺序恰好是按照距离节点s的距离升序排列的，而节点u是v的前驱节点必然要求d(s,u)&d(s,v),因此按照BFS遍历顺序，到达节点v时，其前驱节点u的σsu必然已经计算好了。
现在我们计算出所有的了σst，为了得到δst(v)我们可能还要计算σst(v),虽然可以通过下面的关系式计算，但是复杂度又上去了。
σst(v)={σsv?σvt0d(s,v)+d(v,t)=d(s,t)other
事实上我们并不关心具体的某个δst(v)，我们想要的是
∑s,tδst(v)
δs?(v)=∑t∈Vδst(v)
下面我们要说明下面这个关系式成立：
δs?(v)=∑w:v∈Ps(w)σsvσsw(1+δs?(w))
如果这个关系式成立的话，根据先驱关系，计算δs?(v)需要先计算δs?(w),而v是w的先驱,顺序恰好跟BFS相反，因此用个栈就可以了。
我们试图在节点w与它的前驱节点v建立关系。我们可以把通过节点w的最短路径分成两类
通过节点v的路径
不通过节点v的路径
为了推导方便，引入几个符号：δst(v,e)=σst(v,e)σst，σst(v,e)表示s→t最短路径通过节点v和边e的条数。
显然的我们有
δs?(v)=∑t∈V∑w:v∈Ps(w)δst(v,{v,w})=∑w:v∈Ps(w)∑t∈Vδst(v,{v,w})
s→t的通过w的最短路径为σst(w)=σswσwt,而σst(v,{v,w})=σsvσwt
后者是因为从s→t经过v，(v,w)要先到达v,然后走(v,w),最后从w→t.
这里我们得到t≠w时
δst(v,{v,w})=σsvσswσst(w)σst
δst(v,{v,w})=σsvσsw
∑w:v∈Ps(w)∑t∈Vδst(v,{v,w})=∑w:v∈Ps(w)??σsvσsw+∑t∈V-{w}σsvσswσst(w)σst??=∑w:v∈Ps(w)σsvσsw(1+δs?(w))
至此计算就完毕了。
列举下主要计算步骤
选取源节点s做BFS计算σst
遍历过程中将节点推入栈中，同时保留每个节点作为其他节点前驱的集合。
用公式计算δs?(v)
import networkx as nx
from Queue import Queue
G = nx.random_graphs.barabasi_albert_graph(100,3)
C = nx.centrality.betweenness_centrality(G,normalized=False)
CB = dict.fromkeys(G,0.0)
for s in G.nodes():
Pred = {w:[] for
w in G.nodes()}
dist = dict.fromkeys(G,None)
sigma = dict.fromkeys(G,0.0)
dist[s] = 0
sigma[s] = 1
Q = Queue()
while not Q.empty():
v = Q.get()
S.append(v)
for w in G.neighbors(v):
if dist[w] == None:
dist[w] = dist[v] + 1
if dist[w] == dist[v] + 1:
sigma[w] += sigma[v]
Pred[w].append(v)
delta = dict.fromkeys(G,0.0)
for w in S[::-1]:
for v in Pred[w]:
delta[v] += sigma[v]/sigma[w]*(1+delta[w])
if w != s:
CB[w] += delta[w]
for v in CB:
CB[v] /= 2.0
print(sum(abs(CB[v]-C[v]) for v in G))
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：2171次
排名：千里之外[转载]Centrality　中心性&－&Node&centrality&in&w
(Centrality)中心性和中心性在带权网络上的推广
　　这两天从基础问题着手开始了解网络相关知识，百度的空间与Word的内容衔接真是太烂了，只能发链接了。链接位于hotmail的文档共享中。在链接中已有描述，下面只说在有权网络上的推广。
声明：英语以及专业水平不是一般地有限，翻译得不好随便喷，仅供个人参考。
　　无权网络中心性有三种：度中心性，紧密度中心性和介数中心性。
度&(degree)
　　无权网络　有连接的相邻结点的数目，结点i的度ki描述为：
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/c5f34df193c9&690"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
　　其中，i是中心结点，j表示所有其它结点，x是邻接矩阵，xij&=
1当且仅当结点i,&j有边相连。
　有权网络　与结点相连接边的强度之和，也被看作是点的强度：
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/c5f34df"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
　　其中，w是权重邻接矩阵，i,j之间有边相连时wij大于0，且表示权值。
　　结合结点强度与度　为了结合度和强度这两种反映网络的不同方式，引入了：
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/c5f34e07ee15&690"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
紧密度和介数
　　紧密度和介数都是基于最短路径的识别和路径长度的。最短路径可定义为：
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/c5f34e012a69&690"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
　　其中h是结点i到结点j的中间结点。
　　紧密中心度依赖于从一个结点出发到其它所有结点的最短路径长度，并被定义为总长度的倒数。介数依赖于识别最短路径，计算通过这一结点的最短路径数。
　　结点i的紧密中心度：
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/c5f34e01a72a&690"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
结点i的介数中心度：
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/c5f34e00be9d&690"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
gjk是0-1网络（就是无权网络，所有边权为1）的最短路径的数目，gjk(i)是其中通过结点i的最短路径的数目。
　　边权代表了结点之间的关系强度，强度越高，距离越近。这样重新定义最短路径为：
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/c5f34e06b3f4&690"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
结合路径中结点数的最短路径　
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/c5f34e"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
　　α&=&0时，上式与无权网络中的最短路径定义相一致；
　　0 &&α &
1时，中间结点作用增强，倾向于去寻找更短的路径；
　　α & 1时，中间结点的作用削弱，倾向于寻找更长的路径。
　　将修改的最短路径方法应用到介数和紧密度中可分别定义：
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/c5f34e"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
<img src="/blog7style/images/common/sg_trans.gif" real_src ="/middle/a31ee343f37&690"
ALT="[转载]Centrality　中心性&－&Node&centrality&in&w"
TITLE="[转载]Centrality　中心性&－&Node&centrality&in&w" />
　　Tore&Opsahl,&Filip&Agneessens,
John&Skvoretz, 2010. Node centrality in weighted
networks: Generalizing degree and shortest paths. Social Networks
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。您的位置： &
网络集聚性对节点中心性指标准确性的影响
优质期刊推荐