Efficient presolving methods for the influence maximization problem

DOI10.1002/NET.22161zbMATH Open1530.91479arXiv2101.00393OpenAlexW4383102427MaRDI QIDQ6139380FDOQ6139380

Jianhua Yuan, Yuhong Dai, Shengjie Chen, Author name not available (Why is that?), Wei-Kun Chen

Publication date: 18 December 2023

Published in: Networks (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2101.00393

zbMATH Keywords

integer programmingstochastic programminginfluence maximizationBenders decompositionpresolving methods

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Stochastic programming (90C15) Integer programming (90C10)

Cites Work

• COBRA: A new formulation of the classic \(p\)-median location problem
• The sample average approximation method for stochastic discrete optimization
• A strong-connectivity algorithm and its applications in data flow analysis
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Title not available (Why is that?)
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• The average connectivity of a graph
• Human sexual contact network as a bipartite graph
• Title not available (Why is that?)
• Using dual presolving reductions to reformulate cumulative constraints
• Monotonic optimization: Problems and solution approaches
• Presolve Reductions in Mixed Integer Programming
• Exact approaches to the single-source network loading problem
• Bootstrap percolation in directed inhomogeneous random graphs
• Probabilistic Partial Set Covering with an Oracle for Chance Constraints
• Least cost influence propagation in (social) networks
• Least-Cost Influence Maximization on Social Networks
• Title not available (Why is that?)
• A two-stage stochastic programming approach for influence maximization in social networks
• Large-scale influence maximization via maximal covering location
• Improving connectivity of compromised digital networks via algebraic connectivity maximisation
• An efficient linear programming based method for the influence maximization problem in social networks
• Connectivity of a general class of inhomogeneous random digraphs

Cited In (3)

• Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization
• Large-scale influence maximization via maximal covering location
• Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem

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)