PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast and Scalable Influence Estimation in the Independent Cascade Model: a unified framework

Matic Požar, Miklós Krész

arXiv:2610.32502v1cs.SI

TL;DR

Exact Independent Cascade activation probabilities are #P-hard to compute, while repeated high-precision estimation is costly. This paper unifies analytical approximation methods and compares them across networks and diffusion settings; second-order dynamic message passing achieves the strongest reported overall accuracy, with added computational overhead.

  • Problem

    Exact IC evaluation is #P-hard, and the paper addresses the limited systematic comparison of analytical approximations for node-level activation probabilities.

    Source: §1 · p. 2

  • Method

    The paper unifies IC approximations by temporal representation, retained propagation information, and incoming-influence aggregation, and develops new methods.

    Source: §1 · p. 4, §8 · p. 42

  • Results

    Second-order DMP achieves the lowest pooled median RMSE in both benchmark suites and the lowest dataset- or graph-family-level median RMSE on every network considered.

    Source: §8 · p. 42

  • Takeaways & Limitations

    The unified view exposes relationships among approximation families and presents a finer spectrum of accuracy–runtime trade-offs.

    Source: §8 · p. 42

    DMP2 adds substantial computational overhead, which depends on directed triangle-closing states and can become large in highly clustered networks.

    Source: §7.4 · p. 42

Abstract

from arXiv · show

Computing diffusion processes on networks is fundamental to applications including influence maximization, epidemic modeling, information propagation, and diffusion inference. The Independent Cascade (IC) model is one of the most widely used models of progressive diffusion, yet exact computation of its activation probabilities is #P-hard, while Monte Carlo simulation becomes costly when accurate estimates are required repeatedly. Despite its central role, analytical approximation of the IC diffusion function has received comparatively little systematic attention relative to the extensive literature on influence-maximization algorithms. We present a comprehensive study of analytical approximations for the IC model. We review a wide range of existing approaches and unify them through a common framework based on temporal representation, retained propagation information, and aggregation rule. This perspective exposes connections between previously distinct approximation families and motivates several new methods. We further conduct, to our knowledge, the first large-scale cross-family comparison of analytical IC approximations for node-level marginal activation probabilities. Our benchmark spans real-world and synthetic networks with systematically varied topology, seed-set size, edge-probability model, and diffusion strength. The proposed second-order dynamic message-passing method achieves the lowest pooled median error and the lowest dataset- or graph-family-level median error on every network considered. The results reveal systematic differences between approximation families, identify regimes in which higher-order corrections are most beneficial, and establish analytical IC approximation as a rich accuracy-efficiency design space rather than a collection of isolated methods.

Abbreviations

Table 1 is an abbreviation list.

Abbreviations

1 Introduction

Exact IC probabilities are #P-hard to compute, and repeated high-precision Monte Carlo estimation is costly. The paper organizes and compares analytical approximations, then introduces new methods and reports second-order DMP as the lowest-error method on every tested dataset.

1 Introduction

  • Exact IC evaluation is #P-hard, while high-precision Monte Carlo can be costly for repeated node-level probability or marginal-gain evaluations.Scalar expected spread can conceal differences in individual nodes’ activation probabilities.Source: §1 · pp. 2–3
  • Learning-based estimators are excluded from the main comparison because their results depend on training data, architecture, and generalization, requiring a separate protocol.The authors leave evaluation of whether learned corrections justify those requirements for future work.Source: §1 · p. 3
  • Earlier studies often assessed approximations only within downstream tasks, and low edge probabilities can make method differences less visible.Source: §1 · pp. 3–4
  • Second-order DMP achieves the lowest estimation error on every tested dataset.Source: §1 · p. 4
  • The contributions include a taxonomy, a unified formulation connecting existing methods, and new approximations including higher-order cavity methods.Source: §1 · p. 4
  • The study provides the first comprehensive analytical IC approximation comparison, spanning method families and varied networks, seed sets, edge models, and diffusion strengths.Source: §1 · p. 4
  • The present paper substantially extends a preliminary conference version with additional methods, theoretical analysis, and broader experiments.Source: §1 · p. 4

2 Problem Formulation

The paper formalizes IC diffusion and the node-level probabilities it seeks to estimate, then places those quantities alongside Monte Carlo estimation and influence maximization. It motivates efficient analytical estimates by the computational difficulty of exact evaluation and the costs of repeated sampling.

2.1 Networks and the Independent Cascade Model

  • In the IC model, newly active nodes independently attempt to activate inactive out-neighbors, and a live-edge realization turns diffusion into reachability.Undirected edges are represented by two directed edges.Source: §2.1 · pp. 5–6
  • The Generalized Independent Cascade model allows stochastic initial activation, although the paper primarily presents methods for deterministic seed sets.Source: §2.1 · p. 6

2.2 Marginal Activation Probabilities and Influence Spread

  • A node’s marginal activation probability is its probability of activation by time t; cavity marginals instead evaluate activation after removing specified nodes.Source: §2.2 · pp. 6–7
  • Expected influence spread aggregates node-level activation probabilities into one scalar, losing the fine-grained probability information about individual nodes.Source: §2.2 · pp. 7–8

2.3 Monte Carlo Estimation and Computational Complexity

  • Exact IC marginal computation is #P-hard because exponentially many live-edge realizations can contribute to a node’s activation probability.Source: §2.3 · p. 8
  • Monte Carlo estimates marginals from sampled live-edge realizations; with 10^4 samples, an individual marginal’s worst-case standard error is at most 0.005.More precision requires a quadratic increase in sample count relative to the desired reduction in standard error.Source: §2.3 · pp. 8–9

2.4 Influence Maximization Context

  • Influence maximization selects a seed set under a budget; the IC influence function is monotone and submodular, while exact influence computation is #P-hard.Source: §2.4 · p. 9
  • Greedy influence maximization relies on repeated candidate evaluations, motivating efficient analytical estimates of node-level marginals at costs below high-precision Monte Carlo.Source: §2.4 · p. 10

3 A Unified View of Independent Cascade Approximation

This section organizes IC approximations by the temporal state they propagate, the history or context they retain, and how they aggregate incoming activation attempts, with route restrictions treated as a complementary strategy. This framework connects otherwise distinct methods and clarifies the limits of exact inference and simplified approximations.

3.1 Exact Marginal Formulation and Main Challenges

  • Exact marginals require correlated neighbor-state probabilities and cavity removal to prevent feedback, while cavity-state enumeration can have exponential complexity.Shared predecessors can create dependencies, and memoized cavity evaluation can require roughly O(poly(n)2^n) states.Source: §3.1 · pp. 11–12

3.2 Existing Solutions

  • Existing methods simplify NM by relaxing correlations and feedback; path-restricted variants can miss dynamics at larger edge probabilities, while DMP uses edge-cavity messages and is exact on trees.DMP retains independent neighbor activations in its model and is exact on trees or forests with independent edge variables and independent or deterministic seeds.Source: §3.2 · pp. 12–13

3.3 A Unified Mathematical View

  • A unified framework groups IC approximations by propagated temporal state, retained propagation context, and incoming-attempt aggregation, exposing relationships among previously distinct methods.These are the three modeling choices used to organize the approximation families.Source: §3.3 · p. 16

3.3.1 A common propagation operator.

  • The common propagation operator applies noisy-OR to incoming edge-level activation attempts; differences among several methods arise from the state supplied to that operator.The incidence-matrix representation permits nonlinear operations before destination-wise aggregation.Source: §3.3.1 · p. 17

3.3.2 Cumulative and step-wise propagation.

  • NM propagates cumulative activation probabilities, whereas SWE propagates newly active probabilities and corrects for nodes already activated.SPM and SP1M restrict activation to the shortest-path layer or that layer plus one, respectively; SP1M adds a previous-activation correction.Source: §3.3.2 · p. 18

3.3.3 Linearization and the common core of NM and SWE.

  • In the low-activation limit, ALE is the linearized form of either NM or SWE; beyond that limit, their differences arise from overlapping routes and, for SWE, activation depletion.ALE's weighted-walk expansion replaces probabilistic unions of overlapping activation routes with linear aggregation.Source: §3.3.3 · pp. 19–20

3.3.4 History and cavity context.

  • NM and SWE retain no explicit information about the route by which activation reaches a node, whereas DMP propagates edge-cavity messages.Source: §3.3.4 · p. 20
  • Higher-order cavity approximations retain additional local history beyond first-order DMP, creating a hierarchy for controlling feedback absent from ordinary node-level propagation.In the linear regime, cavity propagation corresponds to nonbacktracking rather than unrestricted weighted walks.Source: §3.3.4 · pp. 20–21

3.3.5 Structural restriction as an orthogonal strategy.

  • MIA, SPM, SP1M, and neighborhood methods restrict routes or explored regions, then can combine with choices about state, history, and aggregation.IRIE instead collapses cavity-like relations to damped node-level influence scores, approximating weighted walks for influence scores rather than node-level marginal probabilities.Source: §3.3.5 · p. 21

3.3.6 Taxonomy

  • The taxonomy identifies temporal state, retained history or context, and incoming aggregation as the three principal axes; path and topology restrictions modify propagation space.Table 2 summarizes this unified taxonomy.Source: §3.3.6 · p. 22, Table 2 · p. 22
  • NM, SWE, and DMP retain nonlinear noisy-OR aggregation but propagate cumulative node, step-wise node, and edge-cavity states, respectively; ALE linearizes that operator.MIA and SPM instead restrict propagation structure, providing a common basis for comparing error, complexity, and richer context.Source: §3.3.6 · pp. 22–23

4 New Approximation Methods

The section extends preliminary SWE-NO and modified ALE estimators with compensatory continuation, cavity variants, and higher-order dynamic message passing. Its methods vary how temporal layers, incoming overlap, and propagation history are represented.

4 New Approximation Methods

  • The work extends preliminary SWE-NO and modified ALE estimators with a general continuation framework, cavity-based variants, and higher-order dynamic message-passing corrections.The preliminary estimators are restated to provide a common basis for the extensions.Source: §4 · p. 23

4.1 Compensatory Continuation of Approximation Methods

  • Compensatory continuation composes approximation operators, using a conservative estimator’s output to initialize a more aggressive one rather than combining final estimates algebraically.Continuation steps are approximation steps, not additional IC time steps, and improvement is not guaranteed for arbitrary estimator pairs.Source: §4.1 · p. 23

4.2 SWE-NO

  • SWE-NO keeps SWE’s step-wise recurrence but changes temporal accumulation to noisy-OR, deliberately damping the accumulated estimate.Its accumulated quantity is not interpreted as the probability of activation by time t; the noisy-OR is a damping mechanism.Source: §4.2 · pp. 23–24

4.3 Independent Propagation-Layer Approximation

  • IPL retains ALE’s linear propagation within each depth but uses a noisy-OR survival product across depths, making standard ALE its first-order aggregation approximation.The cross-depth aggregation treats layer events as mutually independent.Source: §4.3 · p. 25

4.4 Second-Order Incoming-Aggregation Corrections

  • ALE2 adds pairwise overlap between incoming activation opportunities, while IPL2 combines that correction with IPL’s treatment of overlap across propagation depths.The second-order operator handles within-layer overlap; IPL handles overlap between contributions arriving at different depths.Source: §4.4 · pp. 26–27

4.5 Cavity Extensions of Existing Approximations

  • Cavity extensions apply edge-specific messages to suppress immediate feedback while preserving the underlying method’s characteristic update rule.The variants cover SWE, SWE-NO, ALE, IPL, steady-state DMP/SSS, and the SWE-HIB-C hybrid.Source: §4.5 · p. 27

4.6 Higher-Order Dynamic Message Passing

  • DMP of order h retains the latest h cavity vertices, forming a monotone hierarchy of finite-order upper bounds; second-order extra states correspond to directed triangle-closing configurations.The hierarchy’s monotonicity does not by itself imply convergence to the true marginals; second-order overhead depends on triangle-closing states and can be superlinear in the worst case.Source: §4.6 · pp. 27–29

5 Experiments

The benchmark compares representative analytical IC approximations selected to cover distinct modeling choices, rather than every published variant. It tests them on real and synthetic networks across varied diffusion conditions using held-out instances.

5.1 Selection of Benchmark Methods

  • The benchmark selects representative methods spanning temporal information, feedback, dependency, and admissible paths, including new methods and first- and second-order DMP.SSS-Noself and NBUB were excluded because their computational costs were prohibitive or less scalable; MIA was omitted from the principal aggregate comparison because it could not be evaluated consistently across the full grid.Source: §5.1 · pp. 30–31

5.2 Experimental Setup

  • Evaluation covers seven real-world networks and five synthetic network families, varying seed-set size, edge-probability model, and diffusion strength on held-out instances.The probability models include constant, weighted-cascade, and heterogeneous Dirichlet settings; regimes include weak, moderate, and strong diffusion.Source: §5.2 · p. 31

6 Results

Across real-world and synthetic benchmarks, second-order DMP has the lowest pooled median RMSE and leads on every dataset or graph family. The results also show that approximation accuracy depends on topology, diffusion conditions, and how methods represent propagation.

6.1 Overall Accuracy and Higher-Order DMP

  • DMP2’s benefit varies by topology: its median RMSE reduction is approximately 24.5% on Watts–Strogatz graphs and 9.5% on Holme–Kim graphs, with very small differences on three other families.The correction targets dependencies from short cyclic structures; the real-world clustering association is descriptive and based on only seven topologies.Source: §6.1 · pp. 32–33
  • Pooled across real-world seed fractions, DMP2’s median RMSE reduction over DMP rises from approximately 1.5×10^-5 at g⋆=0.10 to 0.00308 at g⋆=0.60, but at s=0.01 the largest gain is at g⋆=0.35.Larger seed fractions mechanically add more seed nodes with essentially zero error, so the observed seed-fraction trend is not solely evidence of easier non-seed diffusion.Source: §6.1 · p. 33, §6.4 · pp. 37–38

6.2 Step-Wise, Cavity, and Steady-State Approximations

  • SWE-NO leads non-cavity methods, cavity SWE-NO improves pooled RMSE in both suites, and SWE-HIB-C is also strong; basic SWE and NM lack general dominance, while cavity SWE can worsen synthetic pooled error.Cavity SWE’s synthetic pooled median RMSE is 0.01089 versus 0.00849 for SWE, despite cavity SWE winning on most paired instances.Source: §6.2 · pp. 33–35

6.1 Overall Accuracy and Higher-Order DMP

  • DMP2 has the lowest pooled median RMSE on both benchmarks: 0.00728 versus DMP’s 0.00915 on real-world networks and 0.00208 versus 0.00211 on synthetic networks.It also has the lowest dataset-level median RMSE on all seven real-world networks and graph-family-level median RMSE on all five synthetic families, though it does not win every individual instance.Source: §6.1 · p. 32, Figure 1 · p. 34

6.2 Step-Wise, Cavity, and Steady-State Approximations

  • Steady-state SSS is less accurate than finite-horizon NM in both suites, while steady-state DMP has a 0.06856 median RMSE on Watts–Strogatz graphs versus 0.01450 for finite-horizon DMP.The synthetic pooled median for steady-state DMP is 0.00231, which conceals its difficult-topology errors.Source: §6.2 · p. 35

6.3 Linear, Additive, and Path-Restricted Approximations

  • IPL is more accurate than ALE on both benchmarks, but second-order corrections are not uniform: ALE2 worsens pooled median RMSE while IPL2 lowers it to 0.07296 and retains a heavier upper tail.IPL2’s pooled median RMSE falls from 0.07978; ALE2’s rises from 0.10401 to 0.10798.Source: §6.3 · p. 36
  • Additive SWE is much cheaper but less accurate than nonlinear SWE, and SP1M improves on SPM while both remain less accurate than the strongest node-level and cavity methods.SP1M reduces pooled median RMSE from 0.19971 to 0.09580 on real-world networks and from 0.22446 to 0.14191 on synthetic networks.Source: §6.3 · p. 36

6.4 Dependence on Diffusion Regime

  • Edge-probability heterogeneity generally makes pooled results harder, but the ordering varies by method; for finite-horizon methods, error also tends to rise with diffusion strength and often fall as seed fraction increases.Seed-fraction trends need caution because seed nodes contribute essentially zero error, and ALE and IPL are not monotonic across all seed fractions.Source: §6.4 · pp. 37–38

7 Discussion

The discussion interprets approximation errors through feedback and dependencies, considers higher-order cavity corrections and practical parameter selection, and identifies limits on the benchmark and method. It highlights accuracy–complexity trade-offs and open questions about extending the approach beyond the IC setting.

7.1 Sources of Approximation Error

  • DMP2's larger gains on clustered graphs support short-cycle feedback correction, while residual error likely reflects dependent incoming branches that message passing still conditionally treats as independent.The second-order advantage is small on weakly clustered graph families but substantially larger on Watts–Strogatz and Holme–Kim networks.Source: §7.1 · p. 38

7.2 Higher-Order Cavity Corrections Beyond the IC Model

  • Higher-order cavity correction is a finite-memory cavity recursion; order-two IC retains only triangle-closing states, while outside progressive monotone settings, larger exclusions need not yield one-sided changes.The nonredundant second-order states arise when the additional excluded vertex is also an incoming neighbor.Source: §7.2 · p. 39

7.3 Differentiability and Practical Parameter Selection

  • Differentiable analytical approximations could support edge-probability estimation, inverse diffusion, or network-parameter learning, but the paper does not investigate those downstream tasks.The approximations can be represented as deterministic computational graphs and differentiated with automatic-differentiation techniques.Source: §7.3 · p. 40
  • Small changes in horizon parameters can appreciably affect accuracy and runtime; DMP variants appear less sensitive to small horizon perturbations than simpler approximations.The benchmark's setting-specific calibration represents favorable calibration, not deployment with an optimal horizon known in advance.Source: §7.3 · p. 40

7.4 Limitations and Future Work

  • The benchmark is finite, and its Monte Carlo reference probabilities contain sampling error, so very small differences between strong methods warrant care.The authors suggest exact-marginal graph families as a complement to Monte Carlo evaluation.Source: §7.4 · p. 41
  • Including deterministic seed nodes mechanically raises the zero-error share at larger seed fractions, so all-node RMSE gains may not reflect better prediction of subsequent diffusion.The authors suggest reporting complementary metrics restricted to non-seed nodes.Source: §7.4 · p. 41
  • Setting-specific Monte Carlo calibration may be unavailable at deployment, and accurate node marginals alone do not establish high-quality influence-maximization seed selection.The paper evaluates activation-probability estimation, not downstream optimization performance.Source: §7.4 · pp. 41–42
  • DMP2 adds substantial triangle-state overhead, especially in highly clustered networks, and reported runtime excludes state construction; the analysis is restricted to IC.The authors frame DMP2 as an accuracy-oriented point in the accuracy–runtime trade-off, not a uniformly preferable replacement for first-order DMP.Source: §7.4 · pp. 41–42

8 Conclusion

The paper unifies analytical IC approximations through temporal representation, retained information, and aggregation, then compares them across varied diffusion regimes. DMP2 leads the accuracy results, while the broader findings frame approximation as a trade-off space with no universally dominant mechanism.

8 Conclusion

  • The unified framework organizes approximations by temporal state, retained information, and aggregation rule, clarifying relationships among families and motivating new methods.The resulting methods expose a finer spectrum of accuracy–runtime trade-offs than considering existing approximations in isolation.Source: §8 · p. 42
  • The benchmark covers real-world and synthetic networks while varying topology, seed-set size, edge-probability model, and diffusion strength.It evaluates node-level marginal activation probabilities under a common protocol across diverse regimes.Source: §8 · p. 42
  • DMP2 achieved the lowest pooled median RMSE in both benchmark suites and the lowest dataset- or graph-family-level median RMSE on every network considered.Its advantage over first-order DMP was especially pronounced where short-loop effects matter, including highly clustered synthetic networks and selected low-seed, moderate-to-strong diffusion settings; it incurred substantial computational overhead but remained scalable on all networks considered.Source: §8 · p. 42
  • IPL substantially improves on ALE while retaining the same O(T|E|) asymptotic complexity on sparse networks.A second-order incoming-aggregation correction improves IPL on most real-world benchmark instances, but not uniformly.Source: §8 · p. 43
  • Approximation performance depends on structural and dynamical regime as well as computational complexity, and no single mechanism dominates every regime or trade-off point.The results position analytical IC approximation as a design space whose temporal representation, retained information, and aggregation rules can be varied for application requirements.Source: §8 · p. 43

Declarations

The declarations identify the data and code sources, describe AI assistance and author responsibilities, and report competing interests, funding, and contributions.

Availability of data and materials

  • The analyzed real-world datasets are publicly available through SNAP or the IMPC repository, and synthetic data and results can be reproduced using the public project code and configuration.Generated result files are not included because of their size.Source: Availability of data and materials · p. 43

Use of artificial intelligence

  • GPT-5.6 assisted with implementation, editing, manuscript organization, and methodological discussion; the authors specified and verified the research and take responsibility for the manuscript and results.Source: Use of artificial intelligence · p. 44

Competing interests

Funding

  • Miklós Krész received ARIS grant support and support from the CogniCom research program.Source: Funding · p. 44

Authors’ contributions

  • MP conceived the study, developed methods, ran and analyzed experiments, and drafted the manuscript; MK supervised, contributed to methodology, and reviewed and edited it.Source: Authors’ contributions · p. 44

Appendix A Proof of Theorem 1

This section examines higher-order DMP for the IC model, proving upper-bound and monotonicity properties for finite-history estimates and describing cavity variants and loop-correction connections. It also contrasts recurrent higher-order DMP with the IC construction and describes the real-world networks used in the benchmark.

Appendix A Proof of Theorem 1

  • Under independent seed and live-edge indicators, every finite-order DMP estimate upper-bounds exact activation, and retaining more history monotonically tightens the estimate.The proof also shows noisy-OR cavity updates overestimate activation because positively associated incoming-branch failures are replaced by independent branches with the same marginals.Source: Appendix A · pp. 44, 46, 47

Appendix B Cavity Extensions

  • Cavity SWE is a heuristic feedback correction, not an exact reformulation, because conditioning on target survival changes cascade distributions whereas deleting the target only blocks a feedback path.It substitutes edge-specific nonbacktracking messages for unavailable conditional neighbor information.Source: Appendix B · p. 48

Cavity SWE-NO.; Cavity ALE.; Cavity IPL.

  • Cavity SWE-NO adds temporal noisy-OR damping, cavity ALE excludes immediate reverse propagation while summing layers, and cavity IPL combines cavity layers with survival-product aggregation.The SWE-NO noisy-OR accumulation is an approximation, not an exact probability of a union of independent activation-time events.Source: Cavity SWE-NO · p. 49, Cavity ALE · pp. 49–50, Cavity IPL · p. 50

Cavity SSS.; SWE-HIB-C.

  • Cavity SSS is the steady-state limit of DMP, while SWE-HIB-C propagates newly accumulated mass and its T updates return estimates at maximum depth T +1.The depth includes one additional propagation layer from the final DMP-style node readout.Source: Cavity SSS · p. 50, SWE-HIB-C · p. 51

B.0.1 Relation to Higher-Order and Loop-Corrected Message Passing; Higher-order non-backtracking IC bounds.

  • Higher-order DMP extends IC DMP with bounded rolling cavity history and monotonic ordering; unlike Abbe et al.’s final-influence upper bounds, it estimates finite-horizon marginals and uses nonredundant order-two triangle-closure states.Higher-order message passing is an established general idea; the contribution is this IC-specific hierarchy and state construction.Source: §B.0.1 · p. 51, Higher-order non-backtracking IC bounds · pp. 51–52

High-order non-backtracking matrices.; Triangle-aware percolation message passing.; Triangle-nonbacktracking message passing.

Message passing with loop-containing neighborhoods.; Belief propagation on networks with loops.; Loop-corrected cavity distributions.; Higher-order dynamic cavity approximations.; Higher-order recurrent DMP with loops.

Higher-order recurrent DMP with loops.

  • For recurrent DMP, triangular-structure messages parallel the order-two correction, but IC uses truncated spatial cavity history for finite-horizon marginals and a monotonic hierarchy.The recurrent method models epidemics in which nodes may repeatedly change state and closes higher-order dynamic quantities; IC is progressive and has a direct live-edge interpretation.Source: Higher-order recurrent DMP with loops · p. 54

C.1 Real-World Networks

  • NetHEPT is an undirected co-authorship network, WikiVote a directed voting network, Enron an undirected email network, and Epinions a directed trust network.The networks represent author collaborations, administrator-election votes, email communications, and user-declared trust relationships, respectively.Source: §C.1 · p. 54
  • Slashdot encodes friend-or-foe ties, ca-CondMat author collaborations, and cit-HepTh directed citations between papers.The datasets are social, scientific collaboration, and citation networks, respectively.Source: §C.1 · p. 54

C.2 Synthetic Networks

The synthetic benchmark uses five standard network families, with 5,000 nodes and target mean degree 4, 10, or 20; undirected edges are represented as opposite directed arcs for the IC model.

C.2 Synthetic Networks

  • All five synthetic network families use n = 5000 nodes and target mean degree d ∈{4, 10, 20}, with undirected edges converted to oppositely directed arcs.The benchmark therefore varies density through d while keeping n fixed.Source: §C.2 · pp. 54–55
  • Erdős–Rényi graphs connect each node pair independently with the same probability.Source: §C.2 · p. 55
  • Barabási–Albert graphs use preferential attachment, with new nodes preferentially connecting to well-connected existing nodes.Source: §C.2 · p. 55
  • Holme–Kim graphs add triad formation to preferential attachment, producing heavy-tailed degree distributions with substantially higher clustering than standard BA.Source: §C.2 · p. 55
  • The stochastic block model uses four equal-sized communities and assigns 70% of expected degree within communities and 30% between them.Source: §C.2 · p. 55
  • Watts–Strogatz graphs start from a regular ring lattice with degree k = d and rewire edges with probability β = 0.1.Source: §C.2 · p. 55

C.3 Diffusion Configurations and Regime Calibration

The benchmark varies seed-set size and three base edge-probability models, while calibrating overall diffusion strength separately for each graph and configuration. Diffusion strength is measured among initially inactive nodes, with targets spanning weak, moderate, and strong regimes.

C.3 Diffusion Configurations and Regime Calibration

  • Seed sets cover 1%, 5%, 10%, and 20% of nodes, and the benchmark varies seed-set size, edge-probability model, and diffusion strength.The secondary activation rate measures diffusion relative to the initially inactive population, avoiding mechanically larger values from larger seed sets.Source: §C.3 · pp. 55, 57
  • The constant model gives every edge the same base probability, so diffusion differences arise from graph structure rather than transmission-probability heterogeneity.The common value is assigned before global calibration.Source: §C.3 · p. 56
  • Weighted cascade assigns smaller probabilities to edges entering high-in-degree nodes, with incoming probabilities summing to one before global rescaling.This normalizes incoming transmission strength across nodes with different in-degrees.Source: §C.3 · p. 56
  • The heterogeneous Dirichlet model samples relative incoming-edge weights with κ = 0.5, producing uneven transmission probabilities across a node’s incoming edges.Unlike weighted cascade’s uniform allocation across predecessors, it concentrates probability on a small number of edges while retaining the general normalization.Source: §C.3 · p. 56
  • Targets g⋆∈{0.10, 0.35, 0.60} represent weak, moderate, and strong diffusion, measured as the expected fraction of initially inactive nodes activated during the cascade.A global scale α is calibrated separately for each graph realization, edge-probability model, and seed fraction; infeasible targets are marked rather than replaced.Source: §C.3 · pp. 56–57

C.4 Hyperparameter Calibration and Held-Out Evaluation

Hyperparameters are selected on calibration instances and evaluated on held-out instances, with independent graph realizations used for synthetic tests. Evaluation combines error, agreement, ranking, and runtime measures because practical approximation quality depends on both predictive accuracy and computational cost.

C.4 Hyperparameter Calibration and Held-Out Evaluation

  • Each setting selects the configuration with minimum mean calibration RMSE across three instances, then freezes it for evaluation on five held-out instances.Selection is performed separately by network setting, edge model, seed fraction, and target activation rate; ties favor smaller T, then smaller L.Source: §C.4 · pp. 57–58
  • Synthetic held-out tests use new graph realizations, while real-world tests keep each dataset’s topology fixed and vary seed sets and, for Dirichlet, edge weights.Synthetic calibration and test sets each comprise three and five independent instances, respectively; real-world settings use the same split.Source: §C.4 · p. 57
  • Synthetic reference probabilities use 10,000 Monte Carlo realizations for calibration and 50,000 for held-out tests; real-world budgets vary by dataset and are larger for held-out evaluation.The larger held-out budgets reduce sampling noise in final accuracy measurements.Source: §C.4 · p. 58

C.5 Evaluation Metrics

  • RMSE emphasizes large node-level errors and selects hyperparameters, while MAE measures typical error magnitude with less sensitivity to a few large deviations.Pearson correlation complements absolute-error measures by capturing linear agreement even when estimates differ systematically in scale or offset.Source: §C.5 · p. 59
  • Spearman correlation measures preservation of node activation-marginal ordering, but it does not directly measure rankings of candidate marginal gains in greedy influence maximization.Its rank-based perspective is relevant to rank-sensitive downstream applications.Source: §C.5 · p. 59
  • AUC treats nodes at or above the 95th percentile of Monte Carlo activation probability as positive and is supplementary because seed nodes can influence this threshold-based metric.Estimated probabilities serve as classification scores separating highly activated nodes from the rest.Source: §C.5 · pp. 59–60
  • Runtime is reported alongside accuracy because approximation quality involves the trade-off between predictive accuracy and computational cost.The motivation for analytical approximations is reducing diffusion-estimation cost relative to high-budget Monte Carlo simulation.Source: §C.5 · p. 60

C.6 Implementation Details

All methods use a common graph representation and shared input conventions to support runtime comparisons. Timing measures application to a prepared graph, excluding setup and reusable second-order DMP preprocessing.

C.6 Implementation Details

  • All methods receive the same compact ICGraph, edge-probability array, and initial activation vector, and return node-probability estimates in a shared node ordering.Directed edges are stored in contiguous source-sorted arrays, with method-specific structural indices constructed and cached as needed.Source: §C.6 · p. 60
  • Related methods share array-based operations and edge-indexed cavity messages, so runtime differences primarily reflect each approximation’s additional state and computation.Required operations such as shortest-path searches and repeated fixed-point computations are retained.Source: §C.6 · p. 60
  • The implementation uses method-dependent internal precision despite identical edge-probability inputs, and the benchmark code is available at the repository.The experiments ran on a Dell Precision 7710 workstation with an Intel Core i7-6820HQ processor and 16 GB RAM.Source: §C.6 · pp. 60–61
  • Reported runtime covers only approximation execution on a prepared graph, excluding graph loading, calibration, hyperparameter selection, reference generation, and metric computation.Second-order DMP’s topology-dependent triangle-state indexing is cached before timing, so preprocessing costs that can be amortized are omitted.Source: §C.6 · p. 61

Related papers

Loading 2610.32502v1…