面向结构洞的复杂网络关键节点排序

复杂网络中的结构洞节点对于信息传播具有重要作用, 现有关键节点排序方法多数没有兼顾结构洞节点和其他类型的关键节点进行排序. 本文根据结构洞理论与关键节点排序相关研究选取了网络约束系数、介数中心性、等级度、效率、网络规模、PageRank值以及聚类系数7个度量指标, 将基于ListNet的排序学习方法引入到复杂网络的关键节点排序问题中, 融合7个度量指标, 构建了一个能够综合评价面向结构洞节点的关键节点排序方法. 采用模拟网络和实际复杂网络进行了大量实验, 人工标准试验结果表明本文排序方法能够综合考虑结构洞节点和核心节点, 关键节点排序与人工排序结果具有较高的一致性. SIR传播模型评估实验结果表明由本文选择TOP-K节点发起的传播能够在较短的传播时间内达到最大的传播范围.     

Target recovery in complex networks

The invulnerability of complex networks is an important issue which has been widely analyzed in different fields. A lot of works have been done to measure and improve the stability of complex networks when being attacked. Recently, how to recover networks after attack was intensively studied. The existing methods are mainly designed to recover the overall functionality of networks, yet in many real cases the recovery of important nodes should be given priority, to which we refer target recovery. For example, when the cold wave paralyses the railway networks, target recovery means to repair those stations or railways such that the transport capacity of densely-populated cities can be recovered as fast as possible. In this paper, we first compare the impact of attacks on the whole network and target nodes respectively, and then study the efficiency of traditional recovery methods that are proposed based on global centrality metrics. Furthermore, based on target centrality metrics, we introduce a local betweenness recovery method and we find it has better performance than the traditional methods. We finally propose a hybrid recovery method which includes local betweenness metric and local closeness metric. The performance of the hybrid method is shown to be similar to that of the greedy algorithm.     

一种新的网络传播中最有影响力的节点发现方法

在复杂网络的传播模型研究中, 如何发现最具影响力的传播节点在理论和现实应用中都有重大的意义. 目前的研究一般使用节点的度数、紧密度、介数和K-shell等中心化指标来评价影响力, 这种方法虽然简单, 但是由于它们仅利用了节点自身的内部属性, 因而在评价影响力时精确度并不高, 普遍性适用性较弱.为了解决这个问题, 本文提出了KSC (K-shell and community centrality)指标模型. 此模型不但考虑了节点的内部属性, 而且还综合考虑了节点的外部属性, 例如节点所属的社区等. 然后利用SIR (susceptible-infected-recovered)模型对传播过程进行仿真, 实验证明所提出的方法可以更好地发现最具有影响力的节点, 且可适用于各种复杂网络. 本文为这项具有挑战性研究提供了新的思想和方法. 关键词： 复杂网络 最具影响力的节点 社区划分 中性化测量     

Identifying influential nodes in complex networks

Identifying influential nodes that lead to faster and wider spreading in complex networks is of theoretical and practical significance. The degree centrality method is very simple but of little relevance. Global metrics such as betweenness centrality and closeness centrality can better identify influential nodes, but are incapable to be applied in large-scale networks due to the computational complexity. In order to design an effective ranking method, we proposed a semi-local centrality measure as a tradeoff between the low-relevant degree centrality and other time-consuming measures. We use the Susceptible-Infected-Recovered (SIR) model to evaluate the performance by using the spreading rate and the number of infected nodes. Simulations on four real networks show that our method can well identify influential nodes.     

Extracting hidden fluctuation patterns of Hang Seng stock index from network topologies

We present a model of complex network generated from Hang Seng index (HSI) of Hong Kong stock market, which encodes stock market relevant both interconnections and interactions between fluctuation patterns of HSI in the network topologies. In the network, the nodes (edges) represent all kinds of patterns of HSI fluctuation (their interconnections). Based on network topological statistic, we present efficient algorithms, measuring betweenness centrality (BC) and inverse participation ratio (IPR) of network adjacency matrix, for detecting topological important nodes. We have at least obtained three uniform nodes of topological importance, and find the three nodes, i.e. 18.7% nodes undertake 71.9% betweenness centrality and closely correlate other nodes. From these topological important nodes, we can extract hidden significant fluctuation patterns of HSI. We also find these patterns are independent the time intervals scales. The results contain important physical implication, i.e. the significant patterns play much more important roles in both information control and transport of stock market, and should be useful for us to more understand fluctuations regularity of stock market index. Moreover, we could conclude that Hong Kong stock market, rather than a random system, is statistically stable, by comparison to random networks.     

利用邻域“结构洞”寻找社会网络中最具影响力节点

识别复杂网络中的关键节点对网络结构优化和鲁棒性增强具有十分重要的意义. 经典的关键节点测量方法在一定程度上能够辨识网络中影响力节点, 但存在一定局限性: 局部中心性测量方法仅考虑节点邻居的数目, 忽略了邻居间的拓扑关系, 不能在计算中反映邻居节点间的相互作用; 全局测量方法则由于算法本身的复杂性而不能应用于大规模社会网络的分析, 另外, 经典的关键节点测量方法也没有考虑社会网络特有的社区特征. 为高效、准确地辨识具有社区结构的社会网络中最具影响力节点, 提出了一种基于节点及其邻域结构洞的局部中心性测量方法, 该方法综合考虑了节点的邻居数量及其与邻居间的拓扑结构, 在节点约束系数的计算中同时体现了节点的度属性和“桥接”属性. 利用SIR(易感-感染-免疫)模型在真实社会网络数据上对节点传播能力进行评价后发现, 所提方法可以准确地评价节点的传播能力且具有强的鲁棒性.     

节点中心性对复杂网络传播模式的影响分析

在众多的重要节点评估方法研究中,具有较高中心性的节点一直是关注的焦点,许多传播行为的研究也主要围绕高中心性节点展开,因此在一定程度上忽略了低中心性节点对传播行为的影响.本文从传播异构性角度,通过初始感染最大中心性节点和最小中心性节点揭示网络结构异构性对信息传播的影响.实验结果表明,传播过程中存在"链型"和"扇型"两种传播模式,在初始感染比例不断提升的情况下,两种传播模式的相互转换引发传播速率的变化,进一步促使非线性传播规模交叉现象的产生.这一现象说明,在宏观的信息传播过程中,最小中心性节点的影响力不容忽视,尤其在初始感染比例升高时,最小中心性节点比最大中心性节点更具传播优势.     

Identifying all-around nodes for spreading dynamics in complex networks

Identifying the most influential nodes in complex networks provides a strong basis for understanding spreading dynamics and ensuring more efficient spread of information. Due to the heterogeneous degree distribution, we observe that current centrality measures are correlated in their results of nodes ranking. This paper introduces the concept of all-around nodes, which act like all-around players with good performance in combined metrics. Then, an all-around distance is presented for quantifying the influence of nodes. The experimental results of susceptible-infectious-recovered (SIR) dynamics suggest that the proposed all-around distance can act as a more accurate, stable indicator of influential nodes.     

The importance of centralities in dark network value chains

This paper introduces three novel centrality measures based on the nodes’ role in the operation of a joint task, i.e., their position in a criminal network value chain. For this, we consider networks where nodes have attributes describing their “capabilities” or “colors”, i.e., the possible roles they may play in a value chain. A value chain here is understood as a series of tasks to be performed in a specific order, each requiring a specific capability. The first centrality notion measures how many value chain instances a given node participates in. The other two assess the costs of replacing a node in the value chain in case the given node is no longer available to perform the task. The first of them considers the direct distance (shortest path length) between the node in question and its nearest replacement, while the second evaluates the actual replacement process, assuming that preceding and following nodes in the network should each be able to find and contact the replacement. In this report, we demonstrate the properties of the new centrality measures using a few toy examples and compare them to classic centralities, such as betweenness, closeness and degree centrality. We also apply the new measures to randomly colored empirical networks. We find that the newly introduced centralities differ sufficiently from the classic measures, pointing towards different aspects of the network. Our results also pinpoint the difference between having a replacement node in the network and being able to find one. This is the reason why “introduction distance” often has a noticeable correlation with betweenness. Our studies show that projecting value chains over networks may significantly alter the nodes’ perceived importance. These insights might have important implications for the way law enforcement or intelligence agencies look at the effectiveness of dark network disruption strategies over time.     

