A bridge between influence models and control methods

Abstract

Abstract Understanding how influence is seeded and spreads through social networks is an increasingly important study area. While there are many methods to identify seed nodes that are used to initialize a spread of influence, the idea of using methods for selecting driver nodes from the control field in the context of seed selection has not been explored yet. In this work, we present the first study of using control approaches as seed selection methods. We employ a Minimum Dominating Set to develop a candidate set of driver nodes. We propose methods based upon driver nodes (i.e. Driver-Random, Driver-Degree, Driver-Closeness, Driver-Betweenness, Driver-Degree-Closeness-Betweenness, Driver-Kempe, Driver-Ranked) for selecting seeds from this set. These methods make use of centrality measures to rank the driver nodes in terms of their potential as seed nodes. We compare proposed methods to existing approaches using the Linear Threshold model on both real and synthetic networks. Our experiment results show that the proposed methods consistently outperform the benchmarks. We conclude that using driver nodes as seeds in the influence spread results in faster and thus more effective spread than when applying traditional methods.

Keywords

• Complex networks
• Influence spread
• Control
• Driver nodes
• Seed selection methods