Optimal Detection of Influential Spreaders in Online Social Networks

Abstract

The wide availability of digital data in online social networks such as the Facebook offers an interesting question on finding the influential users based on the user interaction over time. An example is the clicking of the Facebook "Like" button to endorse a digital object (e.g., a post or picture) posted by other user. This online interaction activity connects users sharing similar opinions or disposition and spreads their influence. In this paper, we study the estimation problem of finding a small number of users in the online social network who are influential in maximizing the reach of a digital message when it originates from them. The digital interaction in the online social network can be modeled using an interaction graph, e.g., associate users through the past record of snapshot observations of Like\'s activity in Facebook. We propose a network centrality approach in which we first use graph convexity to characterize the relative influential level of users on the interaction graph. We then propose a message passing algorithm to rank these users in order to identify the influential spreaders who play a forward-engineering role in catalyzing the spread of a new message. A useful application is to schedule a cascade of endorsement of a digital marketing message or for a business entity with a Facebook presence to find a number of Facebook users to spread the word of new commercial products. Lastly, we describe the performance of our algorithm using a synthetic dataset.