Detection of influential nodes with multi-scale information

The identification of influential nodes in complex networks is one of the most exciting topics in network science. The latest work successfully compares each node using local connectivity and weak tie theory from a new perspective. We study the structural properties of networks in depth and extend this successful node evaluation from single-scale to multi-scale. In particular, one novel position parameter based on node transmission efficiency is proposed, which mainly depends on the shortest distances from target nodes to high-degree nodes. In this regard, the novel multi-scale information importance (MSII) method is proposed to better identify the crucial nodes by combining the network's local connectivity and global position information. In simulation comparisons, five state-of-the-art algorithms, i.e. the neighbor nodes degree algorithm (NND), betweenness centrality, closeness centrality, Katz centrality and the k-shell decomposition method, are selected to compare with our MSII. The results demonstrate that our method obtains superior performance in terms of robustness and spreading propagation for both real-world and artificial networks.     

复杂网络中节点重要性排序的研究进展

如何用定量分析的方法识别超大规模网络中哪些节点最重要, 或者评价某个节点相对于其他一个或多个节点的重要程度, 这是复杂网络研究中亟待解决的重要问题之一. 本文分别从网络结构和传播动力学的角度, 对现有的复杂网络中节点重要性排序方法进行了系统的回顾,总结了节点重要性排序方法的最新研究进展, 并对不同的节点重要性排序指标的优缺点以及适用环境进行了分析, 最后指出了这一领域中几个有待解决的问题及可能的发展方向. 关键词： 复杂网络 节点重要性 网络结构 传播动力学     

Searchability of Central Nodes in Networks

Social networks are discrete systems with a large amount of heterogeneity among nodes (individuals). Measures of centrality aim at a quantification of nodes’ importance for structure and function. Here we ask to which extent the most central nodes can be found by purely local search. We find that many networks have close-to-optimal searchability under eigenvector centrality, outperforming searches for degree and betweenness. Searchability of the strongest spreaders in epidemic dynamics tends to be substantially larger for supercritical than for subcritical spreading.     

Transport in weighted networks: partition into superhighways and roads

Transport in weighted networks is dominated by the minimum spanning tree (MST), the tree connecting all nodes with the minimum total weight. We find that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centrality--the number of times a node (or link) is used by transport paths. One component, superhighways, is the infinite incipient percolation cluster, for which we find that nodes (or links) with high centrality dominate. For the other component, roads, which includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the infinite incipient percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. The significance of this finding is that one can improve significantly the global transport by improving a tiny fraction of the network, the superhighways.     

微博双向“关注”网络节点中心性及传播 影响力的分析

根据新浪微博的实际数据, 建立了两个基于双向“关注”的用户关系网络, 通过分析网络拓扑统计特征, 发现二者均具有小世界、无标度特征. 通过对节点度、紧密度、介数和k-core 四个网络中心性指标进行实证分析, 发现节点度服从分段幂率分布; 介数相比其他中心性指标差异性最为显著; 两个网络均具有明显的层次性, 但不是所有度值大的节点核数也大; 全局范围内各中心性指标之间存在着较强的相关性, 但在度值较大的节点群这种相关性明显减弱. 此外, 借助基于传染病动力学的SIR信息传播模型来分析四种指标在刻画节点传播能力方面的差异性, 仿真结果表明, 选择具有不同中心性指标的初始传播节点, 对信息传播速度和范围均具有不同影响; 紧密度和k-core较其他指标可以更加准确地描述节点在信息传播中所处的网络核心位置, 这有助于识别信息传播拓扑网络中的关键节点.     

