论文发表、论文指导
周一至周五
9：00&22：00
浅议几种复杂网络节点重要度分析的中心性方法
　　摘要：网络节点重要度分析是研究和分析复杂网络的一种非常重要的方法。识别有影响力的节点比较常用的是利用中心性方法解决这个问题。本文介绍了几种常见的进行网络节点重要度分析的中心性方法，并通过实例对几种中心性方法进行了分析比较。 中国论文网 /7/view-7371694.htm　　Abstract： To study and analyze complex networks， identifying influential nodes is a very important methodology. Many centrality measures have been proposed to address this issue. In this paper， centrality measures to identify influential nodes in complex networks are described. Numerical examples show the analysis and comparison of several methods to identify influential nodes. 　　关键词：复杂网络；重要节点；中心性方法 　　Key words： complex networks；identify influential nodes；centrality measures 　　中图分类号：TN711 文献标识码：A 文章编号：（9-02 　　0 引言 　　当前，从疾病传播网络到全球医疗诊断网络，从电力网到交通网络，从交际网络到社会关系网络，复杂网络已经渗透到人类社会生活，给我们带来了极大的便利，但是，同时也产生了诸如交通瘫痪、谣言快速传播等不容忽视的负面冲击。因此，对复杂网络进行深入的研究和分析以方便对其负面影响进行预测、避免和控制是刻不容缓的。由于网络中的节点存在着许多的全局信息和局部信息，因此对有影响力节点的识别即节点重要度分析是一个非常重要的方向，在许多领域也得到了广泛的应用，如攻击防御、谣言传播控制、搜索排名等。目前，已提出多种复杂网络节点中心性方法解决节点重要度分析问题。本文介绍了几种常见的进行网络节点重要度分析的中心性，并通过算例对几种方法进行了分析比较。 　　1 基本理论 　　复杂网络是由数量巨大的节点和节点之间错综复杂的关系共同构成的网络结构，在数学上可以抽象为一个由点集V和边集E组成的图G=（V，E）。如图1所示，是具有11个节点12条边的简单无向无权网络图。为简化问题，本文仅针对无向无权网络进行研究。 　　2 节点重要度分析方法 　　所谓的重要节点是指与网络其他节点相比，能在更大程度上影响网络的结构与功能的一些比较特殊的节点。一般而言，一个网络中的重要节点的数量都是比较少的，但其影响却可以快速地波及到网络中的大部分节点[1]。为了解决识别网络节点重要度问题，已有多种不同的网络节点中心性方法。各种方法利用计算出的中心性值进行排序，确定节点重要程度。 　　2.1 度中心性（Degree centrality measure） 　　节点i的度中心性[2]，用CD（i）表示，定义为： 　　其中i为当前所求节点，j表示其他所有的节点，N是网络节点总数，xij表示i与j之间有连接关系。两个节点之间相连，则为1，反之则为0。 　　2.2 介数中心性（Betweenness centrality measure） 　　节点i的介数中心性[3]，用CB（i）表示，定义为： 　　其中gst表示从节点s到节点t的最短路径的数目，gst（i）表示从节点s到节点t所有最短路径中经过节点i的最短路径的数目，是用来对介数中心性值进行归一化，n为网络节点的数目。 　　其中表示节点i和节点j之间的最短距离dij，其定义如下： 　　d（i，j）=min（xih+…+xhj）（3） 　　2.3 接近中心性（Closeness centrality measure） 　　节点i的接近中心性[3]，用CC （i）表示，定义为： 　　2.4 融合中心性（Compromise centrality measure） 　　节点i的融合中心性[8]，用CED（i）表示。其来源于对度中心性、接近中心性和介数中心性的值的融合计算，具体计算方法步骤如下： 　　①设CD（i），CC （i）和CB （i）分别为节点i的度中心性、接近中心性和介数中心性的值，分别进行归一化，计算方法为： 　　其中i表示节点i的归一化中心值，N为复杂网络节点数。 　　②然后整合节点i的归一化中心值，得到CED（i）。设分别为别为节点i的度中心性、接近中心性和介数中心性归一化中心值。利用欧拉公式得到的融合中心性的值定义为： 　　其中n为网络节点的数目。 　　2.5 TOPSIS中心性（TOPSIS centrality measure） 　　节点i的TOPSIS中心性[7]，用CTC（i），是利用度中心性、接近中心性和介数中心性的值结合逼近最优解的偏好顺序法（TOPSIS）的方法，具体计算方法如下： 　　①计算出各节点度中心性、接近中心性和介数中心性的值，并利用公式（5）进行归一化，再进行加权计算，得到加权归一化值； 　　②计算理想最优解A+和最劣解A-，具体说就是步骤二中的最大值和最小值； 　　③根据公式（7）计算节点与理想最优解和最劣解之间的相似紧密度即节点i的TOPSIS中心性值。 　　CTC（i）=， i=1，…，m（7） 　　其中S和S分别表示节点i与理想最优解和最劣解之间的距离。
　　3 算例 　　如图1为有11个节点，12条边的无向无权网络。利用前述各中心性定义，分别计算复杂网络所有节点的度中心性、接近中心性和介数中心性、融合中心性和TOPSIS中心性的值，其中计算TOPSIS中心性时假定权重都相等，即都为，计算结果如表1所示。 　　从表1可知，根据度中心性，各节点的重要度排序结果为：4、7>5、6>1、10>2、3、8、9、11；根据接近中心性，各节点的重要度排序结果为：6>5>7>10>4>1>11、9、8>3、2；根据介数中心性，各节点的重要度排序结果为：6>7>5>4>10>1>2、3、8、9、11；根据融合中心性，各节点的重要度排序结果为：7>6>4>5>10>1>8、9、11>2、3；根据TOPSIS中心性，各节点的重要度排序结果为：7>6>4>5>10>1>8、9、11>2、3。 　　4 结论 　　本文介绍了几种常见的进行网络节点重要度分析的中心性方法，并通过实例对几种中心性方法进行了分析比较。使用不同的中心性方法，可以得到不同的节点重要度结果。度中心性是在网络分析中刻画节点中心性的最直接度量指标，一个节点的节点度越大就意味着这个节点的度中心性越高，该节点在网络中就越重要。接近中心性是刻画节点通过网络到达其它节点难易程度的指标，相比节点度指标更能反映网络的全局结构。节点的接近度越高，那么离其它节点越近，传播难度越低，所需借助的节点越少，反之亦然。网络上传输时负载最重的节点是处于网络中心位置的节点，也就是经过此点的最短路径条数最多的节点。一个节点的介数越高，该节点在网络中就越重要。融合中心性和TOPSIS中心性是考虑前三种中心性进行综合处理所得，能更有效地识别复杂网络节点重要度。 　　参考文献： 　　[1]StefnaniaVtali，James B Glattfelder， and Stefano Battiston. The networkof global corporate control. PloS One， 6（10）：e. 　　[2]Phillip Bonacich. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Socioogy. ）：113-120. 　　[3]Liton C Freeman. Centrality in social networks conceptual clarification[J]. Social networks， ）：215-239. 　　[4]Zhang， Tingping， Liang， Xinyu， A Novel Method of Identifying Influential Nodes in Complex Networks Based on Random Walks Journal of Information and Computational Science， v 11， n 18， p ， December 10， 2014. 　　[5]Tingping Zhang， Bin Fang， and XinyuLiang ，A novel measure to identify influential nodes in complex networks based on network global efficiency[J]. Modern Physics Letters B， ）. 　　[6]杜雨弦.复杂网络中节点重要度评估算法的研究[D].重庆：西南大学，2015. 　　[7]张廷萍.一种新的复杂网络节点重要度分析方法[J].赤峰学院学报（自然科学版），2016（8）.
转载请注明来源。原文地址：
【xzbu】郑重声明：本网站资源、信息来源于网络，完全免费共享，仅供学习和研究使用，版权和著作权归原作者所有，如有不愿意被转载的情况，请通知我们删除已转载的信息。
xzbu发布此信息目的在于传播更多信息，与本网站立场无关。xzbu不保证该信息（包括但不限于文字、数据及图表）准确性、真实性、完整性等。【图文】网络中节点重要性评价_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&10W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
网络中节点重要性评价
阅读已结束，下载本文到电脑
定制HR最喜欢的简历
你可能喜欢【图文】社会网络分析_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&10W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
社会网络分析
阅读已结束，下载本文到电脑
定制HR最喜欢的简历
你可能喜欢【图文】社会网络分析_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&10W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
社会网络分析
阅读已结束，下载本文到电脑
定制HR最喜欢的简历
你可能喜欢NetworkX是一个用Python语言开发的图论与复杂网络建模工具，内置了常用的图与复杂网络分析算法，可以方便的进行复杂网络数据分析、仿真建模等工作。networkx支持创建简单无向图、有向图和多重图（multigraph）；内置许多标准的图论算法，节点可为任意数据；支持任意的边值维度，功能丰富，简单易用。
import networkx as nx
#!-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
#建立一个空的无向图G
G.add_node(1)
#添加一个节点1
G.add_edge(2,3)
#添加一条边2-3（隐含着添加了两个节点2、3）
G.add_edge(3,2)
#对于无向图，边3-2与边2-3被认为是一条边
print "nodes:", G.nodes()
#输出全部的节点： [1, 2, 3]
print "edges:", G.edges()
#输出全部的边：[(2, 3)]
print "number of edges:", G.number_of_edges()
#输出边的数量：1
nx.draw(G)
plt.savefig("wuxiangtu.png")
plt.show()
nodes: [1, 2, 3]
edges: [(2, 3)]
number of edges: 1
#-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_nodes_from([3,4,5,6])
G.add_cycle([1,2,3,4])
G.add_edge(1,3)
G.add_edges_from([(3,5),(3,6),(6,7)])
nx.draw(G)
plt.savefig("youxiangtu.png")
plt.show()
#!-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_nodes_from([3,4,5,6])
G.add_cycle([1,2,3,4])
G.add_edge(1,3)
G.add_edges_from([(3,5),(3,6),(6,7)])
nx.draw(G)
plt.savefig("youxiangtu.png")
plt.show()
注：有向图和无向图可以互相转换，使用函数：
Graph.to_undirected()
Graph.to_directed()
例2，例子中把有向图转化为无向图：
#!-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_nodes_from([3,4,5,6])
G.add_cycle([1,2,3,4])
G.add_edge(1,3)
G.add_edges_from([(3,5),(3,6),(6,7)])
G = G.to_undirected()
nx.draw(G)
plt.savefig("wuxiangtu.png")
plt.show()
注意区分以下2例
#-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
road_nodes = {'a': 1, 'b': 2, 'c': 3}
#road_nodes = {'a':{1:1}, 'b':{2:2}, 'c':{3:3}}
road_edges = [('a', 'b'), ('b', 'c')]
G.add_nodes_from(road_nodes.iteritems())
G.add_edges_from(road_edges)
nx.draw(G)
plt.savefig("youxiangtu.png")
plt.show()
#-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
#road_nodes = {'a': 1, 'b': 2, 'c': 3}
road_nodes = {'a':{1:1}, 'b':{2:2}, 'c':{3:3}}
road_edges = [('a', 'b'), ('b', 'c')]
G.add_nodes_from(road_nodes.iteritems())
G.add_edges_from(road_edges)
nx.draw(G)
plt.savefig("youxiangtu.png")
plt.show()
有向图和无向图都可以给边赋予权重，用到的方法是add_weighted_edges_from，它接受1个或多个三元组[u,v,w]作为参数，其中u是起点，v是终点，w是权重。
#!-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
#建立一个空的无向图G
G.add_edge(2,3)
#添加一条边2-3（隐含着添加了两个节点2、3）
G.add_weighted_edges_from([(3, 4, 3.5),(3, 5, 7.0)])
#对于无向图，边3-2与边2-3被认为是一条边
print G.get_edge_data(2, 3)
print G.get_edge_data(3, 4)
print G.get_edge_data(3, 5)
nx.draw(G)
plt.savefig("wuxiangtu.png")
plt.show()
{'weight': 3.5}
{'weight': 7.0}
经典图论算法计算
计算1：求无向图的任意两点间的最短路径
# -*- coding: cp936 -*-
import networkx as nx
import matplotlib.pyplot as plt
#计算1：求无向图的任意两点间的最短路径
G = nx.Graph()
G.add_edges_from([(1,2),(1,3),(1,4),(1,5),(4,5),(4,6),(5,6)])
path = nx.all_pairs_shortest_path(G)
print path[1]
计算2：找图中两个点的最短路径
import networkx as nx
G=nx.Graph()
G.add_nodes_from([1,2,3,4])
G.add_edge(1,2)
G.add_edge(3,4)
n=nx.shortest_path_length(G,1,4)
except nx.NetworkXNoPath:
print 'No path'
强连通、弱连通
强连通：有向图中任意两点v1、v2间存在v1到v2的路径（path）及v2到v1的路径。
弱联通：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。
例1：弱连通
#-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
#G = nx.path_graph(4, create_using=nx.Graph())
G = nx.path_graph(4, create_using=nx.DiGraph())
#默认生成节点0 1 2 3，生成有向变0-&1,1-&2,2-&3
G.add_path([7, 8, 3])
#生成有向边：7-&8-&3
for c in nx.weakly_connected_components(G):
print [len(c) for c in sorted(nx.weakly_connected_components(G), key=len, reverse=True)]
nx.draw(G)
plt.savefig("youxiangtu.png")
plt.show()
set([0, 1, 2, 3, 7, 8])
例2：强连通
#-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
#G = nx.path_graph(4, create_using=nx.Graph())
G = nx.path_graph(4, create_using=nx.DiGraph())
G.add_path([3, 8, 1])
#for c in nx.strongly_connected_components(G):
#print [len(c) for c in sorted(nx.strongly_connected_components(G), key=len, reverse=True)]
con = nx.strongly_connected_components(G)
print type(con)
print list(con)
nx.draw(G)
plt.savefig("youxiangtu.png")
plt.show()
&generator object strongly_connected_components at 0xAA1D80&
&type 'generator'&
[set([8, 1, 2, 3]), set([0])]
#-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
G.add_path([5, 6, 7, 8])
sub_graph = G.subgraph([5, 6, 8])
#sub_graph = G.subgraph((5, 6, 8))
nx.draw(sub_graph)
plt.savefig("youxiangtu.png")
plt.show()
#-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
road_nodes = {'a':{'id':1}, 'b':{'id':1}, 'c':{'id':3}, 'd':{'id':4}}
road_edges = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'd')]
G.add_nodes_from(road_nodes)
G.add_edges_from(road_edges)
nx.draw(G)
plt.savefig("youxiangtu.png")
plt.show()
#-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
def flt_func_draw():
flt_func = lambda d: d['id'] != 1
return flt_func
road_nodes = {'a':{'id':1}, 'b':{'id':1}, 'c':{'id':3}, 'd':{'id':4}}
road_edges = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'd')]
G.add_nodes_from(road_nodes.iteritems())
G.add_edges_from(road_edges)
flt_func = flt_func_draw()
part_G = G.subgraph(n for n, d in G.nodes_iter(data=True) if flt_func(d))
nx.draw(part_G)
plt.savefig("youxiangtu.png")
plt.show()
pred，succ
#-*- coding:utf8-*-
import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
road_nodes = {'a':{'id':1}, 'b':{'id':1}, 'c':{'id':3}}
road_edges = [('a', 'b'), ('a', 'c'), ('c', 'd')]
G.add_nodes_from(road_nodes.iteritems())
G.add_edges_from(road_edges)
print G.nodes()
print G.edges()
print "a's pred ", G.pred['a']
print "b's pred ", G.pred['b']
print "c's pred ", G.pred['c']
print "d's pred ", G.pred['d']
print "a's succ ", G.succ['a']
print "b's succ ", G.succ['b']
print "c's succ ", G.succ['c']
print "d's succ ", G.succ['d']
nx.draw(G)
plt.savefig("wuxiangtu.png")
plt.draw()
['a', 'c', 'b', 'd']
[('a', 'c'), ('a', 'b'), ('c', 'd')]
{'c': {}, 'b': {}}
阅读(...) 评论()}