Betweenness Centrality的计算方法 |
您所在的位置:网站首页 › 介数是什么意思 › Betweenness Centrality的计算方法 |
Betweenness Centrality的计算方法
Betweenness Centrality也称为中介中心性。 Betweenness Centrality的计算公式为: 前面的 g ( v ) g(v) g(v)代表顶点v的Betweenness Centrality值。 σ s t ( v ) \sigma_{st}(v) σst(v)代表从顶点s到顶点t之间经过v的最短路径数。 σ s t \sigma_{st} σst代表从顶点s到顶点t之间所有的最短路径数。 注意: 如果s,t之间有最短路径,但是没有最短路径经过v,则 σ s t ( v ) = 0 \sigma_{st}(v)=0 σst(v)=0,则不论 σ s t \sigma_{st} σst的值是什么,结果都是0.所以我们只查找 σ s t ( v ) ! = 0 \sigma_{st}(v)!=0 σst(v)!=0的路径,再找到st之间的所有路径,两个路径的数量相除,就是st对v的贡献值。 举例计算Betweenness Centrality以上图为例,图中有6个顶点,8条边。 A的Betweenness Centrality的值为0因为所有顶点之间的最短路径都不经过A。 B的Betweenness Centrality的值为8因为有以下路径经过B。 从A出发的最短路径和从A出发的经过B的最短路径条数一致,都是是5,路径如下: ABD ABC ABDE ABDF ABCE则从A出发的顶点的对B的贡献为1/1 + 1/1 + 1/1 + 2/2 = 4(因为ABDE和ABCE起始点和终点相同) 没有从B出发的经过B最短路径。 从C出发的经过B的最短路径条数是1,路径如下: CBACA之间的最短路径为 CBA则从C出发的顶点的对B的贡献为1/1 = 1 从D出发的经过B的最短路径条数是1,路径如下: DBADA之间的最短路径为 DBA则从D出发的顶点的对B的贡献为1/1 = 1 从E出发的经过B的最短路径条数是2,路径如下: ECBA EDBAEA之间的最短路径为 ECBA EDBA则从E出发的顶点的对B的贡献为2/2=1 从F出发的经过B的最短路径条数是1,路径如下: FDBAFA之间的最短路径为 FDBA则从F出发的顶点的对B的贡献为1/1=1 所以B的Betweenness Centrality是8. C的Betweenness Centrality的值为2因为有以下路径经过C。 从A出发的经过C的最短路径条数是1,路径如下: ABCEAE之间的最短路径为 ABCE ABDE则从A出发的顶点的对C的贡献为0.5 从B出发的经过C的最短路径条数是1,路径如下: BCEBE之间的最短路径为 BCE BDE则从B出发的顶点的对B的贡献为1/2 = 0.5 从C出发的最短路径经过C的是0. 从D出发的经过C的最短路径条数是0 从E出发的经过C的最短路径条数是2,路径如下: ECB ECBA之间的最短路径为 ECB EDB之间的最短路径为 ECBA EDBA则从E出发的顶点的对B的贡献为1/2+1/2=1 从F出发的经过C的最短路径条数是0 D的Betweenness Centrality的值为7因为有以下路径经D。 从A出发的经过D的最短路径条数是2,路径如下: ABDF ABDE之间的最短路径为 ABCE ABDE之间的最短路径为: ABDF则从A出发的顶点的对D的贡献为1/2 + 1 = 1.5 从B出发的经过D的最短路径条数是2,路径如下: BDF BDEBF之间的最短路径为 BDFBE之间的最短路径为 BCE BDE则从B出发的顶点的对D的贡献为1/1 + 1/2 = 1.5 从C出发的经过D的最短路径条数是1,路径如下: CDFCF之间的最短路径为 CEF CDF则从C出发的顶点的对D的贡献为1/2 = 0.5 从D出发的经过D的最短路径条数是0 从E出发的经过D的最短路径条数是2,路径如下: EDB EDBAEB之间的最短路径为 ECB EDBEA之间的最短路径为 ECBA EDBA**则从E出发的顶点的对D的贡献为1/2 + 1/2 = 1 ** 从F出发的经过D的最短路径条数是3,路径如下: FDB FDBA FECFB之间的最短路径为 FDBFA之间的最短路径为 FDBAFC之间的最短路径为 FEC FDC**则从F出发的顶点的对D的贡献为1/1 + 1/1 + 1/2 =2.5 ** E的Betweenness Centrality的值为1因为有以下路径经E。 从A出发的经过E的最短路径条数是0. 从B出发的经过E的最短路径条数是0. 从C出发的经过E的最短路径条数是1,路径如下: CEFCF之间的最短路径为 CEF CDF**则从C出发的顶点的对E的贡献为 1/2 =0.5 ** 从D出发的经过E的最短路径条数是0. 从E出发的经过D的最短路径条数是0 从F出发的经过D的最短路径条数是1,路径如下: FECFC之间的最短路径为 FEC FDC F的Betweenness Centrality的值为0因为没有任何最短路径经过F。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |