Portfolio Optimization for Influence Spread

Naoto Ohsaka, Yuichi Yoshida

Abstract

Motivated by viral marketing, stochastic diffusion processes that model influence spread on a network have been studied intensively. The primary interest in such models has been to find a seed set of a fixed size that maximizes the expected size of the cascade from it. Practically, however, it is not desirable to have the risk of ending with a small cascade, even if the expected size of the cascade is large. To address this issue, we adopt conditional value at risk (CVaR) as a risk measure, and propose an algorithm that computes a portfolio over seed sets with a provable guarantee on its CVaR. Using real-world social networks, we demonstrate that the portfolio computed by our algorithm has a significantly better CVaR than seed sets computed by other baseline methods.
BibTeX
@inproceedings{ohsaka2017portfolio,
  author = {Naoto Ohsaka and Yuichi Yoshida},
  title = {{Portfolio Optimization for Influence Spread}},
  booktitle = {The Web Conference},
  year = {2017},
  doi = {10.1145/3038912.3052628},
}

Loading related content...

Figure