Convex relaxation for finding planted influential nodes in a social network
Abstract
We consider the problem of maximizing influence in a social network. We focus on the case that the social network is a directed bipartite graph whose arcs join senders to receivers. We consider both the case of deterministic networks and probabilistic graphical models, that is, the socalled "cascade" model. The problem is to find the set of the $k$ most influential senders for a given integer $k$. Although this problem is NPhard, there is a polynomialtime approximation algorithm due to Kempe, Kleinberg and Tardos. In this work we consider convex relaxation for the problem. We prove that convex optimization can recover the exact optimizer in the case that the network is constructed according to a generative model in which influential nodes are planted but then obscured with noise. We also demonstrate computationally that the convex relaxation can succeed on a more realistic generative model called the "forest fire" model.
 Publication:

arXiv eprints
 Pub Date:
 July 2013
 arXiv:
 arXiv:1307.4047
 Bibcode:
 2013arXiv1307.4047E
 Keywords:

 Mathematics  Optimization and Control;
 Computer Science  Social and Information Networks;
 Physics  Physics and Society