PaperlayerView exact revision on arXiv

Source-linked AI summary

Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process

Wei Chen, Wei Lu, Ning Zhang

arXiv:1204.3074v3cs.SIphysics.soc-ph

TL;DR

The paper asks how to maximize social-network influence before a deadline when diffusion is delayed. It extends IC and LT with meeting events, proves submodularity, and develops faster heuristics. These heuristics achieve greedy-level spread in experiments while running orders of magnitude faster, although exact local-DAG construction remains NP-hard and greedy is costly to scale.

  • Problem

    Influence maximization must account for propagation delays and deadlines when campaigns require influence spread within a limited time window.

  • Method

    The paper extends IC and LT to IC-M and LT-M with meeting events, proves monotonicity and submodularity, and designs MIA-M, MIA-C, and LDAG-M heuristics.

  • Results

    The heuristics produce seed sets with equally good quality as greedy while running two to three orders of magnitude faster.

  • Takeaways & Limitations

    Deadline- and delay-aware heuristics can preserve greedy-level influence spread while avoiding the scalability costs of greedy optimization.

  • Takeaways & Limitations

    Exact LDAG construction is NP-hard and therefore performed heuristically; greedy also becomes non-scalable when influence is estimated by costly simulations.

Abstract

from arXiv · show

Influence maximization is a problem of finding a small set of highly influential users, also known as seeds, in a social network such that the spread of influence under certain propagation models is maximized. In this paper, we consider time-critical influence maximization, in which one wants to maximize influence spread within a given deadline. Since timing is considered in the optimization, we also extend the Independent Cascade (IC) model and the Linear Threshold (LT) model to incorporate the time delay aspect of influence diffusion among individuals in social networks. We show that time-critical influence maximization under the time-delayed IC and LT models maintains desired properties such as submodularity, which allows a greedy approximation algorithm to achieve an approximation ratio of $1-1/e$. To overcome the inefficiency of the greedy algorithm, we design two heuristic algorithms: the first one is based on a dynamic programming procedure that computes exact influence in tree structures and directed acyclic subgraphs, while the second one converts the problem to one in the original models and then applies existing fast heuristic algorithms to it. Our simulation results demonstrate that our algorithms achieve the same level of influence spread as the greedy algorithm while running a few orders of magnitude faster, and they also outperform existing fast heuristics that disregard the deadline constraint and delays in diffusion.

1 Introduction

The paper formulates influence maximization under time-delayed diffusion and deadlines, extending classical models to time-critical campaigns. It proves useful optimization properties and introduces heuristics that retain influence quality while greatly reducing runtime.

  • Motivation: Time delays and campaign deadlines are missing from classical IC and LT formulations, despite observed temporal variation in social influence diffusion.Influence may propagate slowly because of heterogeneous human activity and network-related temporal effects; short campaigns therefore require deadline-aware optimization.
  • Contributions: The paper extends influence maximization with deadline constraints and proposes IC-M and LT-M models with random meeting events.These models represent delayed propagation between users while retaining the influence-maximization objective.
  • Contributions: Monotonicity and submodularity yield a greedy (1 −1/e)-approximation despite NP-hardness.The result preserves the standard approximation framework for the time-delayed models.
  • Contributions: MIA-M, MIA-C, and LDAG-M heuristics match greedy seed-set quality while running two to three orders of magnitude faster.The heuristics are designed specifically for time delays and deadline constraints.
  • Contributions: Existing heuristics that ignore time delays and deadlines can produce poor influence spread relative to the proposed context-specific heuristics.The comparison motivates incorporating temporal constraints directly into seed selection.

2 Time-Critical Influence Maximization for Time-Delayed Independent Cascade Model

The IC-M model adds probabilistic meeting events and a deadline to the Independent Cascade process. The resulting influence function remains monotone and submodular, while the optimization problem remains NP-hard.

  • Model and Problem Definition: IC-M assigns each edge a meeting probability, and a first meeting gives the active node one chance to activate its inactive neighbor.Successful activation occurs at the meeting step, after which the newly active node propagates in the next step.
  • Model and Problem Definition: Meeting probabilities matter under a deadline because they determine whether influence can propagate before the campaign ends.Without a deadline, any positive meeting probability eventually produces a meeting; within a deadline, timing changes the optimal seed set.
  • Model and Problem Definition: The objective maximizes the expected number of nodes activated by deadline τ using at most k seeds.The paper denotes this deadline-bounded influence function by στ(S).
  • Complexity: The time-critical IC-M influence-maximization problem is NP-hard.The original IC problem is recovered when all meeting probabilities equal one and τ = |V|.
  • Properties: For every deadline τ ≥1, the IC-M influence function is monotone and submodular.A possible-world construction fixes meeting outcomes and live-or-blocked edges, reducing each realization to a reachability function whose expectation preserves these properties.

