A novel method for identifying influential nodes in complex networks based on gravity model

How to identify influential nodes in complex networks is an essential issue in the study of network characteristics. A number of methods have been proposed to address this problem, but most of them focus on only one aspect. Based on the gravity model, a novel method is proposed for identifying influential nodes in terms of the local topology and the global location. This method comprehensively examines the structural hole characteristics and K-shell centrality of nodes, replaces the shortest distance with a probabilistically motivated effective distance, and fully considers the influence of nodes and their neighbors from the aspect of gravity. On eight real-world networks from different fields, the monotonicity index, susceptible-infected-recovered (SIR) model, and Kendall's tau coefficient are used as evaluation criteria to evaluate the performance of the proposed method compared with several existing methods. The experimental results show that the proposed method is more efficient and accurate in identifying the influence of nodes and can significantly discriminate the influence of different nodes.     

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.     

The relative importance of structure and dynamics on node influence in reversible spreading processes

The reversible spreading processes with repeated infection widely exist in nature and human society, such as gonorrhea propagation and meme spreading. Identifying influential spreaders is an important issue in the reversible spreading dynamics on complex networks, which has been given much attention. Except for structural centrality, the nodes’ dynamical states play a significant role in their spreading influence in the reversible spreading processes. By integrating the number of outgoing edges and infection risks of node’s neighbors into structural centrality, a new measure for identifying influential spreaders is articulated which considers the relative importance of structure and dynamics on node influence. The number of outgoing edges and infection risks of neighbors represent the positive effect of the local structural characteristic and the negative effect of the dynamical states of nodes in identifying influential spreaders, respectively. We find that an appropriate combination of these two characteristics can greatly improve the accuracy of the proposed measure in identifying the most influential spreaders. Notably, compared with the positive effect of the local structural characteristic, slightly weakening the negative effect of dynamical states of nodes can make the proposed measure play the best performance. Quantitatively understanding the relative importance of structure and dynamics on node influence provides a significant insight into identifying influential nodes in the reversible spreading processes.     

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

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

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

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

An extended improved global structure model for influential node identification in complex networks

Accurate identification of influential nodes facilitates the control of rumor propagation and interrupts the spread of computer viruses. Many classical approaches have been proposed by researchers regarding different aspects. To explore the impact of location information in depth, this paper proposes an improved global structure model to characterize the influence of nodes. The method considers both the node's self-information and the role of the location information of neighboring nodes. First, degree centrality of each node is calculated, and then degree value of each node is used to represent self-influence, and degree values of the neighbor layer nodes are divided by the power of the path length, which is path attenuation used to represent global influence. Finally, an extended improved global structure model that considers the nearest neighbor information after combining self-influence and global influence is proposed to identify influential nodes. In this paper, the propagation process of a real network is obtained by simulation with the SIR model, and the effectiveness of the proposed method is verified from two aspects of discrimination and accuracy. The experimental results show that the proposed method is more accurate in identifying influential nodes than other comparative methods with multiple networks.     

Towards understanding the behavior of physical systems using information theory

One of the goals of complex network analysis is to identify the most influential nodes, i.e., the nodes that dictate the dynamics of other nodes. In the case of autonomous systems or transportation networks, highly connected hubs play a preeminent role in diffusing the flow of information and viruses; in contrast, in language evolution most linguistic norms come from the peripheral nodes who have only few contacts. Clearly a topological analysis of the interactions alone is not sufficient to identify the nodes that drive the state of the network. Here we show how information theory can be used to quantify how the dynamics of individual nodes propagate through a system. We interpret the state of a node as a storage of information about the state of other nodes, which is quantified in terms of Shannon information. This information is transferred through interactions and lost due to noise, and we calculate how far it can travel through a network. We apply this concept to a model of opinion formation in a complex social network to calculate the impact of each node by measuring how long its opinion is remembered by the network. Counter-intuitively we find that the dynamics of opinions are not determined by the hubs or peripheral nodes, but rather by nodes with an intermediate connectivity.     

LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks

Identifying influential nodes in complex networks is one of the most significant and challenging issues, which may contribute to optimizing the network structure, controlling the process of epidemic spreading and accelerating information diffusion. The node importance ranking measures based on global information are not suitable for large-scale networks due to their high computational complexity. Moreover, they do not take into account the impact of network topology evolution over time, resulting in limitations in some applications. Based on local information of networks, a local clustering H-index (LCH) centrality measure is proposed, which considers neighborhood topology, the quantity and quality of neighbor nodes simultaneously. The proposed measure only needs the information of first-order and second-order neighbor nodes of networks, thus it has nearly linear time complexity and can be applicable to large-scale networks. In order to test the proposed measure, we adopt the susceptible-infected-recovered (SIR) and susceptible-infected (SI) models to simulate the spreading process. A series of experimental results on eight real-world networks illustrate that the proposed LCH can identify and rank influential nodes more accurately than several classical and state-of-the-art measures.     

Identifying Influential Nodes in Complex Networks Based on Multiple Local Attributes and Information Entropy

Identifying influential nodes in complex networks has attracted the attention of many researchers in recent years. However, due to the high time complexity, methods based on global attributes have become unsuitable for large-scale complex networks. In addition, compared with methods considering only a single attribute, considering multiple attributes can enhance the performance of the method used. Therefore, this paper proposes a new multiple local attributes-weighted centrality (LWC) based on information entropy, combining degree and clustering coefficient; both one-step and two-step neighborhood information are considered for evaluating the influence of nodes and identifying influential nodes in complex networks. Firstly, the influence of a node in a complex network is divided into direct influence and indirect influence. The degree and clustering coefficient are selected as direct influence measures. Secondly, based on the two direct influence measures, we define two indirect influence measures: two-hop degree and two-hop clustering coefficient. Then, the information entropy is used to weight the above four influence measures, and the LWC of each node is obtained by calculating the weighted sum of these measures. Finally, all the nodes are ranked based on the value of the LWC, and the influential nodes can be identified. The proposed LWC method is applied to identify influential nodes in four real-world networks and is compared with five well-known methods. The experimental results demonstrate the good performance of the proposed method on discrimination capability and accuracy.     

复杂网络中最小K-核节点的传播能力分析

K-核分解方法对于识别复杂网络传播动力学中最重要节点具有重要的价值, 然而该方法无法对复杂网络中大量最小K-核节点的传播能力进行准确度量. 本文主要考察最小K-核节点的传播行为, 利用其邻居的K-核信息, 提出一种度量这类节点传播能力的方法. 实证网络数据集的传播行为仿真结果表明, 该方法与度、介数等指标相比更能准确度量最小K-核节点的传播能力. 关键词： 复杂网络 传播能力 K-核分解 最小K-核节点     

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

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

Epidemic spreading in lattice-embedded scale-free networks

We study geographical effects on the spread of diseases in lattice-embedded scale-free networks. The geographical structure is represented by the connecting probability of two nodes that is related to the Euclidean distance between them in the lattice. By studying the standard susceptible-infected model, we found that the geographical structure has great influences on the temporal behavior of epidemic outbreaks and the propagation in the underlying network: the more geographically constrained the network is, the more smoothly the epidemic spreads, which is different from the clearly hierarchical dynamics that the infection pervades the networks in a progressive cascade across smaller-degree classes in Barabási–Albert scale-free networks.     

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.     

An Efficient Partition-Based Approach to Identify and Scatter Multiple Relevant Spreaders in Complex Networks

