PaperlayerView exact revision on arXiv

Source-linked AI summary

COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Co-evolution

Mehrdad Farajtabar, Yichen Wang, Manuel Gomez Rodriguez, Shuang Li, Hongyuan Zha, Le Song

arXiv:1507.02293v2cs.SIcs.LGphysics.soc-phstat.ML

TL;DR

Information diffusion and network evolution influence one another, but most existing models treat them separately. The paper proposes COEVOLVE, a temporal point-process model with coupled diffusion and link-creation processes, and reports that it reproduces common real-world patterns while predicting diffusion and network events more accurately than alternatives. The framework also supports efficient simulation and convex optimization for learning parameters from historical traces.

  • Problem

    Existing information-diffusion and network-evolution models mostly treat the two stochastic processes independently, despite evidence that they are coupled over time.

  • Method

    COEVOLVE jointly models diffusion and network evolution with interdependent temporal point processes, including source-aware Hawkes diffusion, information-driven link survival, efficient simulation, and convex parameter learning.

  • Results

    COEVOLVE reproduces common diffusion, static-network, and temporal-network patterns and provides significantly more accurate link and diffusion-event predictions than alternatives on large-scale Twitter data.

  • Takeaways & Limitations

    Jointly modeling information diffusion and network evolution captures coevolutionary dynamics and supports more accurate predictions of both event types.

  • Takeaways & Limitations

    The model does not yet efficiently account for processes that naturally evolve at different time scales, such as links over days and information propagation over minutes or hours.

Abstract

from arXiv · show

Information diffusion in online social networks is affected by the underlying network topology, but it also has the power to change it. Online users are constantly creating new links when exposed to new information sources, and in turn these links are alternating the way information spreads. However, these two highly intertwined stochastic processes, information diffusion and network evolution, have been predominantly studied separately, ignoring their co-evolutionary dynamics. We propose a temporal point process model, COEVOLVE, for such joint dynamics, allowing the intensity of one process to be modulated by that of the other. This model allows us to efficiently simulate interleaved diffusion and network events, and generate traces obeying common diffusion and network patterns observed in real-world networks. Furthermore, we also develop a convex optimization framework to learn the parameters of the model from historical diffusion and network evolution traces. We experimented with both synthetic data and data gathered from Twitter, and show that our model provides a good fit to the data as well as more accurate predictions than alternatives.

1 Introduction

Online information diffusion and network evolution are coupled processes, yet prior work largely models them separately. COEVOLVE jointly models their continuous-time dynamics, supports efficient simulation and convex parameter learning, and improves prediction accuracy over alternatives.

  • Motivation: Online users’ information sharing creates cascades and new links, while network changes alter how information spreads over time.Twitter evidence indicates that network changes are often triggered by information diffusion.
  • Research gap: Most prior models treat information diffusion and network evolution as independent, ignoring their mutual influence over time.The paper identifies a need for joint probabilistic models of the two processes.
  • Model: COEVOLVE is a temporal point-process model for joint information diffusion and network evolution, with two interwoven and interdependent components.The model represents both processes in continuous time and allows them to unfold simultaneously.
  • Model: The diffusion component uses an identity-revealing multivariate Hawkes process whose retweet intensity is boosted by prior events from time-varying followees.Modeling the particular source of excitation supports source-specific information dynamics and link acquisition.
  • Model: The network component models link creation as an information-driven survival process coupled to retweet events, targeting sources according to excitation and influence.Retweeting events drive link creation toward information sources.
  • Evaluation and capabilities: The model supports scalable simulation and convex likelihood-based parameter learning, while generating traces that match common diffusion and network patterns and improving predictions over alternatives.Simulation complexity is O(nd log m), with n events, m users, and d maximum followees per user.

2 Background on Temporal Point Processes

Temporal point processes represent discrete events occurring at continuous times and characterize future events through history-dependent intensities. Their density, cumulative density, survival, and likelihood functions provide the probabilistic foundation used for modeling event timing.

  • Point-process framework: A temporal point process represents a realization as a list of discrete events localized in continuous time.It can equivalently be represented by a counting process recording the number of events before time t.
  • Point-process framework: Point-process representations model inter-event times directly, avoid selecting aggregation windows, and support fine-grained temporal modeling.The framework also has substantial theoretical support.
  • Core quantities: The conditional intensity λ*(t) gives the conditional probability of observing an event in a small interval given the prior history H(t).The framework typically assumes at most one event in a sufficiently small interval.
  • Core quantities: The survival function gives the conditional probability that no event occurs until a later time, while the density and cumulative density describe when an event occurs.These quantities are illustrated together in Figure 3.
  • Process families and learning: The event-list log-likelihood enables parameter learning, while intensity forms encode phenomena such as history independence, mutual excitation, or one-event survival.The background discusses Poisson, Hawkes, and survival processes as useful functional forms.

3 Generative Model of Information Diffusion and Network Evolution

Coevolve represents retweet and link-creation events as coupled temporal point processes, so information diffusion and network evolution influence one another through shared event histories. Its identity-aware diffusion component connects source-specific retweet exposure to source-targeted link creation.

  • 3.1 Event Representation: Coevolve records tweets/retweets and link creations as triplets containing destination, source, and event time.For retweets, the source is the originator even when the destination retweets through another user; link events indicate that a user begins following a source.
  • 3.1 Event Representation: Retweet events use an identity-revealing matrix N(t), while link events use adjacency matrix A(t) to represent direct following.N_us(t) counts retweets by destination u due to source s, whereas A_us(t) indicates whether u directly follows s.
  • 3.2 Joint Model with Two Interwoven Components: The coupled intensities depend on the joint retweet and link histories, making link creation information-driven and network structure influential to diffusion.The model’s interwoven processes unfold on the same time scale and exercise bidirectional influence.
  • 3.3 Information Diffusion Process: The diffusion process uses an identity-revealing multivariate Hawkes process whose retweet intensity aggregates source-specific activity from a user’s current followees.Source-specific excitation also permits information sources to acquire links according to their informativeness.
  • 3.4 Network Evolution Process: The link-creation process combines survival and Hawkes components, using retweets by neighbors or by the user to increase source-specific following intensity.A factor 1 − A_us(t) ensures each link is created only once, and the two exposure categories close the mutual-influence loop.

4 Efficient Simulation of Coevolutionary Dynamics

The proposed simulator samples each intensity dimension independently and selects the earliest proposed event, exploiting local sparsity to avoid recomputing unaffected processes. The authors prove that its event sequence has the same distribution as Ogata’s algorithm while reducing simulation complexity.

  • Baseline Simulation: Naive Ogata simulation requires O(m^2n^2) operations to draw n events because it repeatedly reevaluates all intensity matrices.Here m is the number of nodes.
  • Proposed Simulation Algorithm: The proposed algorithm independently samples the next event from each intensity dimension and takes the minimum sampled time as the next multidimensional event.This applies the minimum-time construction to the model’s interdependent point processes.
  • Correctness: Lemma 1 establishes that the minimum sampled time matches the next event time from the summed-intensity process, while the firing dimension follows the same conditional distribution.These two facts align the proposed sampler with Ogata’s time and dimension selection.
  • Correctness: Theorem 2 states that Ogata’s algorithm and the proposed algorithm generate sample sequences with the same distribution.The proof applies the lemma after conditioning on the event history and then uses the chain rule across events.
  • Efficiency: O(nd log m) simulation complexity replaces O(n^2m^2), scaling logarithmically with nodes and linearly with edges at each time.The improvement uses sparse local updates affecting only O(d) nearby intensity functions and O(1) exponential-kernel updates.

5 Efficient Parameter Estimation from Coevolutionary Events

The paper formulates parameter learning as a jointly convex optimization problem and develops a parameter-free Minorization-Maximization algorithm with closed-form updates and global convergence guarantees.

  • Likelihood: The likelihood includes observed-event log terms and survival-probability integrals for both retweet and link processes.For unobserved destination-source pairs, the integral term represents the log survival probability.
  • Convex formulation: Parameter learning minimizes the negative joint log-likelihood subject to nonnegative parameters for baseline and excitation terms.The optimization variables are {µu}, {αu}, {ηu}, and {βs}.
  • Convexity: The optimization problem is jointly convex because the joint log-likelihood is concave in the stacked parameter vector and the constraints are linear inequalities.Therefore, the negative log-likelihood is convex over a convex feasible domain.
  • MM algorithm: The resulting MM procedure is parameter-free, insensitive to initialization, decomposes into m independent node-level problems, and is guaranteed to converge to a global optimum.The independent subproblems can be readily parallelized.
  • MM algorithm: The authors use Jensen’s inequality with auxiliary variables to lower-bound the log-likelihood and derive closed-form parameter updates.The auxiliary variables are constrained to be nonnegative and sum to one for each link event.

6 Properties of Simulated Co-evolution, Networks and Cascades

Simulations show that Coevolve generates mutually influencing retweet and link dynamics alongside diverse network structures, shrinking diameters, tunable clustering, and realistic cascade patterns.

  • Retweet and link coevolution: Retweets and link creations cluster in time, follow one another, and exhibit cross-covariance peaking near zero across simulated realizations.The authors report consistent coevolutionary behavior across nodes.
  • Network structure: The simulated largest-connected-component diameter generally decreases as network sparsity changes, after an initial increase caused by merging small components.This reproduces the reported shrinking or flattening diameter pattern of online social networks.
  • Clustering coefficient: The model generates different clustering-coefficient levels by varying α and β, supporting networks with varied degrees of triadic closure.Clustering coefficient is used as a measure proportional to triadic-closure frequency.
  • Network structure: Higher α or β values produce degree distributions closer to power laws, while β = 0 and β = 0.8 yield Erdos-Renyi-like and scale-free networks, respectively.At β = 0, growth is uniform; at β = 0.8, local growth produces clusters.
  • Bidirectional influence: Following a central node increases exposure to retweets, whereas retweets from a newly joined source are followed by links to that source.The examples illustrate both network evolution affecting diffusion and diffusion affecting network structure.
  • Cascade patterns: Higher α or β values produce shallower and wider information cascades, while the model also generates common cascade structures and heavy-tailed cascade size and depth distributions.These patterns are described as matching those observed in historical Twitter data.

7 Experiments on Model Estimation and Prediction on Synthetic Data

On synthetic 400-node networks, the estimation procedure becomes more accurate with more observed events, and Coevolve predicts link and diffusion events better than the tested alternatives.

  • Model estimation: As more events are supplied, parameter estimation becomes more accurate according to relative MAE, Kendall’s rank correlation, and test log-likelihood.The evaluation compares estimated parameters with their true values.
  • Link prediction: Coevolve predicts test link-event sources more accurately than TRF and WENG by average rank and Top1 success probability.The model is trained with increasing numbers of observed events.
  • Diffusion prediction: Coevolve predicts diffusion-event sources more accurately than a Hawkes-process baseline that does not model network evolution.The comparison uses historical events before each prediction and the same ranking measures as link prediction.

8 Experiments on Coevolution and Prediction on Real Data

Experiments on Twitter data show that the fitted model captures retweet-link coevolution and improves link and diffusion-event prediction over the evaluated alternatives.

  • Dataset: On a Twitter dataset with nearly 550,000 events from more than 280,000 users, Coevolve is evaluated for coevolution modeling and prediction.The modeled interval includes tweets, retweets, and links across multiple user layers.
  • Retweet and link coevolution: For sampled Twitter users, fitted intensities track clustered retweets and link creations, whose empirical and simulated cross-covariances both peak near zero.The similarity between empirical and model cross-covariances is reported as striking and consistent across nodes.
  • Retweet and link coevolution: Users with high α and/or β values exhibit high cross covariance between their created links and retweets.This relationship is confirmed for 1,000 randomly selected users.
  • Link prediction: For 8 · 10^4 training events, Coevolve achieves a Top-1 success probability 2.5x larger than TRF and WENG for link-source prediction.Across increasing training-event counts, the model consistently outperforms both alternatives.
  • Diffusion prediction: Modeling coevolutionary dynamics yields significantly better diffusion-source prediction than the Hawkes baseline without network evolution.The comparison is reported over increasing numbers of training events using Figure 20(c-d).
  • Model validation: Intensity-integral quantiles approximately follow the unit-rate exponential distribution, providing empirical evidence that a Hawkes process captures the real dynamics.The check uses intensities with parameters estimated from the real Twitter data.