3 Time-Critical Influence Maximization under Time-Delayed Linear Threshold Model

The LT-M model incorporates probabilistic meetings into threshold-based diffusion and preserves the key theoretical guarantees of influence maximization. The paper extends these guarantees to the Triggering Set model while addressing greedy computation costs.

  • LT-M Model: LT-M adds independent meeting probabilities to the Linear Threshold model, making an influence weight effective only after the corresponding active and inactive users first meet.A node activates when the total effective incoming weight reaches its random threshold.
  • Complexity: The time-critical LT-M influence-maximization problem is NP-hard.The original LT problem is a special case when all meeting probabilities equal one and τ = |V|.
  • Properties: For every deadline τ ≥1, the LT-M influence function is monotone and submodular.The proof uses equivalence between LT-M and a random live-edge process with meeting events.
  • Approximation Guarantees: The shared monotone-submodular structure gives a greedy (1−1/e)-approximation under the cardinality constraint.This guarantee applies to both IC-M and LT-M through standard submodular maximization results.
  • Generalization: The same approximation framework extends to the Triggering Set model with Meeting events.TS-M generalizes IC-M and LT-M, and its deadline-bounded influence function is also monotone and submodular.
  • Greedy Inefficiency: Monte Carlo estimation makes greedy non-scalable on large graphs, motivating faster heuristics.With simulation error, the greedy guarantee becomes 1 −1/e −ϵ, while the simulations remain computationally expensive.

4 Computing Influence in Arborescences in the IC-M model

This section computes deadline-bounded influence in IC-M arborescences by recursively deriving activation probabilities, with a faster closed-form treatment for chain substructures. The chain analysis uses sums of geometric waiting times and supports computation polynomial in log τ.

  • Recursive computation: The arborescence analysis assumes influence reaches the root only through the selected in-arborescence and that it contains at least one seed.Under these assumptions, the algorithm computes deadline-bounded influence spread in the structure.
  • Recursive computation: Dynamic programming recursively computes each node’s activation probability at every step through the deadline τ.The recursion traverses an in-arborescence from leaves to the root and aggregates activation probabilities over t = 0 through τ.
  • Fast chain computation: For a chain, activation time is modeled as the sum of geometric waiting times for successive meetings between adjacent nodes.Each waiting time has a meeting-probability parameter, while successful influence attempts contribute multiplicatively along the path.
  • Fast chain computation: Equal meeting probabilities yield a negative-binomial distribution, whereas distinct probabilities require a separate analysis supplied by the paper.The resulting distribution determines the activation probability at time t for a node at path distance ℓ.
  • Fast chain computation: Computing chain activation probabilities, including cumulative probabilities through τ, takes time polynomial in log τ.This improves on the general arborescence recursion, whose running time is polynomial in τ and therefore exponential in the bit length log τ.
  • Scope and limitation: Chain cases are expected to occur frequently in practice because seed sets are typically much smaller than the original graph.The section leaves polynomial-time computation in general in-arborescences as an open problem.

5 MIA Algorithms for IC-M

