在一个网络中，不同的节点起着大小不同的作用。以社交网络为例，有意见领袖的大V，有死寂沉沉的僵尸粉；以交通网络为例，有至关重要的交通枢纽，有无关痛痒的备用中转站。在使用复杂网络分析业务问题时，如何区分网络中不同节点的重要性程度，就是一个需要考虑的问题。为了解决我们自己的业务问题，顺便了解了一下相关的方法，特记录一下，若有益于相关领域的同学，则幸甚。

    一、要实现的目标

    对网络中的节点定义一个指标，可用来定量地衡量每个节点在网络中重要性的大小。

    二、相关的一些方法总结

    分析节点的重要性，业界较多地从网络拓扑结构出发，也有考虑传播动力学视角的【1】。菜鸟新上路，咱们先了解常用的一些方法即可。

• 局部特征

          节点度  这恐怕是常简单也最多使用的一个指标了。表示与节点所直接连接的边的数量，对于有向图，又分入度与出度。对于节点i, 对于图G中的节点j, 当i与j存在边相连时， a(i,j)=1，否则a(i,j)=0. 那么，节点i的度可以如下计算：

这个定义既直观又实用。但是也确实存在一定不足。比如下图中节点2与节点4的度都是3，它们的重用性真是相同的吗？ 如果我们从网络连接密切程度来看，2的邻居节点1，3，6之间存在较多的边，它们共同形成了一个较紧密的小圈子。而4的邻居3，5，8之间并无边相连。那么从连接紧密性的角度，我们倾向于认为2更重要。但是，可以发现4是通往7，8，9，10的一个必经之地，如果破坏了4，那么这个图就不连通了。这时我们会倾向于认为4更重要。所以，如果能在考虑节点度时，同时引入一些其它信息，则更加妥当。

          在Spark的Graphx中，建立Graph对象后，直接调用 .degrees 即可得到节点度的值。

          集聚系数 上面我们有涉及到紧密性的一个说法，那么，在图论中，有一个指标可以衡量这种属性，就是集聚系数(clustering coefficient)。有局部集聚系数，也有全局集聚系数。对于节点i, 它的邻居节点N(i)之间所存在的边数，与可能存在的最大边数的比值，就叫节点i的局部集聚系数。网络的全局集聚系数就是所有节点的集聚系数求平均值。

不要小看这个指标，它在评估一个网络是否可以称为小世界网络时，具有重要意义。

      在Graphx中，可以直接用 .triangleCount 来获得邻居节点之间实际存在的边数，再除以上式分母上的值，即可。

文章【2】【3】就是在度的基础上，增加了这个系数的因素来作为衡量节点重要性的评价方法。文章【2】的方法：

其中f是节点与其邻居度数之和，g是一个标准化后的指标，具体参考该文即可。俺觉得这个真心有点复杂啊，文章也没有讲清楚为啥一定要这样搞。相比之下，文章【3】就轻便多了，直接把度数与集聚系数作了一下加权，如下：

为了简便，我们这边目前采用了类似于文章【3】的方法。后面有精力再尝试更复杂的方法。

