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

1. sociocentric网络的中心度

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

1.1 Degree centrality

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

1.2 Closeness centrality

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

1.3 Betweenness centrality

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

2. 自我网络的中心度

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

图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是网络的邻接矩阵：

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

图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

赞赏

微信赞赏支付宝赞赏