This section develops MIA-based heuristics for IC-M by approximating deadline-aware influence through local in-arborescences. MIA-M uses dynamic programming, while MIA-C converts delayed propagation into ordinary IC probabilities before applying MIA.

  • Algorithm overview: MIA-M uses Theorem 5’s dynamic programming to compute exact influence on local structures, while MIA-C converts delayed propagation probabilities before seed selection.Both methods address the inefficiency of greedy influence maximization in general graphs.
  • Algorithm overview: Both algorithms construct a maximum influence in-arborescence for each node and use it to approximate influence propagated through the original network.The MIIA representation provides the local structures on which influence calculations and marginal-gain updates are performed.
  • MIA-M: MIA-M augments path length with estimated geometric meeting delays and removes paths whose augmented length exceeds the deadline τ.The augmented length sums estimated waiting times across the path, incorporating meeting events and deadline feasibility.
  • MIA-M: MIIA construction prunes paths using an influence threshold θ and the deadline, trading local-region size and efficiency against seed-set quality.Maximum influence paths are obtained by converting edge probabilities to −log probabilities and applying shortest-path computation.
  • Efficiency: MIA-M and MIA-C use local structures to update marginal gains efficiently during iterative greedy seed selection.MIA-M updates affected nodes in related MIIAs, while MIA-C inherits MIA’s efficient marginal-gain updates after probability conversion.
  • MIA-C: MIA-C estimates converted edge probabilities from influence probability, meeting probability, and deadline, then applies the original MIA algorithm.The parameter β controls the estimated number of meeting attempts; experiments report β = τ as more effective than other choices in most cases.

6 LDAG Algorithms for LT-M

The LDAG-M approach combines exact activation-probability computation on DAGs with locally constructed subgraphs to efficiently approximate influence under LT-M. Because optimal local DAG construction is NP-hard, the method uses heuristic pruning and greedy seed selection.

  • Dynamic programming: Exact influence computation is #P-hard in general graphs but can be performed in time linear to DAG size.
  • Dynamic programming: The dynamic program computes LT-M activation probabilities for each node and time step using recursive predecessor activation probabilities.
  • Local DAG construction: LDAG-M constructs a small local DAG for each node, then uses influence propagated through these subgraphs to approximate influence in the original network.
  • Local DAG construction: Finding the optimal DAG satisfying the influence threshold is NP-hard, so LDAGs are constructed heuristically in a greedy fashion.
  • Local DAG construction: LDAG construction incorporates meeting probabilities through distance weights and removes nodes whose augmented path length exceeds the deadline.
  • Seed set selection: After constructing LDAGs and influence sets, LDAG-M greedily selects at most k seeds while updating incremental influence values.

7 Empirical Evaluations

Experiments compare time-aware and baseline influence-maximization algorithms across real-world networks, meeting-probability settings, deadlines, seed quality, and running time. MIA-M and MIA-C generally preserve influence quality while improving scalability, especially when meeting probabilities are nonuniform.

  • Experiment Setup: Experiments use four real-world datasets and compare MIA-M, MIA-C, Greedy, Degree, and MIA on seed quality and running time.The datasets include NetHEPT, DBLP, WikiVote, and Epinions; Greedy uses CELF with 10,000 Monte Carlo runs.
  • Experiment Setup: Meeting probabilities use degree-based weights m(u, v) = c/(dout(u)+c) with c = 5 or values uniformly sampled from {0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8}.Influence probabilities follow Weighted Cascade assignments, with additional Trivalency experiments mentioned in the setup.
  • Quality of Seed Sets: Under weighted meeting probabilities, MIA-M has the highest non-Greedy seed quality, while MIA-C is second best in most test cases.On Epinions with 50 seeds, MIA-M exceeds MIA by 99.4% at τ = 5 and 53.6% at τ = 15; on WikiVote, MIA-M matches Greedy at τ = 5 and is 3% higher at τ = 15.
  • Quality of Seed Sets: With uniformly random meeting probabilities, MIA-M, MIA-C, and MIA usually have similar influence, remain close to Greedy, and outperform Degree.MIA can catch up because seeds selected with m(u, v) = 1 and τ = |V| retain high expected influence under uniform randomness, especially as τ increases.
  • Quality of Seed Sets: MIA-M and MIA-C are more stable than MIA across meeting probabilities, while MIA performs poorly for certain probability assignments.This result contrasts with the cases where uniform randomness allows MIA to approach the time-aware methods.
  • Running Time: MIA-C and MIA run three orders of magnitude faster than Greedy, while MIA-M is two orders faster and scales to Epinions and DBLP.Greedy requires 0.5–1.3 hours on NetHEPT and WikiVote and does not finish on Epinions or DBLP within three days at τ = 5.
  • Effects of Deadline Constraints and Meeting Probabilities: Increasing the deadline from 5 to 15 raises influence spread for all algorithms, and increasing meeting probabilities also raises influence spread on NetHEPT.The meeting-probability experiment evaluates values 0.2, 0.4, 0.5, 0.6, and 0.8.

