Back to Search
Start Over
Large-scale influence maximization via maximal covering location
- Source :
- Güney, E, Leitner, M, Ruthmair, M & Sinnl, M 2021, ' Large-scale influence maximization via maximal covering location ', European Journal of Operational Research, vol. 289, no. 1, pp. 144-164 . https://doi.org/10.1016/j.ejor.2020.06.028, European Journal of Operational Research, 289(1), 144-164. Elsevier
- Publication Year :
- 2021
-
Abstract
- Influence maximization aims at identifying a limited set of key individuals in a (social) network which spreads information based on some propagation model and maximizes the number of individuals reached. We show that influence maximization based on the probabilistic independent cascade model can be modeled as a stochastic maximal covering location problem. A reformulation based on Benders decomposition is proposed and a relation between obtained Benders optimality cuts and submodular cuts for correspondingly defined subsets is established. We introduce preprocessing tests, which allow us to remove variables from the model and develop efficient algorithms for the separation of Benders cuts. Both aspects are shown to be crucial ingredients of the developed branch-and-cut algorithm since real-life social network instances may be very large. In a computational study, the considered variants of this branch-and-cut algorithm outperform the state-of-the-art approach for influence maximization by orders of magnitude.
- Subjects :
- Mathematical optimization
Information Systems and Management
General Computer Science
Relation (database)
Computer science
0211 other engineering and technologies
Stochastic programming
Scale (descriptive set theory)
02 engineering and technology
Management Science and Operations Research
Industrial and Manufacturing Engineering
Submodular set function
Set (abstract data type)
0502 economics and business
Integer programming
Large scale optimization
050210 logistics & transportation
021103 operations research
05 social sciences
Probabilistic logic
Maximization
Influence maximization
Modeling and Simulation
Networks
Subjects
Details
- Language :
- English
- ISSN :
- 03772217
- Volume :
- 289
- Issue :
- 1
- Database :
- OpenAIRE
- Journal :
- European Journal of Operational Research
- Accession number :
- edsair.doi.dedup.....7f7640c5a19ec4f177bf66767f911c34