• 全局特征

     可以看出来，上面讨论的方法仅考虑节点i及其邻居的信息，属于局部性质的指标。 我们再看下有哪些全局特征可以用。但要注意的是，全局指标往往涉及到网络整体的计算，对于我厂这样大规模的网络数据，计算复杂度不得不考虑。

     特征向量法  上面讨论节点度时，默认所有邻居具有同等重要性，但现实中，如果总办领导们是你有且仅有的朋友，而我即便认识鹅厂其余人当中的1W人，恐怕你也比我更重要。即是说，邻居节点本身的重要性会影响所评价节点的重要性。其实，这个也是我们自己的业务场景中期望能考虑进来的一个因素。该指标计算公式如下（相当于对邻居节点的重要性作了线性加权，而加权权重是图G的邻接矩阵的特征向量）：

    中心度   一个点如果到其它所有点的最短路径越小，则该点就越居于网络的中心位置。计算方法如下所示，其中di,j 表示i到j的最短路径长度。把分子N-1放到分母上，就相当于是所有最短路径的平均值。这个定义还是蛮直观的吧，但感觉计算量肯定不小啊。

    点介数    我们这样想吧，如果一个网络中80%的最短路径都经过点i， 那i 是不是很重要？这种点就是重要“交通枢纽”一样的角色。其计算方法如下，分子是所有经过点i的最短路径数，分母是所有最短路径数：

     此处我想用“等等等等”来表达诸如以上的指标真心太多了。大家使用时要结合自己的业务场景进行借鉴。

 三、我们的应用

     目前，俺们也是新入门去应用这个东东。使用的是比较简单的，度数与集聚系数加权的方法。我们在Spark中自定义了一个函数，代码如下:

  def calNodeImportanceIndex(graph :Graph[String,Int], revFlag :Boolean = true) = {
      //revFlag 用来控制集聚系数是正向作用还是反向作用
      val nodeDegree = graph.degrees
      val nodeClusterEdge = graph.triangleCount.cache()
        
      val nodeInfo = nodeClusterEdge.vertices.leftOuterJoin(nodeDegree).map{case (id,(clusterEdgesNum, degree)) => 
         val total :Double = degree.get*(degree.get-1)/2
         val clusterCoeff :Double = if(total == 0) 0 else clusterEdgesNum.toDouble/total
         val revClusterCoeff = if(clusterCoeff == 0.0) 0.0 else 1.toDouble/clusterCoeff
      
         if (revFlag) (id,revClusterCoeff,degree) else (id,clusterCoeff,degree)
      }.cache()
      
      val maxRevClusterCoeff = nodeInfo.map(x => x._2).max
      val minRevClusterCoeff = nodeInfo.map(x => x._2).min
      val maxDegree = nodeInfo.map(x => x._3.get).max
      val minDegree = nodeInfo.map(x => x._3.get).min
      
      nodeInfo.map{case (id,clusterCoeff,degree) =>
          val stdRevClusterCoeff :Double= (clusterCoeff-minRevClusterCoeff)/(maxRevClusterCoeff-minRevClusterCoeff)
          val stdDegree :Double = (degree.get - minDegree).toDouble/(maxDegree - minDegree).toDouble
          val finalIndex = 0.2*stdRevClusterCoeff + 0.8*stdDegree
          (id,finalIndex)
      }
    }

参考文献

【1】Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116
【2】基于度与集聚系数的网络节点重要性度量方法研究   任卓明
【3】网络节点重要度评价方法研究 叶春森

前言   

     在此之前，笔者写过一篇关于复杂网络中节点重要性评估方法的文章（http://blog.csdn.net/a_step_further/article/details/51176964），当时用spark实现过比较简单的方法。近期在业务应用中，又遇到需要对业务问题中不同用户的影响力进行分级的需求，那么重新捡起来复习下。这次使用igraph C library来做，因为它内置了不少已经开发好的接口，使用起来很是方便。本文将几种方法简单做一个对比。

方法讨论

      评价网络中节点重要性程度的主流方法有：节点度、中心度、点介数、PageRank、特征向量等，而igraph包含有所有这些方法的实现，对应关系是：

实践讨论

    本文在业务分析中使用的是微博中转发、评论等关系所构造的图结构，图中每个节点代表一个腾讯微博账号，一条边代表一次转发或评论关系，边的权重代表某段时间内的互动次数。该图的规模是52万个节点，365万条边，使用的单机配置是64G内存，2个物理CPU，6核心。在实践中进行尝试的一些数据如下：

  对于上面3种跑出结果的数据进行标准化，画出数据分布图如下所示，可见均符合长尾分布  

介数中心性和接近中心性指标,  虽然具有较好的刻画节点重要性的能力,  但计算复杂度太高,  难以在大规模网络上使用.  为了权衡算法的效率和效果,  Chen 等人提出了一种基于半局部信息的节点重要性排序方法, 简称半局部中心性(semi-local  centrality).  首先定义N(w)为节点Vw的两层邻居度，其值等于从 Vw出发 2步内可到达的邻居的数目,  然后定义