8 Conclusion and Discussions

The paper extends influence maximization to time-delayed diffusion and identifies further extensions, including login-probability models for online social networks.

  • Time-delayed IC and LT models are extended to support time-critical influence maximization, with fast heuristics proposed for solving it.
  • Login probabilities could better model online social networks, but they introduce dependencies in activation events and require more complicated dynamic programming methods.
  • The login-probability extension has only partial results, which are included in Appendix B.

A Analysis on the summation of geometric random variables

This appendix analyzes sums of geometric random variables, proving their distribution formulas by induction and supporting a technical lemma used elsewhere in the analysis.

  • The appendix provides an induction-based proof for the negative binomial distribution of sums of geometric random variables with a common parameter.
  • For geometric variables with distinct parameters, the proof establishes that the sum has zero probability below its path-length lower bound.
  • The distinct-parameter proof proceeds by decomposing the sum into mutually exclusive events, rearranging summations, and applying induction hypotheses.

B Time-Critical Influence Maximization with Login Events

The login-event models represent delayed influence through users’ intermittent online activity while retaining deadline-constrained diffusion dynamics.

  • Users independently log into online social networks over time, creating delays before they can receive influence from activated friends.
  • In IC-L, a newly active node gets one chance to influence each inactive neighbor when that neighbor first logs in after activation.
  • Both login-event models terminate naturally or at a deadline, and influence maximization remains NP-hard because each subsumes its classical counterpart when login probabilities equal 1.
  • In LT-L, an inactive node activates upon logging in when the weight from effective active in-neighbors reaches its random threshold.

B.1 Submodularity and Approximation Guarantees

The TS-L model combines triggering sets, login events, and deadlines, allowing influence spread to be analyzed through deterministic possible worlds and yielding submodularity guarantees.

  • TS-L combines the Triggering Set model with deadline constraints and login probabilities, and generalizes IC-L and LT-L.
  • In TS-L, an inactive node activates when it logs in and first observes an already active member of its triggering set.
  • The influence function is monotone and submodular under TS-L, because its possible-world functions are monotone and submodular and combine linearly.
  • Each possible world fixes triggering-set selections and login-event sequences, making influence propagation deterministic along live-edge paths.
  • A node is reachable only through a live-edge path whose activation time does not exceed the deadline, using the path with the earliest activation time when multiple paths exist.

B.2 Influence Computation under IC-L Model and LT-L Model

Exact influence-spread computation remains #P-hard under the time-delayed IC-L and LT-L models, so the paper focuses on tractable local structures such as MIA and LDAG.

  • #P-hardness persists because IC-L and LT-L subsume the classical IC and LT models when all login probabilities equal 1.

B.2.1 IC-L Model: Partial Results for Computations in an In-Arborescence

For IC-L in-arborescences, activation probabilities are computed recursively from ordered active in-neighbors and their influence probabilities, while shared login events require special handling. The presented recurrence is partial because a seed set can induce multiple activation sequences.

  • IC-L Model: IC-L activation events from different in-neighbors are dependent because they share the target node’s login event.This contrasts with the meeting-event formulation, where corresponding meeting events are independent.
  • IC-L Model: Activation probability is parameterized by an ordered sequence of active in-neighbor times and corresponding influence probabilities.The sequence is ordered by activation time, with ties broken arbitrarily.
  • IC-L Model: The recurrence separates whether the target logs in during an interval or remains logged out until a later step.In the latter case, simultaneous activation attempts combine with probability 1 −(1−p1)(1−p2).
  • IC-L Model: For one active in-neighbor, the base activation probability is (1 −ℓv)t−t1−1 · ℓv · p1; two neighbors use Equation (15).
  • IC-L Model: The recurrence takes O(m) time but applies only to a fixed active-in-neighbor sequence, requiring further analysis when multiple sequences are possible.For a seed set, the final activation probability is a linear combination over applicable sequences.
  • LT-L Model: For LT-L, activation probabilities can be computed similarly to LT-M because the live-edge representation gives each node only one incoming live edge.Seed activation probability at time t is (1 −ℓs)t · ℓs.
Loading 1204.3074v3…