A Hybrid Approach For Enhanced Influence Maximization Integrating Independent Cascade and Linear Threshold Dynamics For More Reliable Seed Selection in Social Networks

Abstract

Understanding how information, opinions, and behaviors spread through a social network is central to problems as varied as viral marketing, public-health messaging, and platform design, and the node-selection problem at the heart of this — influence maximization — has been studied for close to two decades. Most of that work leans on one of two diffusion models: the Independent Cascade Model (ICM), which treats influence as a probabilistic event between neighbors, or the Linear Threshold Model (LTM), which treats it as a cumulative, threshold-crossing process. Each model captures a real pattern of social behavior, but neither captures both, and real diffusion processes rarely respect the boundary between them. This paper starts from a simple empirical observation — that ICM and LTM trade places as the better predictor depending on network density and seed-set size — and builds a hybrid model that lets both mechanisms act together rather than forcing a choice between them. The hybrid combines the two models' influence-spread estimates through a tunable weighting parameter, and a greedy seed-selection procedure optimizes over the combined signal rather than either model alone. Tested on a real character-interaction network (Game of Thrones) as well as four synthetic and real-world graphs of varying size and density, the hybrid consistently outperforms both individual models, with influence-spread gains of 13–15.5% over the stronger baseline and only modest additional computational cost. The results suggest that treating diffusion as a blend of probabilistic and threshold-based behavior, rather than picking a single mechanism, is a more faithful — and more effective — way to model influence spread in networks with mixed structural properties.