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.     

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.     

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.     

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

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

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

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

A thermal flux-diffusing model for complex networks and its applications in community structure detection

We introduce a thermal flux-diffusing model for complex networks. Based on this model, we propose a physical method to detect the communities in the complex networks. The method allows us to obtain the temperature distribution of nodes in time that scales linearly with the network size. Then, the local community enclosing a given node can be easily detected for the reason that the dense connections in the local communities lead to the temperatures of nodes in the same community being close to each other. The community structure of a network can be recursively detected by randomly choosing the nodes outside the detected local communities. In the experiments, we apply our method to a set of benchmarking networks with known pre-determined community structures. The experiment results show that our method has higher accuracy and precision than most existing globe methods and is better than the other existing local methods in the selection of the initial node. Finally, several real-world networks are investigated.     

复杂网络中社团结构发现的多分辨率密度模块度

现实中的许多复杂网络呈现出明显的模块性或社团性.模块度是衡量社团结构划分优劣的效益函数, 它也通常被用作社团结构探测的目标函数,但最为广泛使用的Newman-Girvan模块度却存在着分辨率限制问题,多分辨率模块度也不能克服误合并社团和误分裂社团同时存在的缺陷. 本文在网络密度的基础上提出了多分辨率的密度模块度函数, 通过实验和分析证实了该函数能够使社团结构的误划分率显著降低, 而且能够体现出网络社团结构是一个有机整体,不是各个社团的简单相加.     

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

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

An improved complex variable element-free Galerkin method for two-dimensional elasticity problems

In this paper, the improved complex variable moving least-squares (ICVMLS) approximation is presented. The ICVMLS approximation has an explicit physics meaning. Compared with the complex variable moving least-squares (CVMLS) approximations presented by Cheng and Ren, the ICVMLS approximation has a great computational precision and efficiency. Based on the element-free Galerkin (EFG) method and the ICVMLS approximation, the improved complex variable element-free Galerkin (ICVEFG) method is presented for two-dimensional elasticity problems, and the corresponding formulae are obtained. Compared with the conventional EFG method, the ICVEFG method has a great computational accuracy and efficiency. For the purpose of demonstration, three selected numerical examples are solved using the ICVEFG method.     

利用重要度评价矩阵确定复杂网络关键节点

为了对复杂网络节点重要度进行评估,针对节点删除法、节点收缩法和介数法的不足,通过定义节点效率和节点重要度评价矩阵, 提出了一种利用重要度评价矩阵来确定复杂网络关键节点的方法.该方法综合考虑了节点效率、节点度值和相邻节点的重要度贡献,用节点度值和效率值来表征其对相邻节点的重要度贡献,其优化算法的时间复杂度为O(Rn²). 实验分析表明该方法可行有效,对于大型复杂网络可以获得理想的计算能力.     

Ranking the spreading influence of nodes in complex networks: An extended weighted degree centrality based on a remaining minimum degree decomposition

Ranking the spreading influence of nodes is crucial for developing strategies to control the spreading process on complex networks. In this letter, we define, for the first time, a remaining minimum degree (RMD) decomposition by removing the node(s) with the minimum degree iteratively. Based on the RMD decomposition, a weighted degree (WD) is presented by utilizing the RMD indices of the nearest neighbors of a node. WD assigns a weight to each degree of this node, which can distinguish the contribution of each degree to the spreading influence. Further, an extended weighted degree (EWD) centrality is proposed by extending the WD of the nearest neighbors of a node. Assuming that the spreading process on networks follows the Susceptible-Infectious-Recovered (SIR) model, we perform extensive experiments on a series of synthetic and real networks to comprehensively evaluate the performance of EWD and other eleven representative measures. The experimental results show that EWD is a relatively efficient measure in running efficiency, it exposes an advantage in accuracy in the networks with a relatively small degree heterogeneity, as well as exposes a competitive performance in resolution.     

Local-Forest Method for Superspreaders Identification in Online Social Networks

Identifying the most influential spreaders in online social networks plays a prominent role in affecting information dissemination and public opinions. Researchers propose many effective identification methods, such as k-shell. However, these methods are usually validated by simulating propagation models, such as epidemic-like models, which rarely consider the Push-Republish mechanism with attenuation characteristic, the unique and widely-existing spreading mechanism in online social media. To address this issue, we first adopt the Push-Republish (PR) model as the underlying spreading process to check the performance of identification methods. Then, we find that the performance of classical identification methods significantly decreases in the PR model compared to epidemic-like models, especially when identifying the top 10% of superspreaders. Furthermore, inspired by the local tree-like structure caused by the PR model, we propose a new identification method, namely the Local-Forest (LF) method, and conduct extensive experiments in four real large networks to evaluate it. Results highlight that the Local-Forest method has the best performance in accurately identifying superspreaders compared with the classical methods.     

基于扩展单粒子模型的锂离子电池参数识别策略

为了精确识别电动汽车锂离子动力电池的关键状态参数,基于多孔电极理论和浓度理论,建立了一种考虑液相动力学行为的锂离子电池扩展单粒子模型.相较于传统单粒子模型,该模型增加了对负电极表面固体电解质界面膜参数的描述,并考虑了温度和液相浓度变化对锂离子电池关键参数的耦合影响.基于所建立的扩展单粒子模型,提出一种简化的参数灵敏度分析方法和有效的锂电池参数识别策略,用以确定特定工况下的高灵敏度待识别参数,进而利用遗传算法实现参数的优化求解.最后,通过对比分析本文模型和传统单粒子模型的仿真输出电压和相同工况下电池的实验输出电压验证了提出模型和参数识别方法的有效性和可行性,为电池管理系统的健康状态估计提供了理论基础.     

