Efficient presolving methods for the influence maximization problem
From MaRDI portal
Publication:6139380
Abstract: We consider the influence maximization problem (IMP) which asks for identifying a limited number of key individuals to spread influence in a network such that the expected number of influenced individuals is maximized. The stochastic maximal covering location problem (SMCLP) formulation is a mixed integer programming formulation that effectively approximates the IMP by the Monte-Carlo sampling. For IMPs with a large-scale network or a large number of samplings, however, the SMCLP formulation cannot be efficiently solved by existing exact algorithms due to its large problem size. In this paper, we attempt to develop presolving methods to reduce the problem size and hence enhance the capability of employing exact algorithms in solving large-scale IMPs. In particular, we propose two effective presolving methods, called strongly connected nodes aggregation (SCNA) and isomorphic nodes aggregation (INA), respectively. The SCNA enables to build a new SMCLP formulation that is potentially much more compact than the existing one, and the INA further eliminates variables and constraints in the SMCLP formulation. A theoretical analysis on two special cases of the IMP is provided to demonstrate the strength of the SCNA and INA in reducing the problem size of the SMCLP formulation. We integrate the proposed presolving methods, SCNA and INA, into the Benders decomposition algorithm, which is recognized as one of the state-of-the-art exact algorithms for solving the IMP. We show that the proposed SCNA and INA provide the possibility to develop a much faster separation algorithm for the Benders cuts. Numerical results demonstrate that with the SCNA and INA, the Benders decomposition algorithm is much more effective in solving the IMP in terms of solution time.
Recommendations
- Large-scale influence maximization via maximal covering location
- An efficient linear programming based method for the influence maximization problem in social networks
- Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem
- An exact method for influence maximization based on deterministic linear threshold model
- A two-stage stochastic programming approach for influence maximization in social networks
Cites work
- scientific article; zbMATH DE number 1931795 (Why is no real title available?)
- scientific article; zbMATH DE number 7124428 (Why is no real title available?)
- A note on thresholds and connectivity in random directed graphs
- A strong-connectivity algorithm and its applications in data flow analysis
- A two-stage stochastic programming approach for influence maximization in social networks
- An efficient linear programming based method for the influence maximization problem in social networks
- Bootstrap percolation in directed inhomogeneous random graphs
- COBRA: A new formulation of the classic \(p\)-median location problem
- Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
- Connectivity of a general class of inhomogeneous random digraphs
- Exact approaches to the single-source network loading problem
- Human sexual contact network as a bipartite graph
- Improving connectivity of compromised digital networks via algebraic connectivity maximisation
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Large-scale influence maximization via maximal covering location
- Least cost influence propagation in (social) networks
- Least-cost influence maximization on social networks
- Monotonic optimization: Problems and solution approaches
- Presolve Reductions in Mixed Integer Programming
- Probabilistic partial set covering with an oracle for chance constraints
- The average connectivity of a graph
- The sample average approximation method for stochastic discrete optimization
- Using dual presolving reductions to reformulate cumulative constraints
Cited in
(3)
This page was built for publication: Efficient presolving methods for the influence maximization problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139380)
