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.     

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模型和本文模型在六类不同网络拓扑下进行了仿真实验.仿真结果表明, 两类模型在均匀网络中没有明显差异, 但在非均匀网络中本文模型更能体现真实网络特点, 实验同时验证了节点的地位影响着信息的传播, 并且发现英文社交平台Twitter和中文社交平台新浪微博在拓扑结构上具备一定相似性.     

The fastest spreader in SIS epidemics on networks

Identifying the fastest spreaders in epidemics on a network helps to ensure an efficient spreading. By ranking the average spreading time for different spreaders, we show that the fastest spreader may change with the effective infection rate of a SIS epidemic process, which means that the time-dependent influence of a node is usually strongly coupled to the dynamic process and the underlying network. With increasing effective infection rate, we illustrate that the fastest spreader changes from the node with the largest degree to the node with the shortest flooding time. (The flooding time is the minimum time needed to reach all other nodes if the process is reduced to a flooding process.) Furthermore, by taking the local topology around the spreader and the average flooding time into account, we propose the spreading efficiency as a metric to quantify the efficiency of a spreader and identify the fastest spreader, which is adaptive to different infection rates in general networks.     

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.     

动态突触、神经耦合与时间延迟对神经元发放的影响

神经元膜电位的受激发放在神经系统的信息传递中起着重要作用.基于一个受动态突触刺激的突触后神经元发放模型,采用数值模拟和傅里叶变换分析的方法研究了动态突触、神经耦合与时间延迟对突触后神经元发放的影响.结果发现:突触前神经元发放频率与Hodgkin-Huxley神经元的固有频率发生共振决定了突触后神经元发放的难易,特定频率范围内的电流刺激有利于神经元激发,动态突触输出的随机突触电流中这些电流刺激所占的比率在很大程度上影响了突触后神经元的发放次数;将突触后神经元换成神经网络后,网络中神经元之间的耦合可以促进神经元的发放,耦合中的时间延迟可以增强这种促进作用,但是不会改变神经耦合对神经元发放的促进模式.     

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

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

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

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

A preliminary investigation on the topology of Chinese and climate networks

Complex networks have been studied across many fields of science in recent years. In this paper, we give a brief introduction of networks, then follow the original works by Tsonis et al (2004, 2006) starting with data of the surface temperature from 160 Chinese weather observations to investigate the topology of Chinese climate networks. Results show that the Chinese climate network exhibits a characteristic of regular, almost fully connected networks, which means that most nodes in this case have the same number of links, and so-called super nodes with a very large number of links do not exist there. In other words, though former results show that nodes in the extratropical region provide a property of scale-free networks, they still have other different local fine structures inside. We also detect the community of the Chinese climate network by using a Bayesian technique; the effective number of communities of the Chinese climate network is about four in this network. More importantly, this technique approaches results in divisions which have connections with physics and dynamics; the division into communities may highlight the aspects of the dynamics of climate variability.     

Evolution of the Internet AS-level topology:From nodes and edges to components

Studying the topology of infrastructure communication networks(e.g., the Internet) has become a means to understand and develop complex systems. Therefore, investigating the evolution of Internet network topology might elucidate disciplines governing the dynamic process of complex systems. It may also contribute to a more intelligent communication network framework based on its autonomous behavior. In this paper, the Internet Autonomous Systems(ASes) topology from 1998 to 2013 was studied by deconstructing and analysing topological entities on three different scales(i.e., nodes,edges and 3 network components: single-edge component M1, binary component M2 and triangle component M3). The results indicate that: a) 95% of the Internet edges are internal edges(as opposed to external and boundary edges); b) the Internet network consists mainly of internal components, particularly M2 internal components; c) in most cases, a node initially connects with multiple nodes to form an M2 component to take part in the network; d) the Internet network evolves to lower entropy. Furthermore, we find that, as a complex system, the evolution of the Internet exhibits a behavioral series,which is similar to the biological phenomena concerned with the study on metabolism and replication. To the best of our knowledge, this is the first study of the evolution of the Internet network through analysis of dynamic features of its nodes,edges and components, and therefore our study represents an innovative approach to the subject.     

Information theoretic description of networks

We present a new information theoretic approach for network characterizations. It is developed to describe the general type of networks with n nodes and L directed and weighted links, i.e., it also works for the simpler undirected and unweighted networks. The new information theoretic measures for network characterizations are based on a transmitter-receiver analogy of effluxes and influxes. Based on these measures, we classify networks as either complex or non-complex and as either democracy or dictatorship networks. Directed networks, in particular, are furthermore classified as either information spreading and information collecting networks.The complexity classification is based on the information theoretic network complexity measure medium articulation (MA). It is proven that special networks with a medium number of links (L∼n^1.5) show the theoretical maximum complexity . A network is complex if its MA is larger than the average MA of appropriately randomized networks: MA>MA_r. A network is of the democracy type if its redundancy R<R_r, otherwise it is a dictatorship network. In democracy networks all nodes are, on average, of similar importance, whereas in dictatorship networks some nodes play distinguished roles in network functioning. In other words, democracy networks are characterized by cycling of information (or mass, or energy), while in dictatorship networks there is a straight through-flow from sources to sinks. The classification of directed networks into information spreading and information collecting networks is based on the conditional entropies of the considered networks (H(A/B)=uncertainty of sender node if receiver node is known, H(B/A)=uncertainty of receiver node if sender node is known): if H(A/B)>H(B/A), it is an information collecting network, otherwise an information spreading network.Finally, different real networks (directed and undirected, weighted and unweighted) are classified according to our general scheme.     

An efficient approach of controlling traffic congestion in scale-free networks

We propose and study a model of traffic in communication networks. The underlying network has a structure that is tunable between a scale-free growing network with preferential attachments and a random growing network. To model realistic situations where different nodes in a network may have different capabilities, the message or packet creation and delivering rates at a node are assumed to depend on the degree of the node. Noting that congestions are more likely to take place at the nodes with high degrees in networks with scale-free character, an efficient approach of selectively enhancing the message-processing capability of a small fraction (e.g. 3%) of the nodes is shown to perform just as good as enhancing the capability of all nodes. The interplay between the creation rate and the delivering rate in determining non-congested or congested traffic in a network is studied more numerically and analytically.     

Empirical topological investigation of practical supply chains based on complex networks

The industrial supply chain networks basically capture the circulation of social resource, dominating the stability and efficiency of the industrial system. In this paper, we provide an empirical study of the topology of smartphone supply chain network. The supply chain network is constructed using open online data. Our experimental results show that the smartphone supply chain network has small-world feature with scale-free degree distribution, in which a few high degree nodes play a key role in the function and can effectively reduce the communication cost. We also detect the community structure to find the basic functional unit. It shows that information communication between nodes is crucial to improve the resource utilization. We should pay attention to the global resource configuration for such electronic production management.     

Synchronization in asymmetrically coupled networks with node balance

We study global stability of synchronization in asymmetrically connected networks of limit-cycle or chaotic oscillators. We extend the connection graph stability method to directed graphs with node balance, the property that all nodes in the network have equal input and output weight sums. We obtain the same upper bound for synchronization in asymmetrically connected networks as in the network with a symmetrized matrix, provided that the condition of node balance is satisfied. In terms of graphs, the symmetrization operation amounts to replacing each directed edge by an undirected edge of half the coupling strength. It should be stressed that without node balance this property in general does not hold.     

基于扩展度的复杂网络传播影响力评估算法

