Using Node Centrality and Optimal Control to Maximize Information Diffusion in Social Networks

Abstract

We model information dissemination as a susceptible-infected epidemic process and formulate a problem to jointly optimize seeds for the epidemic and time varying resource allocation over the period of a fixed duration campaign running on a social network with a given adjacency matrix. Individuals in the network are grouped according to their centrality measure and each group is influenced by an external control function---implemented through advertisements---during the campaign duration. The aim is to maximize an objective function which is a linear combination of the reward due to the fraction of informed individuals at the deadline, and the aggregated cost of applying controls (advertising) over the campaign duration. We also study a problem variant with a fixed budget constraint. We set up the optimality system using Pontryagin's Maximum Principle from optimal control theory and solve it numerically using the forward-backward sweep technique. Our formulation allows us to compare the performance of various centrality measures (pagerank, degree, closeness and betweenness) in maximizing the spread of a message in the optimal control framework. We find that degree---a simple and local measure---performs well on the three social networks used to demonstrate results: scientific collaboration, Slashdot and Facebook. The optimal strategy targets central nodes when the resource is scarce, but non-central nodes are targeted when the resource is in abundance. Our framework is general and can be used in similar studies for other disease or information spread models---that can be modeled using a system of ordinary differential equations---for a network with a known adjacency matrix.

12 pages, 11 figures. Author's version of an article published in IEEE Transactions on Systems, Man, and Cybernetics: Systems. Minor typos were fixed in v2. The published version can be accessed at http://dx.doi.org/10.1109/TSMC.2016.2531690

References in corpus (5)

• Structure and tie strengths in mobile communication networks
• What's in a crowd? Analysis of face-to-face behavioral networks
• How to Run a Campaign: Optimal Control of SIS and SIR Information Epidemics
• Optimal control of information epidemics modeled as Maki Thompson rumors
• Seed Selection for Spread of Influence in Social Networks: Temporal vs. Static Approach

Cited by in corpus (4)

• A Survey on Centrality Metrics and Their Implications in Network Resilience
• Publishing Community-Preserving Attributed Social Graphs with a Differential Privacy Guarantee
• How to choose the most appropriate centrality measure? A decision tree approach
• Optimal control of a kinetic model describing social interactions on a graph