One of the main problems in graph analysis is the correct identification of relevant nodes for spreading processes. Spreaders are crucial for accelerating/hindering information diffusion, increasing product exposure, controlling diseases, rumors, and more. Correct identification of spreaders in graph analysis is a relevant task to optimally use the network structure and ensure a more efficient flow of information. Additionally, network topology has proven to play a relevant role in the spreading processes. In this sense, more of the existing methods based on local, global, or hybrid centrality measures only select relevant nodes based on their ranking values, but they do not intentionally focus on their distribution on the graph. In this paper, we propose a simple yet effective method that takes advantage of the underlying graph topology to guarantee that the selected nodes are not only relevant but also well-scattered. Our proposal also suggests how to define the number of spreaders to select. The approach is composed of two phases: first, graph partitioning; and second, identification and distribution of relevant nodes. We have tested our approach by applying the SIR spreading model over nine real complex networks. The experimental results showed more influential and scattered values for the set of relevant nodes identified by our approach than several reference algorithms, including degree, closeness, Betweenness, VoteRank, HybridRank, and IKS. The results further showed an improvement in the propagation influence value when combining our distribution strategy with classical metrics, such as degree, outperforming computationally more complex strategies. Moreover, our proposal shows a good computational complexity and can be applied to large-scale networks.     

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

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

Feedback between node and network dynamics can produce real-world network properties

Real-world networks are characterized by common features, including among others a scale-free degree distribution, a high clustering coefficient and a short typical distance between nodes. These properties are usually explained by the dynamics of edge and node addition and deletion.     

基于自规避随机游走的节点排序算法

评估复杂网络系统的节点重要性有助于提升其系统抗毁性和结构稳定性. 目前, 定量节点重要性的排序算法通常基于网络结构的中心性指标如度数、介数、紧密度、特征向量等. 然而, 这些算法需要以知晓网络结构的全局信息为前提, 很难在大规模网络中实际应用. 基于自规避随机游走的思想, 提出一种结合网络结构局域信息和标签扩散的节点排序算法. 该算法综合考虑了节点的直接邻居数量及与其他节点之间的拓扑关系, 能够表征其在复杂网络系统中的结构影响力和重要性. 基于三个典型的实际网络, 通过对极大连通系数、网络谱距离数、节点连边数和脆弱系数等评估指标的实验对比, 结果表明提出的算法显著优于现有的依据局域信息的节点排序算法.     

Carrier dynamics in strain-induced InGaAsP/InP quantum dots

Carrier dynamics of strain-induced InGaAsP/InP quantum dots (QDs) is investigated. In this structure, self-assembled InAs islands on the surface act as stressors and create a lateral confinement potential in the near surface InGaAsP/InP quantum well. Photoluminescence (PL) measurements reveal that decreasing the distance from the QD to the surface significantly diminishes the QD–PL intensity, presumably due to surface states of the InAs islands. Moreover, time-resolved measurements show a faster decay of the QD–PL with decreasing distance. To analyze the carrier dynamics, rate equation model is applied and surface state-related transitions are taken into account. The model is found to agree with measurements, and thus provides a possible explanation for the observed temporal behavior of the carriers.     

Studies on controllability of directed networks with extremal optimization

Almost all natural, social and man-made-engineered systems can be represented by a complex network to describe their dynamic behaviors. To make a real-world complex network controllable with its desired topology, the study on network controllability has been one of the most critical and attractive subjects for both network and control communities. In this paper, based on a given directed–weighted network with both state and control nodes, a novel optimization tool with extremal dynamics to generate an optimal network topology with minimum control nodes and complete controllability under Kalman’s rank condition has been developed. The experimental results on a number of popular benchmark networks show the proposed tool is effective to identify the minimum control nodes which are sufficient to guide the whole network’s dynamics and provide the evolution of network topology during the optimization process. We also find the conclusion: “the sparse networks need more control nodes than the dense, and the homogeneous networks need fewer control nodes compared to the heterogeneous” (Liu et al., 2011  [18]), is also applicable to network complete controllability. These findings help us to understand the network dynamics and make a real-world network under the desired control. Moreover, compared with the relevant research results on structural controllability with minimum driver nodes, the proposed solution methodology may also be applied to other constrained network optimization problems beyond complete controllability with minimum control nodes.