Identifying influential nodes based on graph signal processing in complex networks

Identifying influential nodes in complex networks is of both theoretical and practical importance. Existing methods identify influential nodes based on their positions in the network and assume that the nodes are homogeneous. However,node heterogeneity(i.e., different attributes such as interest, energy, age, and so on) ubiquitously exists and needs to be taken into consideration. In this paper, we conduct an investigation into node attributes and propose a graph signal processing based centrality(GSPC) method to identify influential nodes considering both the node attributes and the network topology. We first evaluate our GSPC method using two real-world datasets. The results show that our GSPC method effectively identifies influential nodes, which correspond well with the underlying ground truth. This is compatible to the previous eigenvector centrality and principal component centrality methods under circumstances where the nodes are homogeneous. In addition, spreading analysis shows that the GSPC method has a positive effect on the spreading dynamics.     

PageRank centrality for temporal networks

In this paper, we propose a new centrality measure for ranking the nodes and time layers of temporal networks simultaneously, referred to as the f-PageRank centrality. The f-PageRank values of nodes and time layers in temporal networks are obtained by solving the eigenvector of a multi-homogeneous map. The existence and uniqueness of the proposed centrality measure are also guaranteed by existing results, under some reasonable conditions. The numerical experiments on a synthetic temporal network and two real-world temporal networks (i.e., Email-Eu-core and CollegeMsg temporal networks) show that the proposed centrality outperforms some existing centrality measures.     

基于区域密度曲线识别网络上的多影响力节点

复杂网络多影响力节点的识别可以帮助理解网络的结构和功能,具有重要的理论意义和应用价值.本文提出一种基于网络区域密度曲线的多影响力节点的识别方法.应用两种不同的传播模型,在不同网络上与其他中心性指标进行了比较.结果表明,基于区域密度曲线的识别方法能够更好地识别网络中的多影响力节点,选中的影响力节点之间的分布较为分散,自身也比较重要.本文所提方法是基于网络的局部信息,计算的时间复杂度较低.     

基于层间相似性的时序网络节点重要性研究

时序网络可以更加准确地描述节点之间的交互顺序和交互关系.结合多层耦合网络分析法,本文提出了基于节点层间相似性的超邻接矩阵时序网络节点重要性识别方法,与经典的认为所有层间关系为常数不同,层间关系用节点的邻居拓扑重叠系数进行度量.Workspace和Enrons数据集上的结果显示:相比经典的方法,使用该方法得到的Kendall’sτ值在各时间层上的平均提高,最高为17.72%和12.44%,结果表明层间相似性的度量对于时序网络的节点重要性度量具有十分重要的意义.     

Optimization of transport protocols in complex networks

In this paper, an optimal routing strategy is proposed to enhance the traffic capacity of complex networks. In order to avoid nodes overloading, the new algorithm is derived on the basis of generalized betweenness centrality which gives an estimate of traffic handled by the node for a route set. Since the nodes with large betweenness centrality are more susceptible to traffic congestion, the traffic can be improved, as our strategy, by redistributing traffic load from nodes with large betweenness centrality to nodes with small betweenness centrality in the proceeding of computing collective routing table. Particularly, depending on a parameter that controls the optimization scale, the new routing can not only enlarge traffic capacity of networks more, but also enhance traffic efficiency with smaller average path length. Comparing results of previous routing strategies, it is shown that the present improved routing performs more effectively.     

Routing in scale-free networks based on expanding betweenness centrality

In this paper, an improved routing strategy is proposed for enhancing the traffic capacity of scale-free networks. Instead of using the information of degree and betweenness centrality, the new algorithm is derived on the basis of the expanding betweenness centrality of nodes, which gives an estimate of the traffic handled by the vertex for a certain route set. Since the nodes with large betweenness centrality are more susceptible to traffic congestion, the traffic can be improved by redistributing traffic loads from nodes with large betweenness centrality to nodes with small betweenness centrality in the process of computing the collective routing table. Comparing with results of previous routing strategies, it is shown that the present improved routing performs more effectively.