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

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

一种有效的基于三角结构的复杂网络节点影响力度量模型

度量复杂网络中的节点影响力对理解网络的结构和功能起着至关重要的作用.度、介数、紧密度等经典指标能够一定程度上度量节点影响力,k-shell和H-index等指标也可以应用于评价节点影响力.然而这些模型都存在着各自的局限性.本文基于节点与邻居节点之间的三角结构提出了一种有效的节点影响力度量指标模型(local triangle centrality,LTC),该模型不仅考虑节点间的三角结构,同时考虑了周边邻居节点的规模.我们在多个真实复杂网络上进行了大量实验,通过SIR模型进行节点影响力仿真实验,证明LTC指标相比于其他指标能够更加准确地度量节点的传播影响力.节点删除后网络鲁棒性的实验结果也表明LTC指标具有更好效果.     

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

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

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

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

识别高阶网络传播中最有影响力的节点

识别网络传播中最有影响力的节点是控制传播速度和范围的重要步骤,有助于加速有益信息扩散,抑制流行病、谣言和虚假信息的传播等.已有研究主要基于描述点对交互的低阶复杂网络.然而,现实中个体间的交互不仅发生在点对之间,也发生在3个及以上节点形成的群体中.群体交互可利用高阶网络来刻画,如单纯复形与超图.本文研究单纯复形上最有影响力的传播者识别方法.首先,提出单纯复形上易感-感染-恢复(SIR)微观马尔可夫链方程组,定量刻画单纯复形上的疾病传播动力学.接下来利用微观马尔可夫链方程组计算传播动力学中节点被感染的概率.基于网络结构与传播过程,定义节点的传播中心性,用于排序节点传播影响力.在两类合成单纯复形与4个真实单纯复形上的仿真结果表明,相比于现有高阶网络中心性和复杂网络中最优的中心性指标,本文提出的传播中心性能更准确地识别高阶网络中最有影响力的传播者.     

加权网络中基于冗余边过滤的k-核分解排序算法

k-核分解排序法对于度量复杂网络上重要节点的传播影响力具有重要的理论意义和应用价值,但其排序粗粒化的缺陷也不容忽视.最新研究发现,一些真实网络中存在局域连接稠密的特殊构型是导致上述问题的根本原因之一.当前的解决方法是利用边两端节点的外部连边数度量边的扩散性,采取过滤网络边来减少这种稠密结构给k-核分解过程造成的干扰,但这种方法并没有考虑现实网络上存在权重的普遍性.本文利用节点权重和权重分布重新定义边的扩散性,提出适用于加权网络结构的基于冗余边过滤的k-核分解排序算法:filter-core.通过世界贸易网、线虫脑细胞网和科学家合著网等真实网络的SIR(susceptible-infectedrecovered)传播模型的仿真结果表明,该算法相比其他加权k-核分解法,能够更准确地度量加权网络上具有重要传播影响力的核心节点及核心层.     

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

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

基于领域相似度的复杂网络节点重要度评估算法

节点重要性度量对于研究复杂网络鲁棒性与脆弱性具有重要意义.大规模实际复杂网络的结构往往随着时间不断变化,在获取网络全局信息用于评估节点重要性方面具有局限性.通过量化节点局部网络拓扑的重合程度来定义节点间的相似性,提出了一种考虑节点度以及邻居节点拓扑重合度的节点重要性评估算法,算法只需要获取节点两跳内的邻居节点信息,通过计算邻居节点对之间的相似度,便可表征其在复杂网络中的结构重要性.基于六个经典的实际网络和一个人工的小世界网络,分别以静态与动态的方式对网络进行攻击,通过对极大连通系数与网络效率两种评估指标的实验结果对比,证明了所提算法优于基于局域信息的度指标、半局部度指标、基于节点度及其邻居度的WL指标以及基于节点位置的K-shell指标.     

基于多重影响力矩阵的有向加权网络节点重要性评估方法

本文基于有向加权网络模型,构建了三个影响力矩阵,并利用层次分析法对其赋权求和,形成多重影响力矩阵,从而提出了一种基于该矩阵的节点重要性评价方法.该方法通过新定义的交叉强度指标,来表征节点的局部重要性;利用金网节点对待评估节点的重要性影响总值,来表征节点在全网中的相对重要性.在分析影响节点对待评估节点的影响比例时,既考虑到节点间的距离因素,又引入了最短路径条数因素;既考虑了该影响节点对网络中其他节点的影响关系,又考虑了网络中其他节点对该待评估节点的影响关系,使得评价方法更加全面.将算法运用于ARPA网络,结果表明,该方法能有效地区分各节点之间的差异,最后,对实验结果进疔连锁故障的仿真对比实验,进一步验证了方法的有效性.     

花簇分形无标度网络中节点影响力的区分度

大量研究表明分形尺度特性广泛存在于真实复杂系统中, 且分形结构显著影响网络上的传播动力学行为. 虽然复杂网络的节点传播影响力吸引了越来越多学者的关注, 但依旧缺乏针对分形网络结构的节点影响力的系统研究. 鉴于此, 本文基于花簇分形网络模型, 研究了分形无标度结构上的节点传播影响力. 首先, 对比了不同分形维数下的节点影响力, 结果表明, 当分形维数很小时, 节点影响力的区分度几乎不随节点度变化, 很难区分不同节点的传播影响力, 而随着分形维数的增大, 从全局和局域角度都能很容易识别网络中的超级传播源. 其次, 通过对原分形网络进行不同程度的随机重连来分析网络噪声对节点影响力区分度的影响, 发现在低维分形网络上, 加入网络噪声之后能够容易区分不同节点的影响力, 而在无穷维超分形网络中, 加入网络噪声之后能够区分中间度节点的影响力, 但从全局和局域角度都很难识别中心节点的影响力. 所得结论进一步补充、深化了基于花簇分形网络的节点影响力研究, 研究结果对实际病毒传播的预警控制提供了一定的理论借鉴.     

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.     

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

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

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.     

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.     

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.     

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

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

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.     

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.