Heuristic centrality methods challenge greedy optimization in influence maximization.

Heuristic centrality methods challenge greedy optimization in influence maximization - PMC Skip to main content An official website of the United States government Here's how you know Here's how you know Search Log in Primary site navigation Search Log in Search PMC Full-Text Archive Search in PMC Journal List User Guide As a library, NLM provides access to scientific literature. Inclusion in an NLM database does not imply endorsement of, or agreement with, the contents by NLM or the National Institutes of Health. Learn more: PMC Disclaimer | PMC Copyright Notice Sci Rep . 2026 Apr 11;16:17085. doi: 10.1038/s41598-026-47299-8 Heuristic centrality methods challenge greedy optimization in influence maximization Laiali Almazaydeh 1 , Arar Al Tawil 2, ✉ , Amneh Shaban 3 , Rabiah Al-Qudah 1 Author information Article notes Copyright and License information 1 College of Engineering, Abu Dhabi University, Abu Dhabi, United Arab Emirates 2 Computer Science Department, Faculty of Information Technology, Applied Science Private University, Amman, 11937 Jordan 3 Software Engineering Department, Faculty of Information Technology, Applied Science Private University, Amman, 11937 Jordan ✉ Corresponding author. Received 2026 Jan 5; Accepted 2026 Mar 31; Collection date 2026. © The Author(s) 2026 Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/ . PMC Copyright notice PMCID: PMC13230769  PMID: 41965883 Abstract Influence maximization is a process where a small number of nodes are selected from social networks to maximize the spread of information. Many of the algorithms designed are supported by strong theory, but we do not know enough about their practical performance. This paper presents an extensive empirical analysis of eight representative algorithms from three paradigms: greedy optimization (CELF++), sampling-based approximation (RIS, IMM) and structural heuristics (Degree, PageRank, Betweenness, Dangling, and GCCDC). We tested Facebook social network subgraphs containing 200, 400, 600, 800, and 1,000 nodes through 10 independent runs under the Independent Cascade model for each configuration to obtain statistically reliable results. The findings indicate a significant disparity between theoretical guarantees and actual performance: despite achieving of CELF++ approximation guarantee, CELF++ only achieves 11.2% of the spread attainable using sampling-based algorithms this gap is likely due to an insufficient number of Monte Carlo simulations and implementation constraints as opposed to a fundamental algorithmic flaw. Across all network scales, the sampling-based methods showed nearly optimal performance (IMM: ; RIS: ). Importantly, PageRank achieved 96.3% of IMM’s spread quality while being 794 times faster than the latter, which further proves that complex algorithms aren’t necessary for competing results. Betweenness centrality was found to perform as effectively as PageRank among new centrality measures while Dangling centrality and GCCDC performed as effectively as Degree centrality. All the differences in performance were found to be significantly different. The experimental results show that certain simple heuristics can outperform highly-optimized methods in practice and that theoretical guarantees do not always correlate with reality. Keywords: Influence maximization, Social network analysis, Algorithm comparison, Independent cascade model, Viral marketing Subject terms: Engineering, Mathematics and computing Introduction Today, everything is being digitalized. The digital age has changed everything. One such thing is the social networks. Social networks have changed the way information is being transferred in today’s world. Social media sites such as Facebook, Twitter, Instagram, etc. all facilitate quick and widespread production and dissemination of content. Marketing strategies, public health communication, political mobilization, and misinformation suppression this disrupted 1 , 2 . Organizations with limited budgets face the practical challenge of finding a small number of highly influential people whose adoption or endorsement can create information cascades across the network. Viral marketing campaigns to encourage adoption of products make use of influential people to engage customers. Vaccination awareness initiatives leverage key community actors to encourage positive health behaviours. Political campaigns mobilise opinion leaders to sway voters. And misinformation control efforts target key nodes in the network to stem the flow of false narratives 3 . The effectiveness or ineffectiveness of any campaign largely depends upon optimally choosing such influencers. Thus, influence maximization holds much importance. The influence maximization problem is formally defined as choosing a subset of ( k ) seed nodes in a social network such that its expected influence spread is as large as possible through a stochastic diffusion process. This refers to the fact that information, behaviours or innovations are transferred from person to person in a social network with some probabilities (not certain) 4 – 6 . Practitioners must strike a balance between high quality influence spread and computational feasibility, which necessitates designing algorithms that can deliver good results in a reasonable time period 7 . Efforts are being made to strike a balance between efficiency and effectiveness, as seen by the evolution of such influence maximization algorithms. At one extreme, simple heuristics, such as Degree centrality and PageRank, can be computed in seconds. However, such algorithms may not identify the best (or near-best) seed set. On the flip side, sophisticated greedy algorithms guarantee robust theoretical performance but impose extremely costly computation, making their implementation limited to small networks 5 . Intermediate strategies, like modern sampling-based approaches, claim to merge the benefits of both extremes by providing a nearly optimal influence spread but much better runtime efficiency. The CELF++ optimization makes use of lazy evaluation so as not to perform calculations that do not contribute to the end result. It provides speedups of several hundred times over the naive implementation while maintaining approximation guarantees 8 .Despite the advancements in technology today, each of these algorithms improves by itself. Comparative empirical evaluation of these different algorithms under the same settings is very limited. This is a key research gap due to the lack of systematic, comparative evaluations. Most of the existing studies focus on algorithms that are similar to or better than the existing baselines in a one network scenario 9 . As a result, professionals don’t have any explicit evidence-based directions on choosing algorithms that are well-tailored to their needs and constraints. When does relative simplicity of standard algorithms make them preferable to sophisticated algorithms? When might simple heuristics lead to adequately effective solutions? 10 To what extent do these algorithms scale in relation to the size and structure of the network? It is unlikely we will bridge the theory-practice gap without detailed empirical assessments at different scales and with real world datasets that enable evidence-based decision-making in application. In order to address this gap, this research work presents a comparative analysis of eight representative influence maximization algorithms which are falling under greedy, sampling-based and heuristic categories. The study used actual Facebook social network data and systematically varied the graph size from 200 to 1000 nodes to test for robustness and scale performance 7 . To guarantee statistical robustness, we perform ten independent runs for every experimental configuration followed by significance testing of observed differences. The evaluation of the criteria includes quality of spread of influence, run time, scalability, and trade-off between effectiveness and efficiency 11 . The objective is to offer practitioners practical guidance and evidence-based advice in the selection of algorithms; furthermore to examine theoretical assumptions in a social network context. The key contributions of this research are as follows: The study provides the first detailed empirical comparison of recent influence maximization algorithms from three different methodological classes greedy (CELF++), sampling-based (RIS, IMM), and centrality heuristics (Degree, PageRank, Betweenness, Dangling, GCCDC) applied to real-world social network data with rigorous statistics. It shows that, while CELF++ has a theoretical approximation guarantee of , it performs much worse in our experiments. We suspect this is due to limited Monte Carlo simulations and implementation difficulties. The results show that PageRank and Betweenness centrality, which are simple structural heuristics, achieve more than 96% of the performance of the state-of-the-art IMM algorithm while running orders of magnitude faster. This result challenges the notion that algorithmic complexity is required to achieve state-of-the-art performance. The scalability analysis offers an insight into performance and computational cost as the number of network nodes increases. It will help practitioners select an algorithm that meets their resource constraints. The statistical tests, raw data and source code are made available in a public repository to ensure full reproducibility. It gives practical and evidence-based advice on the selection of algorithms under different operational conditions. It includes uses that are quality-critical, balanced and time-critical. The rest of this paper is organized as follows. Section 2 reviews related work on influence maximization algorithms. Section 3 describes the experimental methodology, including dataset characteristics, parameter settings and evaluation metrics. Section 4 provides results including performance comparison, scaling, run-time analysis, and statistical testing. In Section  5 of the paper, we discuss the implications of our findings, the interpretation of unexpected outcomes, and the practical considerations for selecting algorithms. Section 6 ends with conclusions and possible future research directions. Related work Kempe et al. first formalized the influence maximization problem 12 , Contemporary social network applications have evolved from an academic issue to a practical need. The discussion will cover the greedy and sampling-based algorithms that laid the foundations for this discipline, up until new deep learning developments emerged. Table 1 summarizes the key algorithms discussed in this section. Table 1. Summary of key influence maximization algorithms. Algorithm Year Complexity Key feature Greedy 12 2003 O ( knm ) guarantee CELF 18 2007 O ( knm ) speedup CELF++ 19 2011 O ( knm ) 35–55% faster than CELF DegreeDiscount 20 2009 Millisecond runtime MIA 21 2010 Tree-based approximation RIS 25 2014 Reverse sampling TIM/TIM+ 26 2014 Billion-edge graphs IMM 27 2015 Martingale theory SSA 28 2016 Optimal sampling OPIM 30 2018 Online processing PageRank 33 2015 Centrality-based VoteRank 35 2016 Iterative voting PIANO 46 2023 Varies Deep RL approach Open in a new tab Foundational work and theoretical guarantees Domingos and Richardson 13 , 14 were the first to propose algorithms to find influencers in viral marketing. Kempe, Kleinberg, and Tardos 12 provided a rigorous theoretical framework for research on the topic in question. In their research study, the authors proved that influence maximization is NP-hard under the Independent Cascade (IC) and Linear Threshold (LT) models. However, they also showed that because of the submodular structure of influence functions, a greedy algorithm has a approximation guarantee 15 . This was the first result to show that due to the hardness of the problem, close to optimal solutions are possible. This has led to the development of algorithms for two decades and more. As a strengthening of the above statement, Mossel and Roch 16 established similar guarantees for general threshold models. The journal version 17 contains all the proofs and experiments that establish the Independent Cascade model as the accepted model for influence diffusion. Although Kempe’s greedy algorithm is guaranteed theoretically, its O ( knm ) time complexity means that we have to perform expensive Monte Carlo simulations for every candidate node. This makes it impractical for large networks. In 18 , Leskovec et al. propose the Cost-Effective Lazy Forward (CELF) algorithm making use of submodularity’s diminishing return to get a staggering speedup of by way of lazy evaluation. CELF postpones costly influence calculations by keeping track of an upper bound on marginal gains, only recomputing them when needed. Goyal et al. 19 further improved this with CELF++, which he claimed would provide an additional improvement of 35-55% through lazy-lazy evaluation. Chen et al. significantly advanced scalability through multiple innovations. Their NewGreedy algorithm 20 reused Monte Carlo simulations across iterations, while the DegreeDiscount heuristic offered millisecond-scale approximations for time-sensitive applications.To tackle networks with a million scale, the Maximum Influence Arborescence (MIA) framework 21 , 22 has been developed, which achieves approximation through local trees rather than using global simulation. Variants of Linear Threshold model have received focused attention through SIMPATH 23 and specialized algorithms 24 . Even with these improvements, greedy techniques proved to be too limited in their iterative structure, leading to a change to sampling-based ones. Borgs et al. 25 introduced Reverse Influence Sampling (RIS) which revolutionized the field, transforming influence maximization into a set cover problem. The approach for Reverse reachable Influence Sets (RIS) generates random reverse-reachable (RR) sets from the target nodes chosen at random instead of estimating the influence in the forward direction from the seed nodes. Time complexity of the RIS technique is reduced from O(knm) to almost linear time. Tang and others executed this model using TIM and TIM+ 26 , These systems achieves unprecedented scalability, processing billion-edge graphs in under an hour, with approximation guarantees. The study demonstrated that looks can be functional and performance can be aesthetic. The influential algorithm IMM (Influence Maximization via Martingales) 27 improved the solution RIS through sampling theory based on martingales, which produced tighter theoretical guarantees together with better empirical performance. The sampling-based influence maximization method IMM became a de facto standard, resulting in many extensions. Nguyen et al. 28 introduced SSA with optimal sampling checkpoints, though Huang et al. 29 identified and corrected approximation guarantee issues in the original formulation. Tang et al. 30 developed OPIM for online processing scenarios requiring early termination capabilities. Recent improvements include HIST 31 , which strengthens the theoretical bounds through subset sampling strategies. Sampling-based methods preside over large-scale applications these days because of their better speed, quality and theoretical guarantees. Heuristic approaches and centrality-based methods Heuristic methods, while lacking theoretical guarantees, are appealing for situations requiring quick results or where they can be used as a preprocessing filter. Degree-based methods 32 select high-degree nodes, which are individuals who have a lot of connections. PageRank-based methods 33 , 34 exploit the power-law influence distributions of social networks. Signed PageRank variants 34 consider networks with positive and negative relationships. The iterative voting mechanism has been proposed in VoteRank 35 , where the selected nodes reduce the influence scores of their neighbours to escape redundant selections which take place in local neighbourhoods of the nodes. Community-based techniques 36 – 39 divide networks into modules and choose influential nodes in each community. They leverage network modularity to reduce computational complexity and obtain coverage at every edge of the network. These methods leverage the fast-provisioning aspect of simple heuristics, along with the quality improvement of structural awareness, at the expense of the theoretical guarantees provided by greedy and sampling-based methods. Comparative studies and benchmarking The proliferation of influence maximization algorithms necessitates rigorous comparative evaluation. Arora et al. 40 We performed the largest benchmark study carried out to date involving 11 algorithms. We tested these algorithms on multiple diffusion models and network datasets. The researchers found no single one of the existing state-of-the-art techniques performs best on all metrics. This finding casts doubt on the notion of “winner” algorithms and implies the importance of matching an algorithm to the requirements of specific applications.Lu et al. 41 have questioned the experimental methodologies along with the discussion over evaluation metrics. The suite of Influence Maximization Benchmarker 42 has standardized tools for evaluation reproducing. Jung et al. 43 and Ohsaka et al. 44 provide analyses of algorithms that substantiate the speed-memory-likeness trade-offs. The set of SNAP dataset collections 45 provides standard benchmarks like Twitter (41.6M nodes, 1.4B edges), LiveJournal (5M nodes, 69M edges), Orkut (3M nodes, 117M edges). So that other papers can compare with their work. Recent trends: deep learning and machine learning approaches One of the most important developments of late concerns the application of deep reinforcement learning and graph neural networks to influence maximization. Li et al. 46 developed PIANO, a system that employs reinforcement learning to establish seed selection policies, tailored to specific network characteristics without the need for hand-crafted heuristics. Ling et al. 47 proposed deep graph representation learning frameworks that optimize node embeddings and influence estimation jointly. Chen and colleagues 48 and Yang and colleagues 49 proved deep reinforcement learning can achieve a competitive performance as theoretical algorithms while generalizing better across network types. Graph neural network approaches 50 – 52 learn influence and strategies directly from the structure of the network, enabling techniques like transfer learning for similar networks and amortization of training costs for multiple influence maximization instances. These methods are moving away from the direction of algorithm design towards that of learned optimization, although they presently lack the classical guarantees. Therefore, fairness-aware extensions 53 , 54 have been suggested in order to ensure fairness under them. Research gaps and motivation There are still important gaps despite extensive research. Many existing researches propose a new algorithm as the sole contribution and include only fewer baselines with a direct comparison with only the immediate predecessor limited only to one network. There hasn’t been any extensive empirical study with statistical rigor to compare greedy optimization (CELF++), sampling-based methods (RIS, IMM), and simple heuristics (Degree, PageRank) over a wide range of scales. Moreover, theoretical complexity does not always predict practical performance, because hidden constants, dependencies on network structure, and implementation matter. To systematically evaluate algorithms from different paradigms, we conduct a rigorous statistical analysis over simulation and real social network data. The idea is to provide data-based guidance for selecting algorithms for real applications. Methods Problem formulation Let be a social network such that V is the node set (users) with and E is the edge set (social connections) with The influence maximization problem focuses on the determination of a seed set of size k that will maximize the expected influence spread according to a diffusion model BP or some other model. In our analysis we utilize the Independent Cascade (IC) model 12 which stochastically spreads information throughout the network. We associate with each edge (u,v) in E an influence probability p_uv, the probability that node u activates node v. At the start of the diffusion process, one activates all the alternate nodes in S. Upon arriving at step t , each newly activated node at step tries to activate each of the inactive neighbors with the probability . The process terminates when no more activations occur. The spread of influence is the expected number of activated nodes by the end of the diffusion. Formally, the influence maximization problem is: 1 This optimization problem is NP-hard 12 , necessitating approximation algorithms for practical solutions. Algorithms We examine eight different algorithms that span three different paradigms and discuss their advantages. As depicted in Fig. 1 , the experimental workflow of the study. Fig. 1. Open in a new tab Experimental methodology workflow showing data preparation, algorithm execution, and evaluation pipeline. The framework compares eight algorithms across four graph sizes with statistical validation. CELF++ (cost-effective lazy forward plus plus) CELF++ 19 Improves the greedy algorithm using lazy evaluation. Instead of recomputing marginal gains for every candidate in every iteration, CELF++ maintains an upper bound on marginal gains and only recomputes when necessary. The algorithm maintains a priority queue of candidate nodes with estimates of their marginal gain. When the i -th seed is chosen, nodes are listed in decreasing order of upper bounds. In case the upper bound of a node was obtained for the current seed set (i.e., = ), then it gets selected immediately. Otherwise, its marginal gain gets recomputed. This was observed to achieve speedups of over naive greedy but with the same guarantee 18 . RIS (reverse influence sampling) RIS 25 , 26 takes a new approach which transforms influence maximization into set coverage problem using RR sets. For a target node v selected at random, the RR set of v comprises of every node which can reach v through reverse edges sampled by influence probabilities. The algorithm constructs RR sets in . The value of is determined through theoretical analysis to guarantee approximation. The selection of seeds thus amounts to the identification of k nodes that cover the most number of RR sets. This is carried out greedily. The reasoning behind this is that nodes covering expansive RR sets are likely to induce propagation to multiple nodes. RIS attains a near-linear time complexity of for -approximation. IMM (influence maximization via martingales) IMM 27 Improves RIS via Martingale-Based Concentration Inequalities and Adaptive Sampling. While RIS generates a predetermined number of RR sets, IMM modifies the sample size based on its observations of the coverage pattern. The algorithm calculates: 2 where controls the approximation accuracy. This adaptive approach tightens theoretical bounds while improving practical performance, making IMM the current standard for sampling-based influence maximization. Degree centrality The Degree heuristic chooses the most k connected nodes based on the idea that a highly connected node has a good influence. We can express degree centrality as d(v)=|N(v)|. Here, N(v) is the neighbor set. In other words, it is an algorithm which has no theoretical guarantees, runs quickly, and gives us a faster baseline. PageRank centrality The way PageRank function models influence as a stationary distribution of a random walk on the network 33 . The PageRank score PR ( v ) for node v satisfies: 3 The damping factor of is denoted by and is equal to . Furthermore, while denotes the incoming neighbours, is the out-degree of u . We choose nodes with the top k PageRank scores. This heuristic captures a network’s global structure, which is beyond mere connectivity. Hence it may help identify influential nodes that aren’t positioned in a very obvious way. Using version 2.6 of the library NetworkX with 0.85 as the damping factor, we used the power iteration method to compute the PageRank scores with a convergence tolerance of and maximum no. 100 iterations. The iterative method takes time to execute, where T is the number of iterations until convergence ( for social networks). Our study confirms the applicability of PageRank computation for time-critical applications. For all considered graph sizes, PageRank computation converged within 0.5 seconds. Betweenness centrality Betweenness centrality refers to the bridging nodes that lie on the shortest path between other nodes. It measures the ability of nodes to connect all others 55 . For a node v , the betweenness centrality is defined as: 4 In the above expression denotes the total number of shortest paths from node s to node t . Whereas, refers to a number of those paths that pass through v . In our implementation, we compute betweenness centrality via the NetworkX library using Brandes’ algorithm 56 with time complexity . The nodes with the first k highest betweenness scores are selected as seeds. Dangling centrality The removal of a link from a network can affect network connectivity. It measures this effect. This measure is called dangling centrality and it is used to measure network stability 55 , 57 For each node v , the dangling centrality DC ( v ) is defined as: 5 In this expression, refers to the connectivity score once the edge ( v , u ) is removed, whilst is the connectivity score of neighbour u with node v present. This metric identifies important nodes whose removal would greatly disrupt information flow. Our implementation using degree centrality as a proxy to assess connectivity impact runs in time of where is the average degree. Global clustering coefficient-dependent degree centrality (GCCDC) GCCDC combines the global clustering coefficient with degree centrality to create a comprehensive measure of node importance that takes into account not just local connectivity, but also the global clustering structure of the network 58 . For each node v : 6 where is the degree centrality, GCC is the global clustering coefficient of the network (transitivity), and LC ( v ) is the local clustering coefficient of node v . The idea is that in networks with high clustering, things would be easier for the nodes that have a dense cluster community. Experimental setup Dataset For the project we use Facebook social network dataset 45 which has 4,039 nodes and 88,234 undirected edges which represent friendships. We sample subgraphs with the number of nodes set to 200, 500, 800, and 1000 via importance sampling for a systematic study of scalability. The significance of a node is the average of its normalized degree centrality and normalized PageRank scores. To ensure that the selected nodes are connected, the top-ranked nodes are chosen by importance and their maximum importance neighbours are included. The strategy acts to filter the networks’ influence structure, allowing for scalabilities and experiments. The resultant subgraphs reflect the distinctive features of initiating a network while having higher degree exponent than 3. This further ensures that the simulated node networks are realistic (Fig. 2 ). Fig. 2. Open in a new tab Importance-based sampling results at four scales: ( a ) 200 nodes, ( b ) 500 nodes, ( c ) 800 nodes, ( d ) 1000 nodes. Node size and color represent degree centrality. Average degree and network density are shown for each subgraph. Parameters All experiments utilize the Independent Cascade model, in which the propagation probability is uniform on all edges. This is standard practice (Kempe et al., 2003, Tang et al., 2015). The seed budget k = 10, which is a reasonable limitation for viral marketing applications. To balance accuracy and computational cost, any assessment of the impact would entail using 50 Monte Carlo simulations. The specific parameters for every algorithm are specified here. CELF++ performs 50 simulations to estimate the marginal gain. For architecture RIS the RR sets are given by . For adaptive sampling we set the IMM sets . To ensure reliability, we run all configurations independently over 10 runs with different random seeds (42–51). In our experiment, we will be clear about what is being repeated at two levels. To begin with, influence evaluation runs 50 Monte Carlo simulation to compute an estimate of the expected spread for seed set S . Every simulation of Monte Carlo runs the IC diffusion process from the seed set once only, and average number of activated nodes in 50 simulations gives a good estimate of . Second, 10 independent runs of each algorithm are performed using different random seeds (42–51). Every independent run generates a potentially different seed set because, due to stochasticity in algorithms, e.g. random RR set generation in RIS/IMM, Monte Carlo estimation variance in CELF++. Thus, for sake of every algorithm-graph size configuration, we obtain 10 influence spread values. Each of these 10 values is estimated from the algorithm’s 50 Monte Carlo simulations. Hence, we have robust statistical measures (mean, standard deviation, coefficient of variation) for comparison of our estimates. All algorithms were implemented in Python within a unified experimental framework to ensure fair comparison under identical computational conditions, including shared data structures, random number generation, and Independent Cascade simulation code. Evaluation metrics The main performance metric we use is influence spread (i.e., the mean number of activated nodes) taken over 50 Monte Carlo simulations. The S Objective gives an overall score of how well the algorithm succeeded in locating a set of nodes without using the coverage measure. Computational time is defined as the elapsed time in seconds between when the algorithm starts until the last seed set output. In this way, we can see how efficient the algorithm is. The scalability increases the performance of the algorithm. As the graph size continues to increase, the speed of performance is capable of giving a full picture of what the algorithm does. Statistical Evaluations of the 10 Runs The mean, standard deviation, minimum, maximum, and coefficient of variation (CV) for these 10 runs are all calculated. To assess the significance paired t-tests (for the treatment conditions) with Bonferroni ( ) correction for multiple comparisons. Implementation details In Python 3.8, all algorithms are implemented using NumPy 1.21 for numerical operations and NetworkX 2.6 to build a graph. To reduce run time, vectorized operations are used in the Independent Cascade simulation. To implement priority queues for greedy algorithms we use Python’s heapq module Methods such as RIS, IMM are essentially set-based sampling techniques that utilize efficient set operations and thus allow efficient RR set generation and coverage computation. The experiments are performed on a standard computer with an Intel Core i7 processor and 16G RAM that can be repeated on multiple commodity hardware. The initialization of all random number generators remains consistent across simulations to ensure replicability. Results Across four scales of network, we present a comprehensive comparative evaluation of eight algorithms. All the experiments were run on importance-sampled subgraphs from the Facebook social network with 10 independent runs per configuration. Overall performance comparison Table 2 presents the complete statistical analysis across all eight algorithms and graph sizes, while Figure 5 provides a visual overview revealing stark contrasts in effectiveness. Table 2. Statistical summary of influence spread across eight algorithms and four network scales. Values represent mean ± standard deviation over 10 independent runs under the independent cascade model. Algorithm 200 nodes 500 nodes 800 nodes 1000 nodes CELF++ RIS IMM Degree PageRank Betweenness Dangling GCCDC Open in a new tab Fig. 5. Open in a new tab Performance heatmap visualizing mean influence spread across eight algorithms (rows) and network sizes (columns). Color intensity represents spread magnitude (yellow=low, red=high). The stark contrast between CELF++ (pale yellow) and other algorithms (darker red) visually emphasizes the substantial performance gap. IMM and RIS exhibit the deepest red coloration at all scales, confirming their dominance, while Betweenness and PageRank show nearly identical color patterns across all network sizes. The mean influence spread for the largest network configuration of 1000 nodes was achieved by IMM which had value of . Next was RIS achieving (Fig. 4 d). Among centrality heuristics, Betweenness centrality ( ) and PageRank ( ) achieved nearly identical performance, both substantially outperforming the simple Degree heuristic ( ). GCCDC ( ) performed comparably to Degree, while Dangling centrality ( ) ranked lowest among heuristics. CELF++ substantially underperformed at , attaining only 12.9% of the spread achieved by IMM a discrepancy most likely attributable to insufficient Monte Carlo simulations (50 per evaluation step) and implementation constraints, as discussed in detail in “Local heuristic methods (degree, dangling centrality, GCCDC)”. Fig. 4. Open in a new tab Box plot distributions showing eight algorithm performance variability across four network scales. Red lines indicate medians, circles show means, boxes span interquartile range (Q1–Q3), whiskers extend to min/max values. Sampling-based methods (RIS, IMM) demonstrate exceptional consistency (tight distributions), while CELF++ exhibits high variance and systematic underperformance. Among centrality heuristics, Betweenness and PageRank show tight distributions comparable to sampling methods, whereas Dangling centrality exhibits the highest variability among heuristics. This performance hierarchy remained consistent across all network scales (Figure 3 a). At 200 nodes, RIS ( ) and IMM ( ) achieved nearly identical performance, with CELF++ already showing weakness at . The performance gap widened substantially as networks scaled: CELF++’s relative performance deteriorated from 7.7% (200 nodes) to 1.0% (500 nodes) before partially recovering to 12.9% (1000 nodes) compared to the best-performing algorithm at each scale. Fig. 3. Open in a new tab An exhaustive four-panel characterisation of eight algorithms; ( a ) scalability trends for networks of different sizes, ( b ) run-time comparison on log scale, ( c ) efficiency metric (spread per second) demonstrates trade-offs, ( d ) final performance at n = 1000 with error bars. As panel ( c ) makes clear, PageRank is much cheaper (2,304 spread/s) than IMM which is of much higher quality (2.95 spread/s). According to ( d ), IMM (954.90) is better than RIS (952.53). Betweenness (921.80) is better than PageRank (921.78), but they are close. CELF++ performs very poorly (122.95). Statistical significance analysis Pairwise statistical comparisons for the 1000-node configuration (Table 3 ) confirm that nearly all performance differences are statistically significant ( ), with two exceptions noted below. Both the paired t-test, a parametric analysis, and the Mann-Whitney U test, a non-parametric analysis, gave us the same results. This suggests that our results are robust. Table 3. Pairwise statistical comparisons for the 1000-node configuration. All differences are statistically significant ( ) unless otherwise noted. Comparison t p IMM vs. RIS 2.36 2.57 IMM vs. PageRank 33.12 26.97 PageRank vs. Betweenness 0.99 GCCDC vs. Dangling 14.15 2.90 Degree vs. Dangling 13.43 2.67 IMM vs. CELF++ Open in a new tab A small but significant difference was observed between IMM and RIS, as IMM surpassed RIS by ( , ), confirming that IMM is marginally the better of the two. PageRank is inferior to IMM ( , , ) which is a meaningful 3.5% difference. One interesting output to analyze is that the difference between PageRank and Betweenness centrality is insignificant ( , , ). Thus, these heuristics are able to achieve virtually the same spreading despite using very different centralities. Both are significantly better than Degree centrality ( ), GCCDC ( ) and Dangling centrality ( ). The differences GCCDC and Dangling ( , ) and Degree and Dangling ( , ) are significant but small. CELF++ shows a significant deficiency relative to all other algorithms. The mean difference for the IMM is ( , ), or spread 87.1% lower. As noted in ““Local heuristic methods (degree, dangling centrality, GCCDC)”, this mismatch is likely due to the lack of Monte Carlo simulations and implementation limitations rather than a failure in the algorithm itself. Scalability analysis Figure 3 demonstrates how an algorithm scales with network size. Methods using sampling (e.g., RIS, IMM) as well as heuristics (Degree, PageRank, Betweenness) scale approximately linearly where growth rate of influence spread is roughly the same as that of network size. Table 4 records the quantified growth patterns, where IMM grew by 402%, RIS 399% and PageRank 403% and Degree 411% from 200 to 1000 nodes. Table 4. Scalability analysis showing performance growth from 200 to 1000 nodes. Growth percentages calculated relative to 200-node baseline performance. Algorithm 200 nodes 500 nodes 800 nodes 1000 nodes Spread Spread (Growth) Spread (Growth) Spread (Growth) CELF++ 14.64 4.91 (-66%) 60.86 (+316%) 122.95 (+740%) RIS 190.57 473.29 (+148%) 753.48 (+295%) 952.53 (+400%) IMM 190.23 473.40 (+149%) 753.97 (+296%) 954.90 (+402%) Degree 159.03 440.71 (+177%) 657.08 (+313%) 810.87 (+410%) PageRank 182.95 463.53 (+153%) 731.07 (+300%) 921.78 (+404%) Betweenness 184.05 465.35 (+153%) 732.45 (+298%) 921.80 (+401%) Dangling 144.30 457.82 (+217%) 684.57 (+374%) 797.44 (+453%) GCCDC 156.13 441.74 (+183%) 656.01 (+320%) 811.59 (+420%) Open in a new tab CELF++ exhibited a scaling behavior that varied significantly from others. According to the data, CELF++ does not work well because its growth is erratic. As the nodes increase from 200 to 1000, the growth is upward, which increases overall by 633%. Nonetheless, its performance begins to fall sharply at 500 nodes (4.56 spread) and then recovers partially. This behavior probably arises due to the lazy evaluation’s sensitivity to Monte Carlo estimation variance which are more pronounced at intermediate scales of networks where the gain landscape is less clear. The most probable cause of this instability is the insufficient simulation budget (50 MC runs), as discussed in “Local heuristic methods (degree, dangling centrality, GCCDC)”. The CV illustrates the accuracy and steadiness of the algorithm under consideration. All network sizes yielded the same performance for sampling based methods. Specifically, for IMM, the CV value ranged from 0.07% to 0.17%, while for RIS, the CV value ranged from 0.13% to 0.23%, with a slight variation but not much. Among the various heuristics for centrality, Betweenness centrality proved to be consistent, exhibiting a comparable consistency level to that of the sampling methods, with CV 0.16%–0.36%, while PageRank between 0.14% and 0.25%. The Degree heuristic was more dispersed and had CVs of 0.66%–2.59%. The heuristics with the highest variability was dangling centrality (CV reaches 6.24%), while GCCDC average variability was from 0.62% to 3.24%. The CV of CELF++ rose suddenly to 71.5% when network size is of 500 nodes, indicating a great instability in the quality of the solution, supporting the hypothesis that an inadequate number of Monte Carlo simulations leads to the untrustworthy estimation of marginal gain when network size is of 500 nodes. Computational efficiency Our method achieves high efficiency at all four levels according to the results. Heuristic methods (Degree, PageRank, and Dangling) are the fastest tier and take 0.5 seconds to execute on all networks. The second ring of mid-range heuristics is Betweenness centrality (0.3-8.8 seconds)/GCCDC (0.3-2.9 seconds). These heuristics produce a reasonably better spread quality at moderate implementation cost. The third group consisted of algorithms that use sampling: for RIS the running time was 11.8–64.9 seconds while for IMM it was 11.8–323.5 seconds. The CELF++ algorithm required 24.8 seconds to 688.4 seconds of computation time, which was the highest among all tested algorithms. Moreover, spread quality was the worst among all algorithms in the case of CELF++. The efficiency metric (spread per second, Fig. 3 c) clearly indicates the quality-speed trade-off. The fastest heuristics achieved the highest efficiency (i.e., PageRank performed 2304 spread/sec at 1000 nodes, followed by Degree (2027 spread/sec) and Dangling (1994 spread/sec). Betweenness centrality attained an 104.75 spread per second while GCCDC attained a 279.86 spread per second, offering a good quality and speed trade-off. With 14.68 spread/second, RIS competently balanced quality and speed. Similarly, the absolute spread was on the maximum side for IMM but at lowest efficiency amongst the competitive algorithms (2.95 spread/second). The spread of CELF++ was 0.18 spread/second which makes it have a high runtime and low-quality spread. Within the important configuration of 1000 nodes, PageRank rendered a spread of 921.78 in 0.4 seconds (2,304 spread/sec) while RIS achieved a spread of 952.53 in 64.9 seconds (14.68 spread/sec). This is a 3.3% quality improvement for a 162-fold increase in runtime, making PageRank very cost-effectiveness for those after near-optimal solutions. Betweenness centrality is a solution that offers an intermediate option. It achieves a spread of 921.80 in 8.8 seconds virtually the same quality as PageRank. However, the item is at a higher cost. This cost may be justified when identifying bridge-nodes is valuable in its own right. Algorithm-specific observations Sampling-based methods (RIS, IMM) Sampling-based methods are supported by the theoretical predictions validated by reverse influence sampling and martingale-based concentration inequalities. The marginal superiority of IMM (0.25% on average) is consistent with its tighter theoretical bounds, derived from martingale concentration inequalities. Both methods exhibited very low variance (std < 2.72 for all configurations), an indication of algorithmic stability. The gap in runtime between RIS and IMM increased as the network scaled up: IMM at 1000 nodes took 5 longer than RIS (323.5s vs 64.9s). These high computational costs entail meager quality gains, suggesting RIS can be chosen when quality differences are negligible. Global heuristic methods (PageRank, betweenness centrality) The substantial difference between PageRank and simple Degree centrality indicates the importance of the overall network structure over its local connectivity. The performance gap grew as the size of the network grew. In a network of 1000 nodes, for example, PageRank achieved a spread of 921.78, while Degree’s spread was 810.87 PageRank scored 13.7% better overall. Although the computational cost remained the same (0.4 s), PageRank is strictly better than Degree for this problem. Betweenness centrality 55 , 56 emerged as a strong competitor, achieving 921.80 spread at 1000 nodes statistically indistinguishable from PageRank ( ). Betweenness identifies bridge nodes lying on shortest paths between node pairs, capturing a fundamentally different aspect of network structure compared to PageRank’s random walk model. The near-identical performance suggests that in networks with high clustering coefficients, bridge nodes and structurally central nodes overlap significantly. However, Betweenness requires 8.8 seconds compared to PageRank’s 0.4 seconds due to its computational complexity, making PageRank the preferred choice when runtime is critical and Betweenness the preferred choice when bridge-node identification has independent value. The performance of PageRank and Betweenness in comparison to advanced sampling methods is notable. For real-time seed selection or large networks, PageRank offers an attractive quality, speed and simplicity trade-off, while Betweenness provides equivalent spread quality at a moderate computational cost. Local heuristic methods (degree, dangling centrality, GCCDC) Dangling centrality, Degree centrality 55 , 57 , and GCCDC 58 formed a lower-performing cluster among heuristic methods. At 1000 nodes, the spread of GCCDC (811.59) and Degree (810.87) was almost the same. Among all heuristics, Dangling centrality (797.44) was the lowest. The evaluation of stability in a network due to link deletion is referred to as dangling centrality. The dangling centrality heuristic had the highest CV (up to 6.24% at 200 nodes). The metric focuses on the impact of removing an edge and not on the global routes through which influence takes place. As the scale increases (say, from 100 to 500 nodes), other heuristics tend to have greater performance than ours. In fact, for 500 nodes, our heuristic ranks 5th with a spread of 457.82. This suggests that link-removal-based importance has more information to offer in intermediate scale networks with moderate density. GCCDC utilizes the degree centrality 58 , which is the global clustering coefficient, in an attempt to provide users with a richer alternative to pure degree because it accounts for clustering. The marginal difference in the performance of Degree centrality (811.59 as compared to 810.87 at 1000 nodes) suggests that including such a structure in the clustering format may not help much in such an IC model. This is in line with the observation that metrics that are designed to detect clustering capture mostly redundant influence paths within strong communities, which matter less to influence spread than bridges between communities. Greedy method (CELF++) Our findings suggest that CELF++ is significantly under-performing. Even after guaranteeing and claiming to be 700 times faster than the naive greedy, CELF++ performs much worse than all the other algorithms. There appears to be a myriad of causes. Monte Carlo simulations are not enough The approximation guarantee in CELF++ assumes that we can evaluate the influence function exactly, which is not the case in practice. Our marginal gain estimation uses only 50 Monte Carlo simulations which is much less than the 10,000+ used in standard practice 19 . This generates a huge variance which may cause the lazy evaluation to wrongly rank the nodes which selects non-optimal seeds. This can explain most effectively the observed violation of the theoretical bound. The use of the Python 3.8 programming language imposes a significant computational overhead because the CELF++ algorithm is required to use iterative loops. A compiled implementation (C++, say) would likely reduce run time by one to two orders of magnitude and also allow for larger Monte Carlo budgets in a practical time to obtain solutions. When only 50 simulations are performed at each evaluation stage, these marginal gains can become very variable. The lazy constraints of CELF++ can inaccurately rank nodes and select candidates with local inferiority. The power-law degree distribution with high clustering found in the Facebook network can worsen the weakness of greedy algorithms. Choosing high degree seeds at an early stage can result in the depletion of influence potential at local nodes, which in turn means that the marginal contribution of later choice becomes trivial. Importance-based graph sampling refers to our sampling strategy that selects top nodes by their degree and PageRank score. Thus, the sub-graph in our sampling may become denser around the high-centrality nodes. This has the potential to create a fake favour on heuristic methods while interfering with the long-path structures which greedy algorithms exploit. The relative performance may differ with the use of alternative sampling strategies, such as random walk or forest fire sampling. The algorithm doesn’t seem to be consistently biased; rather, it appears to be unstable. The performance of CELF++ in our experimental setup (50 MC simulations, Python implementation, importance-based sampling) shall not be misinterpreted to indicate that the CELF++ algorithm is indeed fundamentally faulty. With a large enough Monte Carlo budget, optimised implementation and unbiased graph sampling, CELF++ is expected to perform with its theoretical guarantee. Our results demonstrate that greedy optimisation is sensitive to implementation parameters and experimental design choices. Discussion Theoretical vs. empirical performance Our findings highlight a significant gap between theory and practice in influence maximization. The CELF++ algorithm holds a approximation guarantee inherited from the greedy algorithm 12 , 15 , yet achieved only 12.9% of IMM’s spread in our experiments. However, this discrepancy does not necessarily invalidate the theoretical bound. The guarantee assumes exact evaluation of the influence function, whereas our implementation uses only 50 Monte Carlo simulations per marginal gain estimation far below the 10,000+ typically required for reliable lazy evaluation. This insufficient simulation budget introduces substantial variance that can cause incorrect node rankings and suboptimal seed selection, effectively violating the preconditions under which the theoretical guarantee holds. More broadly, the guarantee is insensitive to (1) errors arising from Monte Carlo influence evaluation, (2) tie-breaking decisions, or (3) the way lazy evaluation heuristics interact with the network structure. When these practical factors are present as they inevitably are in real deployments the gap between theoretical bounds and observed performance can be substantial. Our findings suggest that practitioners should verify that implementation parameters satisfy the assumptions underlying theoretical guarantees before relying on them for algorithm selection. On the other hand, sampling-based methods (RIS, IMM) have theory to support them and are also effective in practice. The approximation 26 , 27 translates into consistent high-quality solutions, validating the shift in paradigm from greedy to sampling-based methods. Crucially, sampling-based methods embed their Monte Carlo estimation directly into the algorithmic framework (via reverse-reachable sets), making them inherently more robust to estimation variance than greedy methods that rely on external influence evaluations. The surprising effectiveness of simple heuristics The competitiveness of PageRank questions the need for elaborate algorithms for influence maximization. Obtaining 96.3% of the spread of IMM for only is a strong indication that the complexity of algorithms does not necessarily justified its cost. PageRank is effective because it looks globally at nodes. In contrast to Degree centrality, which merely studies direct connectivity, PageRank considers the indirect paths of influencers through a random walk. When the connectivity forms clustering in social networks, it captures more important global structure than marginal gains through netting. This finding is relevant to practitioners; in real-time marketing, emergency response, and breaking news diffusion, PageRank provides instantaneous near-optimal seed selection. The performance loss of 3.7% to IMM may not be significant in context of sub-second execution. Scalability considerations The near-linear growth of sampling-based methods confirms their practicality for large networks. Based on our findings, we estimate that RIS could take about 795 seconds (or 13 min) to process a 10,000 nodes network while IMM could do so in about 3970 s (or 66 min). Modern algorithms can be made tractable even for networks containing millions of nodes (such as social media networks) with enough power. Nonetheless, as the network size continues to increase, the performance gap between RIS and IMM results becomes super-linear. The adaptive sampling method of IMM is worst-case optimal but has greater overhead than necessary. There is a point where the fixed-sampling strategy of RIS starts to make sense with a lower theoretical bound. The runtime scaling of CELF++ was found to be prohibitive. A linear extrapolation would give 840 s for 1000 nodes and over 8,400 s (2.3 h) for 10,000 nodes. CELF++ has no advantages over sampling-based methods due to its poor solution quality. Implications for algorithm selection Based on our comprehensive evaluation, we provide the following evidence-based recommendations: Quality-critical applications: use IMM for marketing campaigns with substantial budgets, public health interventions, with high stakes notwithstanding high computational cost. The algorithm boasts a mean spread of 954.90 at 1000 nodes and exceptional stability (CV < 0.1%) that warrant its use for applications where influence maximization directly impacts utility. Balanced quality-efficiency scenarios: use RIS. Achieving 99.6% of IMM’s quality at one-fifth the runtime makes RIS the practical choice for most real-world applications. Time-critical or large-scale applications: use PageRank or Betweenness centrality. PageRank’s minimal computational cost (under 0.5 seconds for 1000 nodes) and 96.3% spread quality relative to IMM make it the ideal choice when speed is paramount. Betweenness centrality achieves statistically equivalent spread ( ) in 8.8 seconds, and may be preferred when bridge-node identification provides independent analytical value. Moderate-quality rapid deployment: use degree, GCCDC, or dangling centrality. These heuristics execute in under 3 seconds and achieve 80–85% of IMM’s spread at 1000 nodes, suitable for exploratory analysis or scenarios where approximate solutions are acceptable. Exercise caution with greedy optimization: our results show that CELF++ substantially underperformed under our experimental configuration (50 Monte Carlo simulations, Python implementation, importance-based graph sampling). However, this should not be interpreted as evidence that greedy methods are fundamentally flawed. Rather, practitioners deploying CELF++ or similar greedy algorithms should ensure (1) a sufficient Monte Carlo simulation budget (10,000+ per evaluation step), (2) an optimised compiled implementation to enable higher simulation budgets within practical time constraints, and (3) unbiased graph sampling strategies. Without validated configurations meeting these requirements, greedy methods may not realise their theoretical potential and sampling-based alternatives (RIS, IMM) are recommended instead. Limitations and future directions The limitations must be noted. First, our experiment was performed on a single real-world social network (Facebook) but at various scales. The algorithmic performance of different types of networks is likely to vary due to the nature of their structural properties. The algorithmic performances of different network topologies will differ, for example, directed networks such as Twitter, weighted networks with heterogeneous edge strengths, or dynamic networks, where the edges change over time. For example, directed networks may favor PageRank more because it is inherently built to model directional flow of influence, while weighted networks may affect the relative effectiveness of degree-based heuristics. In the future, the comparative framework we provided should be complemented, with the use of additional network types, like directed graphs (Twitter, citation networks), weighted networks (email communication, collaboration networks), and temporal networks. Varying the propagation probability of edges or using edge specific probabilities based on the properties of the network (like using inverse degree weighting) will also help evaluate robustness of the algorithms better. Second, we implemented the Independent Cascade model having uniform propagation probability (p = 0.1). Influence in the real world varies across edges, depending on co-relationship strength, content type and time. By extending this comparison to weighted cascade models or other diffusion models (Linear Threshold, triggering models), it could be more easily applied. The performance ranking from Linear Threshold (LT) model 12 essentially dictates that we might arrive at different kinds of performance ranking when dealing with the use of some algorithm. In this case, we are talking about algorithms that essentially identifies nodes with some kind of different neighbourhood coverage. In other words, algorithms which identifies the nodes where the most propagated nodes are present rather than those which are highly central. Weighted cascade variants where propagation probabilities are proportionate to inverse degree better capture real-world heterogeneous influence. This may also change the effectiveness of heuristics. In the future comparison of multiple diffusion models, we will see if this performance hierarchy is model dependent or a fundamental characteristic of the algorithms. In particular, the superiority of PageRank, and inferiority of CELF++. Also, the seed budget refers to one operating point. When the seed set is too small –3 or too big , performance characteristics can differ; in particular, heuristics are sometimes more efficient than optimised algorithms and vice versa. In addition, although our experiments using networks ranging from 200 to 1,000 nodes reached similar scalability results, real-world social network platforms operate at scales from millions to billions of nodes. RIS has an extrapolation to run 10,000-node networks in 13 minutes and run PageRank in 5 seconds according to our runtime extrapolations, but these analyses must be validated experimentally at larger scales. When dealing with such scales, constraints of memory, cache efficiency and opportunities of parallelization can change. Future work should apply these algorithms to large-scale benchmark datasets like LiveJournal (5M nodes), Orkut (3M nodes) and Twitter (41.6M nodes) from the SNAP collection 45 to check whether the performance hierarchy holds for web-scale networks. Moreover, recent advances in deep reinforcement learning (DRL) and graph neural networks (GNNs) have introduced promising alternatives for influence maximization 46 – 48 , 50 . These methods learn seed selection policies directly from network structure, potentially capturing complex patterns that hand-crafted algorithms may miss. PIANO 46 , for example, adapts seed selection for specific network characteristics without manual heuristic design using reinforcement learning. Though these methods show competitive performance, they necessitate a long training time and heavy computational power (GPU infrastructure), and cannot provide the theoretical guarantees of sampling-based methods yet. A direct performance comparison between our evaluated algorithms and DRL/GNN-based approaches would be interesting to assess the training overhead versus performance at inference time. Nevertheless, such a comparison should take into consideration the fairness in evaluation. The reason being, the learning based methods amortize the computational cost across different problem instance. Traditional algorithms on the other hand solve each instance independently. This is a key avenue for future research. One methodological limitation that warrants a discussion concerns the reported CELF++ results. The approximation guarantee provided by the greedy algorithm assumes an exact evaluation of the influence function, but when we implement this in practice, we obtain the marginal gain by estimating it using 50 Monte Carlo simulations. The CELF++ algorithm is commonly executed at least 10,000 times before every evaluation step to guarantee that the highest marginal gain nodes are selected correctly by the lazy evaluation mechanism. The underperformance of CELF++ is most likely a result of the lack of simulation budget, not a failure of algorithm. The implementation of all algorithms was done in Python 3.8, which imposes significant computational overhead due to the iterative loops required by CELF++. A compiled implementation (e.g., C++) would more likely give CELF++ a run-time advantage of one to two orders of magnitude, which would make run-time results language rather than algorithm dependent. Our importance-based graph sampling strategy selects nodes according to their degree and PageRank score ranking. This means there may be selection bias caused by our strategy. This bias may favor centrality-based heuristics since our sampling strategy may densify the subgraph around high-degree nodes. Our findings are robust to the manner in which the graph is extracted. Future work should evaluate alternative sampling strategies such as random walk or forest fire sampling. Future work to investigate CELF++ should involve orders of magnitude higher Monte Carlo budgets (e.g., 10,000), optimized compiled implementations, and unbiased graph sampling, to assess whether the performance mismatch persists under typical conditions. In particular, publicly available C++ implementations such as the CELF framework by Gupta et al. ( https://github.com/NikhilGupta1997/Influence-Maximization-CELF ) could serve as a starting point for cross-language performance comparison, which remains an important direction for future work. Finally, we acknowledge that English is not the first language of all authors, and despite careful proofreading, some linguistic imperfections may remain. We welcome suggestions for improving the clarity and readability of the manuscript. Future work should study the underperformance of CELF++ in detail using algorithm traces. Moreover, there may be hybrid approaches that use PageRank seed initialization and sampling for refined targeted sampling. Similarly, dynamic influence maximization with the evolving structure of the network is of interest. Finally, fairness in influence maximization to achieve similar coverage in various groups is yet another direction for future work 53 , 54 . Broader implications The consequences of our findings go further. A good example of this gap is the performance guarantees given by CELF for static allocations and custom author-data constraints. In complexity analysis of algorithms, one gets asymptotic guarantees, but an algorithm’s actual performance depends on the constant of proportionality and other details. These details are important because they are interacting with actual distributions of data. The finding that simple heuristics like PageRank often work better than complex optimization algorithms like CELF++ and sometimes even sampling methods is echoed in many fields. According to 40 simple heuristics outperform sophisticated models. When algorithms are prescribed, empirical evaluation as well as theoretical analysis should be taken into account. Ultimately, the increasing domination of sampling techniques also affirms a more recent algorithmic trend in combinatorial optimization: Reformulating an optimization problem as a sampling or coverage problem often yields both theoretical guarantees and practical efficiency improvements. This model has been successfully utilized in numerous fields such as influence maximization, submodular optimization and probabilistic inference and can be effectively used in future research. Centrality-based heuristic analysis In addition to Degree centrality, the inclusion of Betweenness, Dangling, and GCCDC centrality will also be studied to gain more insight into the effect of different node importance metrics on their ability to propagate influence. Betweenness centrality: the centrality-based heuristic emerged as the strongest among the ones we proposed in SATIC. It achieved 96.5% of the performance of IMM in case of 1000 nodes (921.80 vs. 954.90). It only takes 8.8 s, which is much lower than IMM’s running time of 323.5 s. The proximity of PageRank value (921.78) indicates there is considerable overlap between bridge nodes as per betweenness centrality and structurally important nodes as per PageRank in social networks with high clustering coefficient. The stability of betweenness-based seed selection is confirmed by the low coefficient of variation. Dangling centrality: their performance was average and ranked between 5th to 7th in terms of graph sizes, when it has a spread between 75.8% to 83.5% of IMM. The greater variability (CV of 6.24% with 200 nodes) implies sensitivity to short-term network structure. The focus of this metric on edge-removal impact captures the local disruption potential rather than the global influence pathways. GCCDC: across all scales of graphs, achieved a spread of IMM between 82.0%–93.1 %. The global clustering coefficient (GCC) was combined with local clustering to give slightly better performance than pure degree centrality at larger scales (811.59 vs. 810.87 at 1000 nodes). So, it can be said that clustering-aware metrics offer little additional gains in influence maximization under the IC model with uniform propagation probability. The findings show that betweenness centrality and PageRank offer the most serious competition among centrality-based approaches to sampling-based methods, with the former providing slightly better spread at a medium computational cost, and the latter offering very similar performance at an undervalued running time (0.4 s). Conclusion An empirical study comparing eight influence maximization algorithms at multiple scales is presented in this paper. We run each configuration 10 times independently on the Facebook subgraphs (with 200–1000 nodes) and show statistically significant differences in the performance. We also show that practical assessments often ignored in theoretical analyses matter a lot.Recent studies show that sampling-based methods (RIS, IMM) yield near-optimum performance which is stable (CV <0.25%). In our configuration, CELF++ did not succeed at all with only 12.9% of IMM’s spread at 1000 nodes. This poor performance is likely due to running too few Monte Carlo simulations (50 vs. 10,000+ recommended), Python overhead, and that lazy evaluation is sensitive to importance-based sampling. We have no reason to believe that CELF++ fails basically. This begs the question of using the greedy optimization without tuning many parameters. The PageRank heuristic achieves 96.3% accuracy with respect to IMM, while being 794 faster than IMM at runtime. Hence, PageRank is suitable for applications with a time-critical requirement. The Betweenness centrality compared to PageRank had a great effectiveness of 96.5% of IMM. The performance is at a moderate cost. The Dangling centrality and GCCDC had a comparable performance to the Degree centrality. The gap between theoretical guarantees and empirical performance of CELF++ stemmed from the implementation parameters used, the budget for simulation and the sampling employed for the simulation. The success of PageRank shows that simple heuristics that leverage the global structure of the network can yield competitive results if the global structure of the network provides strong signals about node importance. For practitioners, the IMM method is advised for applications where quality is critical, the RIS method where a quality-efficiency balance is desired, and the PageRank or Betweenness Centrality methods for tasks where efficiency is predominant. To realize their theoretical potential, greedy methods require careful tuning of parameters and numerous Monte Carlo simulations. Future research could analyse the algorithmic traces of CELF++, use higher Monte Carlo budgets, and implemented compilations. One promising direction involves hybrid approaches that exploit PageRank initialization followed by sampling-based refinement and extension to dynamic networks. Acknowledgements This work was fully funded by the Office of Research and Sponsored Programs at Abu Dhabi University in Abu Dhabi, UAE. Author contributions L.A. and A.A.T. conceptualized the research framework and designed the experimental methodology. A.A.T. developed and implemented all five algorithms (CELF++, RIS, IMM, Degree centrality, and PageRank), constructed the importance-based sampling framework, and conducted all computational experiments across multiple network scales. A.S. contributed to the software implementation, algorithm validation, and verification of experimental results. A.A.T. performed the comprehensive statistical analysis, including paired t-tests and significance testing, and created all visualizations and figures. A.A.T. wrote the original manuscript draft, including the theoretical formulation, results interpretation, and discussion sections. L.A., A.S., and R.A.Q. provided critical intellectual input, reviewed the manuscript for scientific rigor, and contributed to revisions and refinements of the final text. L.A. and R.A.Q. supervised the overall project execution and provided administrative support. All authors have read, reviewed, and approved the final version of the manuscript for submission. Data availability The datasets generated and analyzed during the current study are available from the corresponding author on reasonable request. The source Facebook social network dataset is publicly available in the SNAP datasets collection (Leskovec, J. & Krevl, A. SNAP Datasets: Stanford Large Network Dataset Collection, 2014) at http://snap.stanford.edu/data/ego-Facebook.html . All experimental code, algorithm implementations (CELF++, RIS, IMM, Degree centrality, PageRank), statistical analysis scripts, and visualization code used in this study are publicly available in a GitHub repository at https://github.com/arartawil/Influence-Maximization-Algorithms-Comprehensive-Benchmark . The repository includes all code necessary to reproduce the experiments, statistical analyses, and figures presented in the manuscript, along with detailed documentation and setup instructions. Declarations Competing interests The authors declare no competing interests. Footnotes Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. References 1. De Vere Hunt, I. & Linos, E. Social media for public health: Framework for social media-based public health campaigns. J. Med. Internet Res. 24 , e42179. 10.2196/42179 (2022). [ DOI ] [ PMC free article ] [ PubMed ] [ Google Scholar ] 2. Kostygina, G. et al. Boosting health campaign reach and engagement through use of social media influencers and memes. Soc. Med. Soc. 6 , 205630512091247. 10.1177/2056305120912475 (2020). 3. Pillai, R. M. & Fazio, L. K. The effects of repeating false and misleading information on belief. WIREs Cognit. Sci. 12 . 10.1002/wcs.1573 (2021). [ DOI ] [ PubMed ] 4. Huang, S., Lin, W., Bao, Z. & Sun, J. Influence maximization in real-world closed social networks. Proc. VLDB Endowm. 16 , 180–192. 10.14778/3565816.3565821 (2022). [ Google Scholar ] 5. Wu, G., Chen, G., Gao, X. & Yan, G. Parallel greedy algorithm to multiple influence maximization in social network. ACM Trans. Knowl. Discov. Data 15 , 1–21. 10.1145/3442341 (2021). [ Google Scholar ] 6. He, Q. et al. Adaptive rumor suppression on social networks: A multi-round hybrid approach. ACM Trans. Knowl. Discov. Data 19 , 1–24. 10.1145/3701738 (2025). [ Google Scholar ] 7. Qin, X., Zhong, C. & Yang, Q. An influence maximization algorithm based on community-topic features for dynamic social networks. IEEE Trans. Netw. Sci. Eng. 9 , 608–621. 10.1109/TNSE.2021.3127921 (2022). [ Google Scholar ] 8. Wang, L. et al. Influence spread in geo-social networks: A multiobjective optimization perspective. IEEE Trans. Cybern. 51 , 2663–2675. 10.1109/TCYB.2019.2906078 (2021). [ DOI ] [ PubMed ] [ Google Scholar ] 9. C., A. & T., R. Real time anomaly detection in network traffic: A comparative analysis of machine learning algorithms. Int. Res. J. Adv. Eng. Hub 2 , 1968–1977. 10.47392/irjaeh.2024.0269 (2024). 10. Hameed, F. & Alkhzaimi, H. Hybrid genetic algorithm and deep learning techniques for advanced side-channel attacks. Sci. Rep. 15 . 10.1038/s41598-025-06375-1 (2025). [ DOI ] [ PMC free article ] [ PubMed ] 11. Garg, D. M., Dhull, D. H., Kalluri, D. N. & Agrawal, S. Understanding sample size determination in research: A practical guide. Kuey . 10.53555/kuey.v30i5.6040 (2024). 12. Kempe, D., Kleinberg, J. & Tardos, É. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD ’03. 137–146. 10.1145/956750.956769 (2003). 13. Domingos, P. & Richardson, M. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD ’01. 57–66. 10.1145/502512.502525 (2001). 14. Richardson, M. & Domingos, P. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD ’02. 61–70. 10.1145/775047.775057 (2002). 15. Nemhauser, G. L., Wolsey, L. A. & Fisher, M. L. An analysis of approximations for maximizing submodular set functions. Math. Program. 14 , 265–294. 10.1007/BF01588971 (1978). [ Google Scholar ] 16. Mossel, E. & Roch, S. On the submodularity of influence in social networks. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing , STOC ’07. 128–134. 10.1145/1250790.1250811 (2007). 17. Kempe, D., Kleinberg, J. & Tardos, É. Maximizing the spread of influence through a social network. Theory Comput. 11 , 105–147. 10.4086/toc.2015.v011a004 (2015). [ Google Scholar ] 18. Leskovec, J. et al. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD ’07. 420–429. 10.1145/1281192.1281239 (2007) (best student paper award). 19. Goyal, A., Lu, W. & Lakshmanan, L. V. Celf++: Optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th International Conference Companion on World Wide Web , WWW ’11. 47–48. 10.1145/1963192.1963217 (2011). 20. Chen, W., Wang, Y. & Yang, S. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD ’09. 199–208. 10.1145/1557019.1557047 (2009). 21. Chen, W., Wang, C. & Wang, Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD ’10. 1029–1038. 10.1145/1835804.1835934 (2010). 22. Chen, W., Wang, C. & Wang, Y. Scalable influence maximization for independent cascade model in large-scale social networks. Data Min. Knowl. Discov. 25 , 545–576. 10.1007/s10618-012-0262-1 (2012). [ Google Scholar ] 23. Goyal, A., Lu, W. & Lakshmanan, L. V. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In Proceedings of the 11th IEEE International Conference on Data Mining , ICDM ’11. 211–220. 10.1109/ICDM.2011.132 (2011). 24. Chen, W., Yuan, Y. & Zhang, L. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the 10th IEEE International Conference on Data Mining , ICDM ’10. 88–97. 10.1109/ICDM.2010.118 (2010). 25. Borgs, C., Brautbar, M., Chayes, J. & Lucier, B. Maximizing social influence in nearly optimal time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’14. 946–957. arXiv:1212.0884 (2014). 26. Tang, Y., Xiao, X. & Shi, Y. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data , SIGMOD ’14. 75–86. 10.1145/2588555.2593670 (2014). 27. Tang, Y., Shi, Y. & Xiao, X. Influence maximization in near-linear time: A martingale approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data , SIGMOD ’15. 1539–1554. 10.1145/2723372.2723734 (2015). 28. Nguyen, H. T., Thai, M. T. & Dinh, T. N. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data , SIGMOD ’16. 695–710. 10.1145/2882903.2915207 (2016). 29. Huang, K., Wang, S., Bevilacqua, G., Xiao, X. & Lakshmanan, L. V. Revisiting the stop-and-stare algorithms for influence maximization. Proc. VLDB Endowm. 10 , 913–924 (2017). [ Google Scholar ] 30. Tang, J., Tang, X., Xiao, X. & Yuan, J. Online processing algorithms for influence maximization. In Proceedings of the 2018 ACM SIGMOD International Conference on Management of Data , SIGMOD ’18. 991–1005. 10.1145/3183713.3183749 (2018). 31. Guo, Q., Wang, S., Wei, Z. & Chen, M. Influence maximization revisited: Efficient reverse reachable set generation with bound tightened. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data , SIGMOD ’20. 2167–2181. 10.1145/3318464.3389740 (2020). 32. Wang, X., Zhang, X., Zhao, C. & Yi, D. Maximizing the spread of influence via generalized degree discount. PLOS ONE 10.1371/journal.pone.0164393 (2016). [ DOI ] [ PMC free article ] [ PubMed ] [ Google Scholar ] 33. Zhang, B., Wang, Y., Jin, Q. & Ma, J. A pagerank-inspired heuristic scheme for influence maximization in social networks. Int. J. Web Serv. Res. 12 , 48–62. 10.4018/IJWSR.2015100104 (2015). [ Google Scholar ] 34. Li, D. et al. Signed-pagerank: An efficient influence maximization framework for signed social networks. IEEE Trans. Knowl. Data Eng. 10.1109/TKDE.2019.2947421 (2019). [ Google Scholar ] 35. Zhang, J.-X., Chen, D.-B., Dong, Q. & Zhao, Z.-D. Identifying a set of influential spreaders in complex networks. Sci. Rep. 6 . 10.1038/srep27823 (2016). [ DOI ] [ PMC free article ] [ PubMed ] 36. Chen, Y.-C., Zhu, W.-Y., Peng, W.-C., Lee, W.-C. & Lee, S.-Y. Cim: Community-based influence maximization in social networks. ACM Trans. Intell. Syst. Technol. 5 . 10.1145/2532549 (2014). 37. Wang, Y., Cong, G., Song, G. & Xie, K. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD ’10. 1039–1048. 10.1145/1835804.1835935 (2010). 38. Shang, J., Zhou, S., Li, X., Liu, L. & Wu, H. Cofim: A community-based framework for influence maximization on large-scale networks. Knowl.-Based Syst. 117 , 88–100. 10.1016/j.knosys.2016.09.029 (2017). [ Google Scholar ] 39. Abd El-Aziz, A. et al. Lkg: A fast scalable community-based approach for influence maximization problem in social networks. Phys. A Stat. Mech. Appl. 10.1016/j.physa.2021.126243 (2021). [ Google Scholar ] 40. Arora, A., Galhotra, S. & Ranu, S. Debunking the myths of influence maximization: An in-depth benchmarking study. In Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data , SIGMOD ’17. 10.1145/3035918.3035924 (2017). 41. Lu, W., Xiao, X., Goyal, A., Huang, K. & Lakshmanan, L. V. Refutations on “debunking the myths of influence maximization”. arXiv:1705.05144 (2017). 42. Galbrun, E., Gionis, A. & Tatti, N. Large-scale influence maximization with the influence maximization benchmarker suite. In Proceedings of the Joint Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) , GRADES-NDA ’21. 10.1145/3461837.3464510 (2021). 43. Jung, K., Heo, W. & Chen, W. Irie: Scalable and robust influence maximization in social networks. In Proceedings of the 12th IEEE International Conference on Data Mining , ICDM ’12. 10.1109/ICDM.2012.71 (2012). 44. Ohsaka, N., Akiba, T., Yoshida, Y. & Kawarabayashi, K.-I. Fast and accurate influence maximization on large networks with pruned Monte-Carlo simulations. In Proceedings of the 28th AAAI Conference on Artificial Intelligence , AAAI ’14 (2014). 45. Leskovec, J. & Krevl, A. Stanford Large Network Dataset Collection, Snap Datasets (2014). 46. Li, H. et al. Piano: Influence maximization meets deep reinforcement learning. IEEE Trans. Comput. Soc. Syst. 10.1109/TCSS.2022.3172786 (2023).38084365 [ Google Scholar ] 47. Ling, C. et al. Deep graph representation learning and optimization for influence maximization. In Proceedings of the 40th International Conference on Machine Learning , ICML ’23. 21350–21361 (2023). 48. Chen, T., Yan, S., Guo, J. & Wu, W. Touplegdd: A fine-designed solution of influence maximization by deep reinforcement learning. IEEE Trans. Comput. Soc. Syst. 10.1109/TCSS.2023.3269195 (2023).38084365 [ Google Scholar ] 49. Yang, S. et al. Balanced influence maximization in social networks based on deep reinforcement learning. Neural Netw. 169 , 334–351. 10.1016/j.neunet.2023.10.030 (2024). [ DOI ] [ PubMed ] [ Google Scholar ] 50. Panagopoulos, G., Tziortziotis, N., Malliaros, F. D. & Vazirgiannis, M. Maximizing influence with graph neural networks. arXiv:2108.04623 (2023). 51. Kumar, S., Mallik, A. & Panda, B. Influence maximization in social networks using transfer learning via graph-based lstm. Expert Syst. Appl. 212 . 10.1016/j.eswa.2022.118770 (2023). 52. Influence maximization via graph neural bandits. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , KDD ’24. 10.1145/3637528.3671983 (2024). 53. Lin, M. et al. Fair influence maximization in large-scale social networks based on attribute-aware reverse influence sampling. J. Artif. Intell. Res. 76 , 925–957. 10.1613/jair.1.13992 (2023). [ Google Scholar ] 54. Others. Influence maximization with fairness at scale. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , KDD ’23. 10.1145/3580305.3599847 (2023). 55. Fatima, U., Hina, S. & Wasif, M. Dangling centrality highlights critical nodes by evaluating network stability through link removal. Sci. Rep. 15 . 10.1038/s41598-025-24930-8 (2025). [ DOI ] [ PMC free article ] [ PubMed ] 56. Brandes, U. A faster algorithm for betweenness centrality. J. Math. Sociol. 25 , 163–177 (2001). [ Google Scholar ] 57. Fatima, U. & Ahsan, T. A novel dangling centrality metric for real-life quantum graphs. In IEEE International Conference on Quantum Artificial Intelligence (QAI) . 466–472. 10.1109/QAI63978.2025.00078 (2025). 58. Fatima, U., Hina, S. & Wasif, M. A novel global clustering coefficient-dependent degree centrality (GCCDC) metric for large network analysis using real-world datasets. J. Comput. Sci. 70 , 102008. 10.1016/j.jocs.2023.102008 (2023). [ Google Scholar ] Associated Data This section collects any data citations, data availability statements, or supplementary materials included in this article. Data Availability Statement The datasets generated and analyzed during the current study are available from the corresponding author on reasonable request. The source Facebook social network dataset is publicly available in the SNAP datasets collection (Leskovec, J. & Krevl, A. SNAP Datasets: Stanford Large Network Dataset Collection, 2014) at http://snap.stanford.edu/data/ego-Facebook.html . All experimental code, algorithm implementations (CELF++, RIS, IMM, Degree centrality, PageRank), statistical analysis scripts, and visualization code used in this study are publicly available in a GitHub repository at https://github.com/arartawil/Influence-Maximization-Algorithms-Comprehensive-Benchmark . The repository includes all code necessary to reproduce the experiments, statistical analyses, and figures presented in the manuscript, along with detailed documentation and setup instructions. Articles from Scientific Reports are provided here courtesy of Nature Publishing Group ACTIONS View on publisher site PDF (3.0 MB) Cite Collections Permalink RESOURCES Similar articles Cited by other articles Links to NCBI Databases Follow NCBI NCBI on X (formerly known as Twitter) NCBI on Facebook NCBI on LinkedIn NCBI on GitHub NCBI RSS feed Connect with NLM NLM on X (formerly known as Twitter) NLM on Facebook NLM on YouTube National Library of Medicine 8600 Rockville Pike Bethesda, MD 20894 Web Policies FOIA HHS Vulnerability Disclosure Help Accessibility Careers NLM NIH HHS USA.gov Back to Top

Related documents

• Approximate Pareto Frontiers for Submodular Utility and Cost Tradeoffs#987592
• Influence Strength Estimation in Hyperbolic Space for Social Influence Maximization#141702
• Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization#2783
• Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound#200590
• Enhancing Insider Threat Detection in Imbalanced Cybersecurity Settings Using the Density-Based Local Outlier Factor Algorithm#671975