---
title: "Efficient Estimation of Influence Functions for SIS Model on Social Networks"
authors:
  - "Masahiro Kimura"
  - "Kazumi Saito"
  - "Hiroshi Motoda"
doi: ""
url: "https://ijcai.org/proceedings/2009/337"
pdf: "https://ijcai.org/proceedings/2009/0337.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "2046-2050"
track: ""
keywords:
---

# Efficient Estimation of Influence Functions for SIS Model on Social Networks

Masahiro Kimura, Kazumi Saito, Hiroshi Motoda

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 2046-2050.

## Abstract

We address the problem of efficiently estimating the influence function of initially activated nodes in a social network under the susceptible / 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 a pruning strategy. We 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 applying the proposed method to two real world networks.Masahiro Kimura, Kazumi Saito, Hiroshi Motoda