Discovering Influential Nodes for SIS Models in Social Networks
Discovering Influential Nodes for SIS Models in Social Networks
复制标题
DOI：
10.1007/978-3-642-04747-3_24
复制
发表时间：
2009-10
期刊：
影响因子：
--
通讯作者：
Kazumi Saito;M. Kimura;H. Motoda
中科院分区：
文献类型：
--
作者：
Kazumi Saito;M. Kimura;H. Motoda
我们在易感/感染/易感（SIS）模型下解决了有效发现社交网络中有影响力节点的问题，SIS模型是一种允许节点被多次激活的扩散模型。由于这种多重激活特性，计算复杂性急剧增加。我们在原始社交网络的基础上构建了一个分层图，随着时间的推移，每一层都在上面增加，并应用带有修剪和倦怠策略的纽带渗透来解决这个问题。我们通过实验证明，所提出的方法提供了比传统方法更好的解决方案，传统方法仅基于使用两个大型现实世界网络（博客网络和维基百科网络）进行社会网络分析的中心性概念。理论分析表明，该方法的计算复杂度远小于传统的朴素概率模拟方法，并通过实验证实了这一点。发现的影响节点的属性与基于中心性的启发式方法所识别的属性有很大不同。
We address the problem of efficiently discovering the influential nodes in a social network under thesusceptible/infected/susceptible (SIS) model, a diffusion model where nodes are allowed to be activated multiple times. The computational complexity drastically increases because of this multiple activation property. We solve this problem by constructing a layered graph from the original social network with each layer added on top as the time proceeds, and applying the bond percolation with pruning and burnout strategies. We experimentally demonstrate that the proposed method gives much better solutions than the conventional methods that are solely based on the notion of centrality for social network analysis using two large-scale real-world networks (a blog network and a wikipedia network). We further show that the computational complexity of the proposed method is much smaller than the conventional naive probabilistic simulation method by a theoretical analysis and confirm this by experimentation. The properties of the influential nodes discovered are substantially different from those identified by the centrality-based heuristic methods.