量化一个节点在网络中的重要性:中心度(centrality)

中心度(centrality)是用来量化一个顶点在图中的重要性,同样地,中心度也可以用来量化一个节点在网络中的重要性。本文分别介绍以社会为中心的网络(sociocentric network)和以自我为中心的网络(egocentric network)的中心度指标,即degree, closeness和betweenness,并分析在实际网络中如何选择合适指标。

1. sociocentric网络的中心度

早在1978年,L.C. Freeman就提出用degree,closeness,betweenness指标衡量社交网络的中心度,这三个指标也可用于衡量网络的中心度。

1.1 Degree centrality

用顶点的度表示Degree centrality,度高的节点(比如基站,无线网络中的接入点)更容易充当信息交换的角色。公式如下[3]

clip_image002[6]

1.2 Closeness centrality

节点接近程度(Closeness centrality),可以用节点间距离(geodesic distance,两个顶点之间最短路径中所包含边的数目)来表征。比如,一个节点到其他节点的最短路径都很短,那么该节点的Closeness就高。这个指标可以用来衡量信息从该节点传输到其他节点的时间长短。将一个节点到所有其他节点的最短距离累加起来取倒数,即为Closeness centrality。公式如下[3]

clip_image002[8]

1.3 Betweenness centrality

一个节点如果经常出现在其他节点间最短距离路径中(即最短距离的路径经常包含该节点),那么说明该节点更有能力促进其他节点间通信。计算公式如下,分母表示所有节点间最短路径的数目累加,分子表示所有节点间最短路径(该路径包含节点pi),的数目累加。公式如下[3]

clip_image002[10]

2. 自我网络的中心度

自我网络(ego network)可以看做是sociocentric网络的一个子图(局部与全局),节点包括一个中心节点(ego)和其邻居节点(alters),那么边就只有ego与alters之间和alters与alters之间。举例如下[5]

ego network

图1 自我网络示例

2.1 Degree centrality

跟sociocentric网络一样,自我网络(ego network)也是用顶点的度表示Degree centrality。

2.2 Closeness centrality

节点接近程度(Closeness centrality)在自我网络中是没有意义的,因为ego节点到alters节点距离都是1。

2.3 Betweenness centrality

跟sociocentric网络算法一样,但ego网络有一点比较特殊,即任意两个节点的最短距离只能是0或1。通过以下公式[3]可以求出Betweenness centrality(我没看懂,1-A是什么意思,求指点),A是网络的邻接矩阵:

clip_image002[12]

尽管sociocentric和egocentric网络算出求的betweenness centrality不是很对应,但他们的排序是一样的。举例如下[3]

image

图2 sociocentric和egocentric网络中心度对比

3. 中心度指标选择

3.1 sociocentric vs egocentric

sociocentric网络注重研究网络的整体,egocentric网络注重研究个体的性质。sociocentric网络需要知道整个网络的拓扑结果,这在动态网络(如DTN)几乎不可能,所以通常选择自我网络(ego network)作为研究对象。

3.2 degree vs betweenness

我看的论文并没有指出用degree有什么不足,但说了closeness和betweenness 是信息传输最合适的指标[3]。

3.3 其他

如果只是单纯依靠中心度来判断信息路由,存在以下两个不足:
(1)造成中心节点严重拥塞
(2)没有考虑链接的强度
可见,设计路由策略,只有中心度是不够的,还需要衡量链接强度,甚至预测链接。除此之外,中心度的指标也可以根据实际应用改进设计。

 

参考资料:

[1] L.C. Freeman, “A Set of Measures of Centrality Based on Betweenness,” Sociometry, vol. 40, no. 1, pp. 35-41, Mar. 1977.
[2] L.C. Freeman, “Centrality in Social Networks Conceptual Clarification,” Social Networks, vol. 1, no. 3, pp. 215-239, 1978-1979.
[3] E. Daly and M. Haahr, “Social Network Analysis for Information Flow in Disconnected Delay-Tolerant MANETs,” IEEE Trans. Mobile Computing, vol. 8, no. 5, May 2009, pp. 606–21
[4] M. Everett and S.P. Borgatti, “Ego Network Betweenness,” Social Networks, vol. 27, no. 1, pp. 31-38, Jan. 2005
[5] 图片来源:http://www.analytictech.com/networks/egonet.htm

Leave a Reply

Your email address will not be published. Required fields are marked *