eCite Digital Repository

Efficient analysis of node influence based on SIR model over huge complex networks


Kimura, M and Saito, K and Ohara, K and Motoda, H, Efficient analysis of node influence based on SIR model over huge complex networks, Proceedings of the 2014 IEEE International Conference on Data Science & Advanced Analytics, 30 October - 1 November 2014, Shanghai, China, pp. 216-222. ISBN 9781479969913 (2014) [Refereed Conference Paper]

Copyright Statement

Copyright 2014 by the Institute of Electrical and Electronics Engineers

Official URL:

DOI: doi:10.1109/DSAA.2014.7058076


Node influence is yet another useful concept to quantify how important each node is over a network and can share the same role that other centrality measures have. It can provide new insight into the information diffusion phenomena such as existence of epidemic threshold which the other topology-based centralities cannot do. We focus on information diffusion process based on the SIR model, and address the problem of efficiently estimating the influence degree for all the nodes in the network. The proposed approach is a further improvement over the existing work of the bond percolation process [1], [2] which was demonstrated to be very effective, i.e., three orders of magnitude faster than direct Monte Carlo simulation, in approximately solving the influence maximization problem under a greedy search strategy. We introduce two pruning techniques which improve computational efficiency by an order of magnitude. This is a generic approach for the SIR model setting and can be instantiated to any specific diffusion model. It does not require any approximations or assumptions to the model, e.g., small diffusion probability, shortest path, maximum influence path, etc., that were needed in the existing approaches. We demonstrate its effectiveness by extensive experiments on two large real social networks. Main finding includes that different network structures have different epidemic thresholds and the node influence can identify influential nodes that the other centrality measures cannot.

Item Details

Item Type:Refereed Conference Paper
Research Division:Information and Computing Sciences
Research Group:Distributed computing and systems software
Research Field:Networking and communications
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the information and computing sciences
UTAS Author:Motoda, H (Dr Hiroshi Motoda)
ID Code:100270
Year Published:2014
Deposited By:Research Division
Deposited On:2015-05-08
Last Modified:2018-01-28

Repository Staff Only: item control page