“集智百科精选”是一个长期专栏,持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目,集智百科希望打造复杂性科学领域最全面的百科全书,欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入!

本文是对集智百科中“介数中心性”词条的摘录,参考资料及相关词条请参阅百科词条原文。

本词条由集智俱乐部众包生产,难免存在纰漏和问题,欢迎大家留言反馈或者前往对应的百科词条页面进行修改,一经修改,可以获得对应的积分奖励噢!

目录

一、定义
二、真实网络和模型网络中的负荷分配
三、加权网络
四、渗流中心性
五、算法
、编者推荐
七、百科项目志愿者招募

根据每个顶点的介数中心性从最小(红色)到最大(蓝色)着色的无向图。


在图论中,介数中心性Betweenness centrality是基于最短路径的图中心性的一种度量。对于连通图中的每一对节点,在节点之间至少存在一条最短路径,使得路径通过的边数(对于未加权图)或者边权重的和(对于加权图)最小。节点的中心性是经过该节点的最短路径的数量。


介数中心性Betweenness centrality的提出为中心性的衡量提供了一般的标准: 它适用于网络理论中广泛的问题,包括与社会网络、生物学、交通和科学合作有关的问题。尽管早期的学者直观地将中心性描述为基于介数,但是给出了 介数中心性Betweenness centrality的第一个正式定义。


介数中心性Betweenness centrality在网络理论中有着广泛的应用,它代表了节点之间相互独立的程度。例如,在远程通信网络中,具有较高 介数中心性Betweenness centrality的节点将对网络有更多的控制,因为有更多的信息会通过该节点。


基于每个顶点从最小(红色)到最大(蓝色)的中间值的无向图。





定义



一个节点 v 的 介数中心性Betweenness centrality通过以下表达式给出:



其中 st 是从节点 s 到节点 t 的最短路径总数,st(v) 是其中通过节点v的路径数量。

注意,如公式中求和指标所示,一个节点的介数中心性与节点对的数量成比例缩放。因此,计算可以通过除以不包括 v 的节点对数来重新标定,使得g∈[0,1]。有向图是通过除以 (N-1)(N-2)来实现的,而无向图是通过除以 (N-1)(N-2)/2 来实现的,其中 n 是巨组元中的节点数。请注意,当每一条最短路径都通过一个节点时,这个节点达到可以缩放的最大可能值。事实往往并非如此,可以在不损失精度的情况下执行标准化



结果是:



请注意,这种方法将始终是从较小范围到较大范围的缩放,因此不会丢失精度。





真实网络和模型网络中的负荷分配



模型网络

γ为不同值时,无标度网络中负荷的幂律分布曲线.圆圈:γ=2.2,正方形:γ=2.5,钻石:γ=3.0,X:γ=4.0,三角形:γ=∞


结果表明,无标度网络的负荷分布遵循由负载指数δ所给出的幂律



这意味着缩放与节点度相关,



其中g (k) 是度为k的节点的平均负载。指数-δ和 η不是独立的,因为方程(1)指出


对于大 g,也就是大 k,表达式变成



证明了如下等式:



重要的指数是 η,它描述了介数中心性如何依赖于连通性。当所有的最短路径都经过一个节点时,这种情况使节点的介数中心性最大化,这对应于一个树结构(一个没有分簇的网络)。在树形网络的情况下,达到了  η= 2 的最大值。



η的最大值(也是 δ 的最小值)为具有 非零分簇Non-vanishing clustering的网络的负载指数设置了界限。



在这种情况下,指数 η,δ 并不是通用的,取决于不同的细节(平均连接性、相关性等)。


真实网络

现实世界中的 无标度网络,如互联网,也遵循幂律负载分布。[3] 这是一个直观的结果。无标度网络通过创建一些比大多数网络具有更高连通性的枢纽节点,从而在网络中实现较短的路径长度。由于这种额外的连接,这些枢纽节点自然会承担更高的负载。





加权网络



在加权网络中,连接节点的链路不再被视为二元的相互作用,而是根据其容量、影响力、频率等按比例加权,这在拓扑效应之外增加了网络内另一个异质性的维度。一个加权网络中的节点的强度是由其相邻边的权重之和来表示的。



用aij和wij分别作为i和j节点之间的邻接矩阵和权值矩阵。


类似于 无标度网络中度的幂律分布,节点的强度也服从 幂律分布。



对具有介数b的节点强度的平均值s(b)的研究表明,功能行为可以用缩放形式来近似。






渗流中心性



