Optimizing locally the spread of influence in large scale online social networks

Authors:

Abstract
Optimizing the spread of influence in online social networks (OSNs) is important for the design of efficient viral marketing strategies using online recommendations. It is commonly believed that, spreading is a global process, whose optimization would require the knowledge of the whole network information. Here we uncover a characteristic local length scale, called influence radius, hidden in the global nature of spreading processes. We show that, any node's influence to the entire OSN can be quantified from its local network environment within the influence radius, which is significantly smaller than the whole network diameter. By mapping the problem onto bond percolation, we give a theoretical explanation for the presence of this short influence radius, and a framework to quantify individual's influence in real OSNs. We then propose a scalable optimization algorithm to identify the most influential spreaders. The time complexity of our algorithm is independent of network size, and its performance is remarkably close the true optimum. Our method may be applied to other large scale spreading problems, such as the world-wide epidemic control.

This publication has 18 references indexed in Scilit: