# Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2016.

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

- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [Graph Representation Learning for Popularity Prediction Problem: A Survey](https://mlsanity.com/paper/2203.07632/) (2022)
- [Finding Influencers in Complex Networks: An Effective Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2309.07153/) (2023)
- [Jointly Complementary&Competitive Influence Maximization with Concurrent Ally-Boosting and Rival-Preventing](https://mlsanity.com/paper/2302.09620/) (2023)
- [Online Influence Maximization: Concept and Algorithm](https://mlsanity.com/paper/2312.00099/) (2023)

## Abstract (arXiv)

The steady growth of graph data from social networks has resulted in wide-spread research in finding solutions to the influence maximization problem. In this paper, we propose a holistic solution to the influence maximization (IM) problem. (1) We introduce an opinion-cum-interaction (OI) model that closely mirrors the real-world scenarios. Under the OI model, we introduce a novel problem of Maximizing the Effective Opinion (MEO) of influenced users. We prove that the MEO problem is NP-hard and cannot be approximated within a constant ratio unless P=NP. (2) We propose a heuristic algorithm OSIM to efficiently solve the MEO problem. To better explain the OSIM heuristic, we first introduce EaSyIM - the opinion-oblivious version of OSIM, a scalable algorithm capable of running within practical compute times on commodity hardware. In addition to serving as a fundamental building block for OSIM, EaSyIM is capable of addressing the scalability aspect - memory consumption and running time, of the IM problem as well. Empirically, our algorithms are capable of maintaining the deviation in the spread always within 5% of the best known methods in the literature. In addition, our experiments show that both OSIM and EaSyIM are effective, efficient, scalable and significantly enhance the ability to analyze real datasets.