Learning Parameters for Balanced Index Influence Maximization
This work provides an incremental improvement for researchers and practitioners working on influence maximization by offering a data-driven method to tune an existing heuristic algorithm.
This paper addresses the challenge of tuning parameters for the Balance Index (BI) algorithm in influence maximization, a problem that is NP-hard. The authors propose a supervised machine learning approach that uses graph features and random-walk-based sampling to learn optimal BI parameters from small network snapshots. This model is then applied to real-world networks to find effective initiator sets.
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.