Learning Parameters for Balanced Index Influence Maximization
arXiv:2012.08067 · doi:10.1007/978-3-030-65351-4_14
Abstract
Influence maximization is the task of finding the smallest set of nodes whose activation in a social network can trigger an activation cascade that reaches the targeted network coverage, where threshold rules determine the outcome of influence. This problem is NP-hard and it has generated a significant amount of recent research on finding efficient heuristics. We focus on a {\it Balance Index} algorithm that relies on three parameters to tune its performance to the given network structure. We propose using a supervised machine-learning approach for such tuning. We select the most influential graph features for the parameter tuning. Then, using random-walk-based graph-sampling, we create small snapshots from the given synthetic and large-scale real-world networks. Using exhaustive search, we find for these snapshots the high accuracy values of BI parameters to use as a ground truth. Then, we train our machine-learning model on the snapshots and apply this model to the real-word network to find the best BI parameters. We apply these parameters to the sampled real-world network to measure the quality of the sets of initiators found this way. We use various real-world networks to validate our approach against other heuristic.
References in corpus (7)
- Identification of influential spreaders in complex networks
- Mixing patterns in networks
- Influence maximization in complex networks through optimal percolation
- Supervised Random Walks: Predicting and Recommending Links in Social Networks
- Efficient collective influence maximization in cascading processes with first-order transitions
- Threshold driven contagion on weighted networks
- Influence Maximization for Fixed Heterogeneous Thresholds