其中 表示节点 vj的一阶邻居节点的集合.  最终节点 vi的局部中心性定义为  

可见,  半局部中心性涉及了节点的四阶邻居信息. 

#%%
import networkx as nx
#定义图的节点和边 
nodes=['1','2','3','4','5','6','7','8','9','10','11',
       '12','13','14','15','16','17','18','19','20',
       '21','22','23'] 
edges=[('1','2',1),('1','3',1),('1','4',1),('1','5',1),
       ('1','6',1),('1','7',1),('1','8',1),('1','9',1),
       ('2','3',1),('3','4',1),('6','10',1),('7','8',1),
       ('8','9',1),('10','11',1),('10','23',1),('11','12',1),
       ('11','21',1),('11','23',1),('12','13',1),('12','14',1),
       ('12','15',1),('13','14',1),('13','15',1),('13','22',1),('14','15',1),
       ('14','23',1),('15','16',1),('16','17',1),('16','18',1),
       ('16','22',1),('17','18',1),('17','20',1),('17','21',1),
       ('18','19',1),('18','22',1),('19','20',1),('19','21',1),
       ('20','21',1),('20','23',1),('22','23',1)] 
#%%
#定义无向图 
G = nx.Graph()
 
#往图添加节点和边 
G.add_nodes_from(nodes)
G.add_weighted_edges_from(edges) 
#%%
N = {}
Q = {}
CL = {}
for node in G.node:
    node_nei = list(G.neighbors(node))
    for n_i in node_nei:
        node_nei = node_nei + list(G.neighbors(n_i))
    node_nei = list(set(node_nei))
    N[node] = len(node_nei)-1

for node in G.node:
    node_nei = list(G.neighbors(node))
    t = 0
    for n_i in node_nei:
        t = t + N[n_i]
    Q[node] = t
    
for node in G.node:
    node_nei = list(G.neighbors(node))
    t = 0
    for n_i in node_nei:
        t = t + Q[n_i]
    CL[node] = t

for node in G.node:
    print(node,'N-value:',N[node],'Q-value:',Q[node],'CL-value:',CL[node])

结果： 

1 N-value: 9 Q-value: 67 CL-value: 145
2 N-value: 8 Q-value: 17 CL-value: 92
3 N-value: 8 Q-value: 25 CL-value: 101
4 N-value: 8 Q-value: 17 CL-value: 92
5 N-value: 8 Q-value: 9 CL-value: 67
6 N-value: 11 Q-value: 18 CL-value: 104
7 N-value: 8 Q-value: 17 CL-value: 92
8 N-value: 8 Q-value: 25 CL-value: 101
9 N-value: 8 Q-value: 17 CL-value: 92
10 N-value: 9 Q-value: 37 CL-value: 111
11 N-value: 12 Q-value: 41 CL-value: 166
12 N-value: 9 Q-value: 38 CL-value: 157
13 N-value: 8 Q-value: 39 CL-value: 157
14 N-value: 9 Q-value: 40 CL-value: 166
15 N-value: 9 Q-value: 37 CL-value: 156
16 N-value: 11 Q-value: 39 CL-value: 158
17 N-value: 9 Q-value: 39 CL-value: 158
18 N-value: 9 Q-value: 40 CL-value: 148
19 N-value: 8 Q-value: 28 CL-value: 119
20 N-value: 10 Q-value: 40 CL-value: 158
21 N-value: 9 Q-value: 39 CL-value: 148
22 N-value: 12 Q-value: 42 CL-value: 170
23 N-value: 14 Q-value: 52 CL-value: 200

参考：

Duanbing Chen, Linyuan Lü, Ming-Sheng Shang, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(4):1777-1787.

任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014(13):1175-1197.

http://www.xiaowangyun.com/wyblog/detail/?id=121