# Large-scale multi-objective influence maximisation with network downscaling

arXiv: https://arxiv.org/abs/2204.06250 · HTML: https://mlsanity.com/paper/2204.06250/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 13 Apr 2022.

## Builds on (most cited first, 10 of 10)

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [Scale-free networks are rare](https://mlsanity.com/paper/1801.03400/) (2018)
- [Nonparametric Bayesian inference of the microcanonical stochastic block model](https://mlsanity.com/paper/1610.02703/) (2016)
- [Graph Summarization Methods and Applications: A Survey](https://mlsanity.com/paper/1612.04883/) (2016)
- [Top influencers can be identified universally by combining classical centralities](https://mlsanity.com/paper/2006.07657/) (2020)
- [A Multi-Transformation Evolutionary Framework for Influence Maximization in Social Networks](https://mlsanity.com/paper/2204.03297/) (2022)
- [Organization Mining Using Online Social Networks](https://mlsanity.com/paper/1303.3741/) (2013)
- [Graph-Aware Evolutionary Algorithms for Influence Maximization](https://mlsanity.com/paper/2104.14909/) (2021)

## Built on by (most cited first, 1 of 1)

- [Many-Objective Evolutionary Influence Maximization: Balancing Spread, Budget, Fairness, and Time](https://mlsanity.com/paper/2403.18755/) (2024)

## Abstract (arXiv)

Finding the most influential nodes in a network is a computationally hard problem with several possible applications in various kinds of network-based problems. While several methods have been proposed for tackling the influence maximisation (IM) problem, their runtime typically scales poorly when the network size increases. Here, we propose an original method, based on network downscaling, that allows a multi-objective evolutionary algorithm (MOEA) to solve the IM problem on a reduced scale network, while preserving the relevant properties of the original network. The downscaled solution is then upscaled to the original network, using a mechanism based on centrality metrics such as PageRank. Our results on eight large networks (including two with ~50k nodes) demonstrate the effectiveness of the proposed method with a more than 10-fold runtime gain compared to the time needed on the original network, and an up to 82% time reduction compared to CELF.