前言
边介数是运用GN算法求解的关键，通过不断删除边介数最高的边，才能最终生成分裂树。

那么，边介数怎么计算呢？

相信点进我这篇文的朋友们都是看过边介数计算公式的。

那么废话不多说，我直接上图解释吧。
流程
首先假设这里有个图，m个节点，n条边，我们先选节点s作为源节点，以s为源对图进行搜索，画出s到各个节点的最短路径树，假设最短路径树呈这个亚子：



然后我们把所有最邻近叶子结点的那条边标上1，再将其他边标上所有最邻近他的边之和+1，然后就成了这个样子：



这样，我们就有了在这个点作为源节点时的各边单次边介数。然后再换一个节点作为边节点，就有了如下图：



本次计算结果我标注了绿色，然后再按照这个方法，当遍历完所有节点（即所有节点都做过一次边节点）后，再将各边上每次求得的单次边介数累计求和，得到的就是最终该边边介数。
解释
从边介数定义开始讲吧。

大家都知道，边介数定义为从源节点到各节点最短路径中经过该边的路径数，那么就再回到先前的图：



在这张图中，源节点S到各节点都只有一条最短路径，那么我就借着这张图来解释一下：



可以看到，图中这条橙色的边单次边介数为2，而经过它的最短路径有两条。

如果这样还不够清晰，那么——



图中蓝色的边单次边介数为6，经过它的最短路径有6条，足够清楚了吧。
补充
先前有人问过我这个问题，他给我画了这么个图：



他在我给的示例图上添了这么一笔，然后问我这样怎么计算边介数呢？

自然是照常计算啊，添上这条边又不会造成其他边的变动（在还是S作为源节点的情况下），只是这条边上可以标个1罢了。

此外，还有一种情况，就是在这个连通图外还有单独两个连通节点的：



具体我就不详说了，直接看计算过程吧：



不同颜色代表将不同节点作为源节点时的计算结果。

复杂网络中心性
1. 度中心性（Degree Centrality）
2. 介数中心性（Betweenness Centrality）
3. 接近中心性（Closeness Centrality）

1. 度中心性（Degree Centrality）
度中心性（Degree Centrality）是在网络分析中刻画节点中心性（Centrality）的最直接度量指标。一个节点的节点度越大就意味着该节点的度中心性越高，该节点在网络中就越重要。
某个节点 度中心性 计算公式如下：

$DC_i=\frac{k_i}{N-1}$

其中：

$k_i$ 表示现有的与节点 $i$ 相连的边的数量
$N-1$ 表示节点 $i$ 与其他节点都相连的边的数量

例：                                    
2. 介数中心性（Betweenness Centrality）
节点介数是指一个网络里通过节点的最短路径条数
某个节点的 介数中心性 的计算公式如下：

$BC_i=\sum_{s\neq i\neq t}\frac{n^i_{st}}{g_{st}}$

其中：

$n^i_{st}$ 表示经过节点 $i$ ，且为最短路径的路径数量
$g_{st}$ 表示连接 $s$ 和 $t$ 的最短路径的数量

归一化（令结果 < 1）后，有：

$BC_i=\frac{1}{(N-1)(N-2)/2}\sum_{s\neq i\neq t}\frac{n^i_{st}}{g_{st}}$

例：                          
上图计算节点 $1$ 的介数中心性：

从 $5$ -> $4$ ，最短路径为 $(5,1,4)$， 该路径经过节点 $1$ ，所以 $n^1_{54}=1,g_{54}=1$
从 $5$ -> $3$ ，最短路径为 $(5,3)$， 该路径不经过节点 $1$，所以 $n^1_{53}=0,g_{53}=1$
从 $5$ -> $2$ ，最短路径为 $(5,1,2),(5,3,2)$， 经过节点 $1$ 的路径为 $(5,1,2)$，所以 $n^1_{52}=1,g_{52}=2$
从 $4$ -> $3$ ，最短路径为 $(4,1,2,3),(4,1,5,3)$， 两条路径都经过节点 $1$，所以 $n^1_{43}=2,g_{43}=2$
从 $4$ -> $2$ ，最短路径为 $(4,1,2)$， 该路径经过节点 $1$，所以 $n^1_{42}=1,g_{42}=1$
从 $3$ -> $2$ ，最短路径为 $(3,2)$， 该路径不经过节点 $1$，所以 $n^1_{32}=0,g_{32}=1$
最后得出 $B(1)=\frac{7}{2}$ ，对其归一化得 $B(1)=\frac{7}{12}$

3. 接近中心性（Closeness Centrality）
接近中心性用于衡量节点重要性
某个节点的 接近中心性 $CC_i$ 为：

$d_i=\frac{1}{N-1}\sum^{N}_{j=1}d_{ij} \quad \quad CC_i=\frac{1}{d_i}$

其中 $d_i$ 表示节点 $i$ 到其余各点的平均距离，平均距离的倒数就是接近中心度
例：                                             
以上图节点 $A$ 为例，图中点的个数 $N=11$：

与 $A$ 相连的路径为 $1$ 的共 $4$ 个点，为 $D,E,F,B$
与 $A$ 相连的路径为 $2$ 的共 $3$ 个点，为 $G.C,H$
与 $A$ 相连的路径为 $3$ 的共 $3$ 个点，为 $I,J,K$
可得 $A$ 的平均距离为 $d(A)=\frac{1}{10}(4+2 *3+3*3)$，$A$ 的接近中心度为 $CC(A)=\frac{1}{d(A)}$