对网络中节点的传播影响力进行评估具有十分重要的意义, 有助于促进有益或抑制有害信息的传播. 目前, 多种中心性指标可用于对节点的传播影响力进行评估, 然而它们一般只有当传播率处于特定范围时才能取得理想的结果. 例如, 度值中心性指标在传播率较小时较为合适, 而半局部中心性和接近中心性指标则适用于稍大一些的传播率. 为了解决各种评估指标对传播率敏感的问题, 提出了一种基于扩展度的传播影响力评估算法. 算法利用邻居节点度值叠加的方式对节点度的覆盖范围进行了扩展, 使不同的扩展层次对应于不同的传播率, 并通过抽样测试确定了适合于特定传播率的层次数. 真实和模拟数据集上的实验结果表明, 通过扩展度算法得到的扩展度指标能在不同传播率下对节点的传播影响力进行有效评估, 其准确性能够达到或优于利用其他中心性指标进行评估的结果.     

Enhancement of scale-free network attack tolerance

Despite the large size of most communication and transportation systems,there are short paths between nodes in these networks which guarantee the efficient information,data and passenger delivery;furthermore these networks have a surprising tolerance under random errors thanks to their inherent scale-free topology.However,their scale-free topology also makes them fragile under intentional attacks,leaving us a challenge on how to improve the network robustness against intentional attacks without losing their strong tolerance under random errors and high message and passenger delivering capacity.Here we propose two methods (SL method and SH method) to enhance scale-free network’s tolerance under attack in different conditions.     

Adaptive generalized matrix projective lag synchronization between two different complex networks with non-identical nodes and different dimensions

<正>The adaptive generalized matrix projective lag synchronization between two different complex networks with non-identical nodes and different dimensions is investigated in this paper.Based on Lyapunov stability theory and Barbalat’s lemma,generalized matrix projective lag synchronization criteria are derived by using the adaptive control method.Furthermore,each network can be undirected or directed,connected or disconnected,and nodes in either network may have identical or different dynamics.The proposed strategy is applicable to almost all kinds of complex networks.In addition,numerical simulation results are presented to illustrate the effectiveness of this method,showing that the synchronization speed is sensitively influenced by the adaptive law strength,the network size,and the network topological structure.     

Finding communities in directed networks by PageRank random walk induced network embedding

Community structure has been found to exist ubiquitously in many different kinds of real world complex networks. Most of the previous literature ignores edge directions and applies methods designed for community finding in undirected networks to find communities. Here, we address the problem of finding communities in directed networks. Our proposed method uses PageRank random walk induced network embedding to transform a directed network into an undirected one, where the information on edge directions is effectively incorporated into the edge weights. Starting from this new undirected weighted network, previously developed methods for undirected network community finding can be used without any modification. Moreover, our method improves on recent work in terms of community definition and meaning. We provide two simulated examples, a real social network and different sets of power law benchmark networks, to illustrate how our method can correctly detect communities in directed networks.     

基于联合矩阵分解的节点多属性网络社团检测

发现复杂网络中的社团结构在社会网络、生物组织网络和在线网络等复杂网络中具备十分重要的意义. 针对社交媒体网络的社团检测通常需要利用两种信息源: 网络拓扑结构特征和节点属性特征, 丰富的节点内容属性信息为社团检测的增加了灵活性和挑战. 传统方法是要么仅针对这两者信息之一进行单独挖掘, 或者将两者信息得到的社团结果进行线性叠加判决, 不能有效进行信息源的融合. 本文将节点的多维属性特征作为社团划分的一种有效协同学习项进行研究, 将两者信息源进行融合分析, 提出了一种基于联合矩阵分解的节点多属性网络社团检测算法CDJMF, 提高了社团检测的有效性和鲁棒性. 实验表明, 本文所提的方法能够有效利用节点的属性信息指导社团检测, 具备更高的社团划分质量.     

Community detection with consideration of non-topological information

In a network described by a graph, only topological structure information is considered to determine how the nodes are connected by edges. Non-topological information denotes that which cannot be determined directly from topological information. This paper shows, by a simple example where scientists in three research groups and one external group form four communities, that in some real world networks non-topological information (in this example, the research group affiliation) dominates community division. If the information has some influence on the network topological structure, the question arises as to how to find a suitable algorithm to identify the communities based only on the network topology. We show that weighted Newman algorithm may be the best choice for this example. We believe that this idea is general for real-world complex networks.