Detecting community structure in complex networks via node similarity

The detection of the community structure in networks is beneficial to understand the network structure and to analyze the network properties. Based on node similarity, a fast and efficient method for detecting community structure is proposed, which discovers the community structure by iteratively incorporating the community containing a node with the communities that contain the nodes with maximum similarity to this node to form a new community. The presented method has low computational complexity because of requiring only the local information of the network, and it does not need any prior knowledge about the communities and its detection results are robust on the selection of the initial node. Some real-world and computer-generated networks are used to evaluate the performance of the presented method. The simulation results demonstrate that this method is efficient to detect community structure in complex networks, and the ZLZ metrics used in the proposed method is the most suitable one among local indices in community detection.     

基于节点间依赖度的社团结构划分方法

本文提出了一种基于节点间依赖度的在复杂网络中划分社团结构的算法,定义了节点对其邻居的依赖度以及节点对社团的依赖度和条件依赖度.算法的基本要点是优先将最大依赖度不小于其他节点且有惟一依赖节点的节点划分到社团,并将对社团的依赖度或条件依赖度达到一定值的节点吸收进社团,直到所有节点都得到准确的社团划分.本算法在几个实际网络的测试上,都成功地划分出了满足条件的社团,并且对社团结构已知的网络的划分结果符合实际情况.     

节点数加速增长的复杂网络生长模型

受某些实际网络节点数按几何级数增长现象的启发，构造了每个时间步中按当前网络规模成比例地同时加入多个节点的节点数加速增长的网络模型.研究表明，在增长率不是很大的情况下网络度分布仍然是幂律的，但在不同的增长率r下幂律指数是不同的.得到了幂律指数介于2到3之间可调的无标度网络模型，并解析地给出了幂律指数随增长率变化的函数关系.数值模拟还显示，网络的平均最短距离随r减小而簇系数随r增大. 关键词： 复杂网络 无标度网络 生长网络模型 节点数加速增长网络模型     

一种改进的基于信息传播率的复杂网络影响力评估算法

评价网络中节点的信息传播影响力对于理解网络结构与网络功能具有重要意义.目前,许多基于最短路径的指标,如接近中心性、介数中心性以及半局部(SP)指标等相继用于评价节点传播影响力.最短路径表示节点间信息传播途径始终选择最优方式,然而实际上网络间的信息传播过程更类似于随机游走,信息的传播途径可以是节点间的任一可达路径,在集聚系数高的网络中,节点的局部高聚簇性有利于信息的有效扩散,若只考虑信息按最优传播方式即最短路径传播,则会低估节点信息传播的能力,从而降低节点影响力的排序精度.综合考虑节点与三步内邻居间的有效可达路径以及信息传播率,提出了一种SP指标的改进算法,即ASP算法.在多个经典的实际网络和人工网络上利用SIR模型对传播过程进行仿真,结果表明ASP指标与度指标、核数指标、接近中心性指标、介数中心性指标以及SP指标相比,可以更精确地对节点传播影响力进行排序.     

SIHR rumor spreading model in social networks

There are significant differences between rumor spreading and epidemic spreading in social networks, especially with consideration of the mutual effect of forgetting and remembering mechanisms. In this paper, a new rumor spreading model, Susceptible-Infected-Hibernator-Removed (SIHR) model, is developed. The model extends the classical Susceptible-Infected-Removed (SIR) rumor spreading model by adding a direct link from ignorants to stiflers and a new kind of people-Hibernators. We derive mean-field equations that describe the dynamics of the SIHR model in social networks. Then a steady-state analysis is conducted to investigate the final size of the rumor spreading under various spreading rate, stifling rate, forgetting rate, and average degree of the network. We discuss the spreading threshold and find the relationship between the final size of the rumor and two probabilities. Also Runge-Kutta method is used for numerical simulation which shows that the direct link from the ignorants to the stiflers advances the rumor terminal time and reduces the maximum rumor influence. Moreover, the forgetting and remembering mechanisms of hibernators postpone the rumor terminal time and reduce the maximum rumor influence.     

基于复杂网络理论的微博用户关系网络演化模型研究

微博给人们提供便利的同时也产生了较大的负面影响.为获取微博谣言的传播规律,进而采取有效措施防控其传播,本文基于复杂网络理论研究微博用户关系网络的内部特征,提出一种微博用户关系网络演化模型,借助于平均场理论,分析该演化模型的拓扑统计特性,以及谣言在该演化模型上的传播动力学行为.理论分析和仿真实验表明,由该模型演化生成的微博用户关系网络具有无标度特性.度分布指数不仅与反向连接概率有关,而且还取决于节点的吸引度分布.研究还发现,与指数分布和均匀分布相比,当节点吸引度满足幂律分布时,稳态时的谣言传播程度较大.此外,随着反向连接概率或节点初始连边数量的增加,谣言爆发的概率以及网络中最终接受谣言的节点数量都会明显增大.