9 Related Work

Prior work commonly modeled information diffusion and network evolution separately or empirically, while Coevolve models their bidirectional interaction and predicts event timing jointly.

  • Most prior models treated information diffusion and network evolution as independent stochastic processes, leaving joint probabilistic modeling largely absent.
  • Temporal Networks: Related temporal-network models often used discrete timing indices, with some approaches limited by insufficient flexibility or scalability.
  • Information Diffusion: Continuous-time diffusion models have supported time-sensitive tasks including hidden-topology recovery, future-event timing prediction, and cascade-source identification.
  • Co-evolution Dynamics: Empirical studies found that retweet exposure and cascades can trigger new links and connection bursts in online networks.
  • Co-evolution Dynamics: Coevolve differs by modeling bidirectional influence and predicting the precise timing of both diffusion and new-link events rather than only binary link creation.

10 Extensions

The extensions add link removal, changing node populations, external features, and connection-specific parameters while preserving the model’s core learning and simulation properties where stated.

  • Link Removal: The framework can represent link deletion by interleaving link-creation and link-removal survival processes for each node pair.A link-removal process starts when a link exists, and a new creation process is instantiated after removal.
  • Link Removal: Link-removal intensity increases when followees unfollow the same source, reflecting reduced perceived source quality.
  • Node Birth and Death: Node birth and death processes allow the number of users to vary while maintaining a non-negative network size.Node arrivals can be driven by existing network activity, while individual survival processes govern departures.
  • Node Birth and Death: Node death intensity decreases as a node becomes more active, while a baseline death rate is shared across nodes.
  • External Features: External node features can condition diffusion and link-creation intensities, including attributes such as location, followers, and tweet count.
  • External Features: When features enter intensities linearly, parameter-learning convexity and efficient simulation remain valid.
  • Connection-Specific Parameters: Connection-specific parameters distinguish the baseline and excitation associated with each actor-source pair and can be extended to include intermediate diffusion users.

11 Conclusion and Future Works

The paper concludes that a joint continuous-time point-process model captures coevolutionary patterns and improves prediction, while identifying extensions for richer dynamics and heterogeneous time scales.

  • Conclusion: The proposed model captures coevolutionary dynamics, reproduces common real-world network and diffusion patterns, and predicts both processes more accurately than prior state-of-the-art methods.
  • Future Work: The framework can incorporate broader point-process families without changing simulation efficiency or parameter-estimation convexity.
  • Future Work: Future extensions include nonlinear effects such as information overload and peer pressure based on prior diffusion or network state.
  • Future Work: Different natural time scales for link dynamics and information propagation motivate mechanisms that model heterogeneous temporal resolution.The paper notes that link dynamics may unfold over days, whereas propagation may occur over hours or minutes.
  • Future Work: Other proposed extensions include time-varying parameters and learned triggering kernels for finer temporal dynamics.

A Ogata’s Algorithm

Ogata’s algorithm samples events from multivariate temporal point processes through intensity aggregation, candidate-time rejection sampling, and dimension selection, but its naive implementation scales poorly.

  • Sampling Procedure: Ogata’s algorithm samples the next event time from a non-homogeneous Poisson process determined by the summed conditional intensity.
  • Sampling Procedure: The waiting time is exponentially distributed using the integrated intensity, after which the candidate time is accepted through rejection sampling.
  • Sampling Procedure: After accepting an event, the algorithm selects its dimension proportionally to each user’s contribution to total intensity and updates the intensities.
  • Complexity: A naive multivariate implementation requires O(U n^2) time, and the social-network application has U = O(m^2), yielding O(m^2 n^2).
Loading 1507.02293v2…