渗流中心性是加权的介数中心性Betweenness centrality的一种形式,但它在计算该权重时考虑了每条最短路径的源节点和目标节点的“状态”。在许多情况下,复杂网络中都会出现“传染”的渗流现象。例如,病毒或细菌感染可以通过人们的社交网络传播,也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题,设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下,一种“传染病”在一个复杂网络的链接上传播,随着它的传播,无论是可恢复的还是不可恢复的,都会改变节点的“状态”。例如,在流行病学情况下,随着传染病的扩散,个体从“易感”状态转变为“感染”状态。在上面的例子中,随着传染病的传播,每个节点的状态可以是二元的(如接收/没有接收到一条信息)、离散的(易感/受感染/康复),甚至是连续的(如一个城镇中受感染的人群比例)。这些情景的共同特点是,传染病的传播导致网络中节点状态的改变。渗流中心性Percolation centrality (PC)就是基于这个思想而提出的,它衡量了节点在帮助网络渗流方面的重要性。这个测度是由 Piraveenan 等人提出的。


渗流中心性Percolation centrality 定义了在给定时间内,通过一个给定节点的渗流路径的比例。“渗流路径”是一对节点之间的最短路径,其中源节点被渗流的(例如,被感染)。目标节点可以是渗流的或非渗流的,或处于部分渗流状态。



其中σsr是从节点s到节点r的最短路径总数,σsr(v)是通过v的路径数。在时间t时节点i的渗滤状态用xti表示,两个特殊情况是当xti=0表示在时间上是非渗滤状态,而当xti=1表示在时间上是完全渗滤状态。两者之间的值表示部分渗滤状态(例如,在一个城镇网络中,这是该城镇感染者的百分比)。


渗流路径的权重取决于分配给源节点的渗滤水平,前提是源节点的渗滤水平越高,源节点的路径就越重要。因此,位于源自高渗滤节点的最短路径上的节点可能对渗滤更为重要。PC 的定义也可以扩展到包括目标节点的权重。渗滤中心性计算运行在O(NM)时间,高效的实现采用了布兰德斯快速算法,如果计算需要考虑目标节点的权重,最坏情况下时间为O(N^3)。





算法




计算一个图中所有顶点的介数和紧密中心性Closeness centralities涉及到计算图中所有节点对之间的最短路径,使用 Floyd-Warshall 算法时,这需要big theta|



的时间复杂度,改进后的算法不仅可以找到一条路径,还可以计算两个节点之间的所有最短路径。在稀疏图上,Johnson算法或Brandes算法可能更有效率,两者的时间复杂度为Big O notation|



在未加权图上,使用 Brandes 算法计算 介数中心性Betweenness centrality需要的时间复杂度为Big O notation|



在计算一个图的所有节点的介数和紧密中心性Closeness centralities时,假定图是无向的,并且图在允许自环和多边时是连通的。当专门处理网络图时,图通常没有自环或多边来维持简单的关系(其中的边表示两个人或节点之间的联系)。在这种情况下,使用 Brandes 算法将最终的中心性除以2,因为每条最短路径被计算两次。


另一个算法通过引入一个超参数来控制勘探和开发之间的平衡,将计算测地线的弗里曼(Freeman)介数和所有路径上计算纽曼(Newman)介数的结果进行了推广。时间复杂度是图中的边数乘以节点数。


中心性的概念也扩展到了群体层次。群体介数中心性反映了通过一组节点连接非组成员节点对的测地线所占的比例。修改了计算所有节点之间的介数中心性的Brandes算法,以计算具有相同渐近运行时间的一组节点之间的群体介数中心性。





编者推荐



集智课程推荐

图网络算法原理探究——图网络读书会

https://campus.swarma.org/course/1167

本系列课程为图网络论文解读活动“算法原理探究”篇。


网络科学导论|网络科学集智课堂第二期

https://campus.swarma.org/course/2328

本期课程将围绕网络动力学这一前沿的方向,帮助大家构建网络科学学习体系。





百科项目志愿者招募




作为集智百科项目团队的成员,本文内容由水流心不竞翻译,Zcy审校,不是海绵宝宝编辑。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页,更多信息可以访问其集智百科个人主页。


以上内容都是我们做这项目的起点,作为来自不同学科和领域的志愿者,我们建立起一个有效的百科团队,分配有审校、翻译、编辑、宣传等工作。我们秉持:知识从我而来,问题到我为止的信念,认真负责编撰每一个词条。


在这里从复杂性知识出发与伙伴同行,同时我们希望有更多志愿者加入这个团队,使百科词条内容得到扩充,并为每位志愿者提供相应奖励与资源,建立个人主页与贡献记录,使其能够继续探索复杂世界。

如果你有意参与更加系统精细的分工,扫描二维码填写报名表,我们期待你的加入!



集智百科报名表


来源:集智百科

编辑:王建萍


推荐阅读



点击“阅读原文”,阅读词条介数中心性原文与参考文献