文件名称: matlab-bgl-master下载  收藏√  [
 5  4  3  2  1 ]
开发工具: matlab
文件大小: 982 KB
上传时间: 2016-06-27
下载次数: 0
提 供 者: 陈娟
详细说明：复杂网络工具包,便于计算复杂网络边介数，最短路径等问题-Complex Network Kit
文件列表(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
matlab-bgl-master\.bzrignore
.................\.gitignore
.................\.project
.................\@inplace\assign.m
.................\........\display.m
.................\........\double.m
.................\........\end.m
.................\........\inplace.m
.................\........\size.m
.................\........\subsasgn.m
.................\........\subsref.m
.................\..pdouble\ipdouble.m
.................\...int32\ipint32.m
.................\addpath_mbgl_custom.m
.................\all_shortest_paths.m
.................\astar_search.m
.................\bellman_ford_sp.m
.................\betweenness_centrality.m
.................\bfs.m
.................\biconnected_components.m
.................\boyer_myrvold_planarity_test.m
.................\breadth_first_search.m
.................\chrobak_payne_straight_line_drawing.m
.................\circle_graph_layout.m
.................\clique_graph.m
.................\clustering_coefficients.m
.................\combine_visitors.m
.................\components.m
.................\Contents.m
.................\core_numbers.m
.................\.ustom\better_er.m
.................\......\dijkstra_all_sp.m
.................\......\flow_improve.m
.................\......\matching_dmperm.m
.................\......\path_histogram.m
.................\......\randgeom.m
.................\cycle_graph.m
.................\dag_sp.m
.................\depth_first_search.m
.................\dfs.m
.................\dijkstra_sp.m
.................\.oc\changed.txt
.................\...\fileexchange.doc
.................\...\html\changes.html
.................\...\....\faq.html
.................\...\....\images\matlab-bgl-header.png
.................\...\....\......\Thumbs.db
.................\...\....\index.html
.................\...\....\old.html
.................\...\....\site.css
.................\...\....\style.css
.................\...\Matlab BGL.doc
.................\...\mxdom2mbgl-html.xsl
.................\...\tex\bfs_example.gif
.................\...\...\bfs_example.PNG
.................\...\...\bfs_treeplot.png
.................\...\...\dfs.gif
.................\...\...\dfs.PNG
.................\...\...\digraph.gif
.................\...\...\digraph.PNG
.................\...\...\matlab-bgl-tex-ref-2.0.tex
.................\...\...\matlab-bgl-tex-ref-2.1.tex
.................\...\...\matlab-bgl-tex-ref.tex
.................\...\...\matlab_bgl_v1.0.tex
.................\...\...\matlab_bgl_v2.0.tex
.................\...\...\matlab_bgl_v2.1.tex
.................\...\...\matlab_bgl_v3.0.tex
.................\...\...\max-flow.gif
.................\...\...\max-flow.PNG
.................\...\...\multiway_cut-large.emf
.................\...\...\multiway_cut-large.eps
.................\...\...\multiway_cut-large.png
.................\...\...\multiway_cut.emf
.................\...\...\multiway_cut.eps
.................\...\...\multiway_cut.png
.................\...\...\shading.sty
.................\...\...\undigraph.gif
.................\...\...\undigraph.PNG
.................\...\...\write_latex_ref.m
.................\...\write_examples_html.m
.................\...\~$tlab BGL.doc
.................\edge_weight_index.m
.................\edge_weight_vector.m
.................\edmonds_maximum_cardinality_matching.m
.................\edmunds_karp_max_flow.m
.................\erdos_reyni.m
.................\.xamples\approx_multiway_cut.m
.................\........\bacon_numbers.m
.................\........\bfs_example.m
.................\........\bfs_in_mbgl.m
.................\........\bfs_in_mbgl_efficient.m
.................\........\core_numbers_example.m
.................\........\dfs_example.m
.................\........\edge_index_example.m
.................\........\flow_improve_example.m
.................\........\flow_improve_example_live.m
.................\........\max_flow_example.m
.................\........\multiway_example.m
.................\........\new_in_3_0.m
.................\........\new_in_4_0.m
输入关键字，在本站261万海量源码库中尽情搜索：
帮助

网络节点的重要性指标介数中心性的计算，使用python的networkx包


import networkx as nx

G = nx.Graph()

# 从文件@filename中读取网络的adjacentMatrix，通过networkx的add_edges方法向对象G中添加边
def readNetwork(filename):
	fin = open(filename, 'r')
	# for line in fin:
	# 	for node in line:
	# 		print(node, end="")
			
	# lines = fin.readlines()
	# print(len(lines))

	rowCount = 1;
	colCount = 1;
	for line in fin.readlines():
		line = line.split(" ")
		for node in line:
			if node == '1':
				G.add_edge(rowCount, colCount)
			colCount = colCount + 1
		colCount = 1
		rowCount += 1

	print(G.edges())

# 计算网络中的节点的介数中心性，并进行排序输出
def topNBetweeness():
	score = nx.betweenness_centrality(G)
	score = sorted(score.items(), key=lambda item:item[1], reverse = True)
	print("betweenness_centrality: ", score)
	output = []
	for node in score:
		output.append(node[0])

	print(output)
	fout = open("betweennessSorted.data", 'w')
	for target in output:
		fout.write(str(target)+" ")

readNetwork("sf100.data")
topNBetweeness()