一个节点的邻居数越多，就越重要^{6半局部中心性7}

节点j两步可达(二阶邻居)的节点数量

T(j)示节点j的一阶邻居节点的集合

其中N(w)是节点w一阶、二阶邻居的个数K-壳分解

节点在网络中的位置也是至关重要的因素。

1.删掉网络中度为Ks=l的点

2.删掉新出现的Ks=1的点

3.直到所剩网络中没有Ks=1的点

取Ks=2 ,重复以上步骤^8H-index

对于网络中的一个节点v

定义Fv(k)F_v(k)Fv​(k)表示v由k个邻居的度大于k

Hindex(v)=maxk(k∣Fv(k))H_{index}(v)=max_k({k|F_v(k)})Hindex​(v)=maxk​(k∣Fv​(k))

即v最多有Hindex(v)H_{index}(v)Hindex​(v)个邻居的度大于Hindex(v)H_{index}(v)Hindex​(v)^{9 基于路径的方法 接近中心性10}

①通过计算节点与网络中其他所有节点的距离的平均值来消除特殊值的干扰。即利用信息在网络中的平均传播时长来确定节点的重要性。

②一个节点与网络中其他节点的平均距离越小,该节点的接近中心性就越大。介数中心性

①网络中所有节点对的最短路径中，经过一个节点的最短路径数越多这个节点就越重要。

②介数中心性刻画了节点对网络中沿最短路径传输的网络流的控制力离心中心性¹¹

①网络直径定义为网络G中所有节点的离心中心性中的最大值，网络半径定义为所有节点的离心中心性值中的最小值。

②网络的中心节点就是离心中心性值等于网络半径的节点,一个节点的离心中心性与网络半径越接近就越中心。流介数中心性¹²

如果选择最短路径来运输网络流,很多情况下反而会延长出行时间、降低出行效率

网络中所有不重复的路径中, 经过一个节点的路径的比例越大，这个节点就越重要。其中, gstig^i_{st}gsti​为网络中节点s与t之间的所有路径数(不包含回路) gstg_{st}gst​为节点对s与t之间经过i的路径数Katz中心性¹³

Katz中心性认为短路径比长路径更加重要。它通过一个与路径长度相关的因子对不同长度的路径加权。一个与节点i相距有p步长的节点，对i的中心性的贡献为svs^vsv连通介数中心性¹⁴

考虑节点对之间的所有路径，赋予较长的路径较小的权值

定义节点对(p,q)之间的连通度GpqG_{pq}Gpq​

基于连通度的概念，可定义节点r的连通介数中心性。 基于特征向量的方法 特征向量中心性

一个节点的重要性既取决于其邻居节点的数量(即该节点的度)也取决于每个邻居节点的重要性。PageRank中心性

谷歌搜索弓|擎的核心算法,迭代算法。

PageRank算法基于网页的链接结构给网页排序,它认为万维网中一个页面的重要性取决于指向它的其他页面的数量和质量,如果它被很多高质量页面指向,则这个页面的质量也高。^{15LeaderRank中心性}

对PageRank的一种修正。

在现实中人们在内容丰富的热门J网页(出度大的节点).上浏览的时候选择使用地址栏跳转页面的概率要远小于浏览信息量少的枯燥网页(出度小的节点)

参数c的选取往往需要实验获得， 并且在不同的应用背景下最优参数不具有普适性。

在有向网络的随机游走过程中，通过添加一个背景节点以及该节点与网络中所有节点的双向边来代替PageRank算法中的跳转概率c,从而得到一一个无参数且形式上更加简单优美的算法。^{16Hits中心性 权威值(authorities) +枢纽值(Hubs)17}

使用在二分网结构下，可以计算出一个节点的权威值 基于节点移除或收缩的方法

节点的重要性往往体现在该节点被移除之后对网络的破坏性(或对特定功能的影响)¹⁸

参考文献

Bonacich P F . Factoring and Weighting Approaches to Status Scores and Clique Identification[J]. Journal of Mathematical Sociology, 1972, 2(1):113-120. ↩︎

Linton, C, Freeman. Centrality in social networks conceptual clarification[J]. Social Networks, 1978. ↩︎

lyer S, Killingback T, Sundaram B, et al. Attack robustness and centrality of

complex networks. PLoS One, , 8: e59613 ↩︎

Lü L, Zhang Y C, Yeung C H, et al. Leaders in social networks, the delicious case[J]. PloS one, , 6(6). ↩︎

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

Bonacich P F . Factoring and Weighting Approaches to Status Scores and Clique Identification[J]. Journal of Mathematical Sociology, 1972, 2(1):113-120. ↩︎

Chen D, Lü L, Shang M S, et al. Identifying influential nodes in complex networks[J]. Physica a: Statistical mechanics and its applications, , 391(4): 1777-1787. ↩︎

Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature physics, , 6(11): 888-893. ↩︎

Hirsch J E.An index to quantify an individual’s scientific research output[J].PNAS, ,102(46):16569-16572. ↩︎

Freeman L C. Centrality in social networks conceptual clarification[J]. Social networks, 1978, 1(3): 215-239. ↩︎

Hage P, Harary F. Eccentricity and centrality in networks[J]. Social networks, 1995, 17(1): 57-63. ↩︎

Freeman L C, Borgatti S P, White D R. Centrality in valued graphs: A measure of betweenness based on network flow[J]. Social networks, 1991, 13(2): 141-154. ↩︎

Katz L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39-43. ↩︎

Estrada E, Hatano N. Communicability in complex networks[J]. Physical Review E, , 77(3): 036111. ↩︎

Brin S, Page L. The anatomy of a large-scale hypertextual web search engine[J]. 1998. ↩︎

Lü L, Zhang Y C, Yeung C H, et al. Leaders in social networks, the delicious case[J]. PloS one, , 6(6). ↩︎

Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM (JACM), 1999, 46(5): 604-632. ↩︎

Restrepo J G, Ott E, Hunt B R. Characterizing the dynamical importance of network nodes and links[J]. Physical review letters, , 97(9): 094102. ↩︎