Influence Maximization for Fixed Heterogeneous Thresholds
arXiv:1803.02961 · doi:10.1038/s41598-019-41822-w
Abstract
Influence Maximization is a NP-hard problem of selecting the optimal set of influencers in a network. Here, we propose two new approaches to influence maximization based on two very different metrics. The first metric, termed Balanced Index (BI), is fast to compute and assigns top values to two kinds of nodes: those with high resistance to adoption, and those with large out-degree. This is done by linearly combining three properties of a node: its degree, susceptibility to new opinions, and the impact its activation will have on its neighborhood. Controlling the weights between those three terms has a huge impact on performance. The second metric, termed Group Performance Index (GPI), measures performance of each node as an initiator when it is a part of randomly selected initiator set. In each such selection, the score assigned to each teammate is inversely proportional to the number of initiators causing the desired spread. These two metrics are applicable to various cascade models; here we test them on the Linear Threshold Model with fixed and known thresholds. Furthermore, we study the impact of network degree assortativity and threshold distribution on the cascade size for metrics including ours. The results demonstrate our two metrics deliver strong performance for influence maximization.
arXiv comment23 pages, 9 figures
References in corpus (25)
- Assortative mixing in networks
- Epidemic processes in complex networks
- Identification of influential spreaders in complex networks
- Cascade-based attacks on complex networks
- Influence maximization in complex networks through optimal percolation
- Vital nodes identification in complex networks
- Modeling Cascading Failures in the North American Power Grid
- Evidence of Complex Contagion of Information in Social Media: An Experiment Using Twitter Bots
- Optimal network modularity for information diffusion
- Network dismantling
- Bootstrap Percolation on Complex Networks
- Identifying optimal targets of network attack by belief propagation
- Threshold cascades with response heterogeneity in multiplex networks
- The Physics of Living Neural Networks
- Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
- Threshold-limited spreading in social networks with multiple initiators
- Optimizing spread dynamics on graphs by message passing
- The Impact of Heterogeneous Thresholds on Social Contagion with Multiple Initiators
- Local cascades induced global contagion: How heterogeneous thresholds, exogenous effects, and unconcerned behaviour govern online adoption spreading
- Efficient collective influence maximization in cascading processes with first-order transitions
- On Bootstrap Percolation in Living Neural Networks
- Threshold driven contagion on weighted networks
- Cascading failures in spatially-embedded random networks
- Dominating Scale-Free Networks Using Generalized Probabilistic Methods
- Optimal information diffusion in stochastic block models