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

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

Leveraging neighborhood “structural holes” to identifying key spreaders in so cial networks

The identifying of influential nodes in large-scale complex networks is an important issue in optimizing network structure and enhancing robustness of a system. To measure the role of nodes, classic methods can help identify influential nodes, but they have some limitations to social networks. Local metric is simple but it can only take into account the neighbor size, and the topological connections among the neighbors are neglected, so it can not reflect the interaction between the nodes. The global metrics is difficult to use in large social networks because of the high computational complexity. Meanwhile, in the classic methods, the unique community characteristics of the social networks are not considered. To make a trade off between affections and efficiency, a local structural centrality measure is proposed which is based on nodes'' a nd their ‘neighbors’ structural holes. Both the node degree and “bridge” property are reflected in computing node constraint index. SIR (Susceptible-Infected-Recovered) model is used to evaluate the ability to spread nodes. Simulations of four real networks show that our method can rank the capability of spreading nodes more accurately than other metrics. This algorithm has strong robustness when the network is subjected to sybil attacks.