Maximum likelihood estimation of burst-merging kernels for bursty time series

This paper introduces a maximum likelihood estimation method to infer burst-merging kernels from bursty time series, enabling the precise characterization of their hierarchical burst structures and underlying mechanisms through both synthetic and empirical data validation.

The Gist

Imagine you are watching a busy city street. Sometimes, nothing happens for hours. Then, suddenly, a whole crowd rushes past in a few seconds, followed by another long quiet spell. In the world of data, this is called a "bursty" time series. It happens everywhere: people texting in a frenzy, earthquakes shaking the ground, or neurons firing in your brain.

For a long time, scientists could describe when these bursts happened, but they struggled to understand how the small bursts grew into big ones. This paper introduces a new, smarter way to decode that growth pattern.

Here is the breakdown of the paper using simple analogies:

1. The "Lego Tower" of Time

Imagine every single event (a tweet, a heartbeat, an earthquake) is a single Lego brick.

• The Problem: If you just look at the bricks, it's a mess.
• The Solution (Burst Trees): The authors imagine building a tower. When two bricks are close together in time, you glue them together to make a "small burst." When two small bursts are close enough, you glue them to make a "medium burst." Eventually, you glue everything together into one giant tower.
• The Result: This creates a family tree (called a Burst Tree) that shows exactly how tiny events merged into massive events. It reveals the hidden hierarchy of the chaos.

2. The "Glue Recipe" (The Kernel)

The big question is: What is the rule for gluing them together?
Why do some bursts merge easily while others stay apart? Is it random? Do big bursts attract other big bursts (like celebrities attracting more fans)? Or do similar-sized bursts stick together?

The authors call this rule the "Burst-Merging Kernel." Think of it as the secret recipe for the glue.

• Old Method: The previous way to guess this recipe was like trying to figure out a cake recipe by tasting the cake once and guessing the ingredients. It was a rough estimate and often inaccurate.
• New Method: This paper introduces Maximum Likelihood Estimation (MLE). Imagine you have a super-smart detective who tastes the cake 100 times, measures the sugar, flour, and eggs with perfect precision, and mathematically calculates the exact recipe that would produce that cake. That is what this new method does for time series data.

3. How the Detective Works (The Process)

The authors developed a mathematical algorithm that acts like a feedback loop:

1. Guess: Start with a random guess for the "glue recipe."
2. Simulate: Use that recipe to try and rebuild the time series from scratch.
3. Compare: See how different the rebuilt version is from the real data.
4. Adjust: Tweak the recipe slightly to make the simulation match the real data better.
5. Repeat: Do this over and over until the recipe is perfect.

They proved mathematically that this process always finds the best possible recipe, not just a good guess.

4. Testing the Detective

To prove their new detective works, they created fake time series using known "recipes" (like "always glue randomly," "glue big things to big things," or "glue similar things together").

• The Result: When they ran their new method on the fake data, it perfectly recovered the original recipes. It worked like a charm.

5. Real-World Applications

Finally, they applied their method to real-life data:

• Wikipedia Editors: How editors edit pages in bursts.
• Twitter Users: How people tweet in clusters.
• Heartbeats: The rhythm of a healthy human heart.
• Earthquakes: How tremors cluster together.

What did they find?
They discovered that nature loves two specific patterns:

1. Preferential Merging: Big bursts tend to attract other big bursts (the "rich get richer" effect).
2. Assortative Merging: Bursts of similar sizes like to stick together.

Why Does This Matter?

Before this paper, we could see the "what" (the bursts happened), but we couldn't easily see the "how" (the mechanism).

• The Analogy: It's like seeing a car crash. You know where it happened. But this new method tells you why it happened—was it bad brakes? A slippery road? Or a driver who was too fast?
• The Impact: By understanding the "glue recipe" behind the data, scientists can better predict future events, understand the underlying mechanisms of complex systems (like why social media trends explode), and build more accurate models of the world.

In a nutshell: This paper gives us a high-precision microscope to see the invisible rules that govern how chaos organizes itself into patterns.

Technical Summary

1. Problem Statement

Many natural and social processes generate bursty time series, where events occur in rapid clusters (bursts) separated by long inactive periods. While the burst-tree decomposition method (introduced in prior work, Ref. [23]) successfully reveals the hierarchical structure of these bursts across different timescales, a rigorous statistical method to quantify the underlying mechanism was lacking.

Specifically, the burst-merging kernel ($K_{bb'}$), which dictates the probability of two bursts of sizes $b$ and $b'$ merging as the timescale increases, is crucial for understanding the system's dynamics. Previous attempts to estimate this kernel (Ref. [23]) relied on a heuristic ratio of observed merges to expected probabilities. While useful, this method was not statistically rigorous, potentially leading to biased or inaccurate characterizations of the underlying mechanisms (e.g., preferential or assortative merging). The authors aim to develop a Maximum Likelihood Estimation (MLE) method to estimate the burst-merging kernel with statistical rigor.

2. Methodology

A. Burst-Tree Decomposition

The authors utilize the burst-tree framework where a time series of $n$ events is mapped to a tree structure:

• Leaf Nodes: Individual events (size 1) at the smallest timescale.
• Internal Nodes: Merges of two bursts occurring when the timescale $\Delta t$ exceeds the interevent time (IET) between them.
• Ordinal Burst Tree ($G$): A representation of the merging sequence independent of specific IET values, defined by tuples $(u, v, w)$ representing parent $u$ and children $v, w$.
• Merging Process: Analogous to coagulation processes in statistical physics. Starting with $n$ bursts of size 1, bursts are sequentially merged until one burst of size $n$ remains. The kernel $K_{bb'}$ governs the probability of merging a burst of size $b$ with a subsequent burst of size $b'$.

B. Maximum Likelihood Estimation (MLE)

The core contribution is the derivation of an MLE for the kernel matrix $K = \{K_{bb'}\}$.

1. Likelihood Formulation: The likelihood of observing the ordinal burst tree data given the kernel $K$ is modeled as a product of multinomial distributions over the merging steps $s$ (from $0$ to $n-1$).
   $$L(K) = \prod_{s=1}^{n-1} P(G_s | G_{s-1}, K)$$
   where $P(G_s | G_{s-1}, K)$ depends on the probability $p_{sbb'}$ of merging sizes $b$ and $b'$ at step $s$, defined as:
   $$p_{sbb'} = \frac{Q_{s-1}(b)Q_{s-1}(b')K_{bb'}}{\sum_{k,k'} Q_{s-1}(k)Q_{s-1}(k')K_{kk'}}$$
   Here, $Q_{s-1}(b)$ is the distribution of burst sizes at step $s-1$.

2. Log-Likelihood Function: The log-likelihood $l(K)$ is derived, leading to a self-consistent equation for the optimal kernel:
   $$K_{bb'} = \frac{\sum_{s=1}^{n-1} m_{sbb'}}{\sum_{s=1}^{n-1} \frac{Q_{s-1}(b)Q_{s-1}(b')}{\sum_{k,k'} Q_{s-1}(k)Q_{s-1}(k')K_{kk'}}}$$
   where $m_{sbb'}$ is the observed count of merges between sizes $b$ and $b'$ at step $s$.

3. Iterative Algorithm: Since the equation is non-linear and self-consistent, the authors propose an iterative numerical solution:

   • Initialize $K^{(0)}_{bb'} = 1$.
   • Update $K^{(i)}$ using the previous iteration $K^{(i-1)}$ in the denominator.
   • Repeat until the change in log-likelihood falls below a convergence threshold $\epsilon$.

4. Theoretical Guarantees:

   • Appendix A: Proves that the log-likelihood function is concave, ensuring that the solution to the self-consistent equation globally maximizes the likelihood.
   • Appendix B: Proves that the iterative algorithm (using a Minorize-Maximize approach) monotonically increases the log-likelihood, guaranteeing convergence to the optimal kernel.

3. Key Contributions

• Rigorous Estimation Framework: Developed the first statistically rigorous MLE method for burst-merging kernels, replacing previous heuristic approaches.
• Theoretical Validation: Provided mathematical proofs for the global optimality of the solution and the convergence of the iterative algorithm.
• Generalizability: Demonstrated that the method works for various kernel types (constant, sum, product, and empirical forms) and is applicable to diverse empirical datasets.
• Open Source: Made the implementation code available via GitHub.

4. Results

A. Validation with Synthetic Data

The authors tested the method on time series generated from four known model kernels:

1. Constant ($K_{bb'} = 1$): Random merging.
2. Sum ($K_{bb'} = b + b'$): Preferential merging (larger bursts merge more often).
3. Product ($K_{bb'} = bb'$): Strong preferential merging.
4. Empirical ($K_{bb'}$): A complex kernel exhibiting both preferential and assortative (similar size) merging.

Outcome: The estimated kernels from the synthetic data showed excellent agreement with the ground-truth model kernels across all cases. This validated the accuracy and robustness of the MLE method.

B. Application to Empirical Time Series

The method was applied to four real-world datasets:

1. Wikipedia Editor: Edit sequences of a highly active editor.
2. Twitter User: Tweet sequences of a highly active user.
3. Heartbeat: Inter-beat intervals of a healthy subject.
4. JUNEC: Earthquake sequences in Japan.

Outcome:

• The estimated kernels revealed both preferential and assortative merging behaviors in all datasets.
• Preferential merging: Larger bursts tend to merge with other bursts, contributing to heavy-tailed burst size distributions.
• Assortative merging: Bursts of similar sizes tend to merge more frequently than those of vastly different sizes.
• The results were consistent with previous findings but provided a more accurate and statistically sound quantification of these mechanisms.

5. Significance

• Precise Characterization: This method allows researchers to move beyond descriptive statistics (like burst size distributions) to mechanistic understanding by precisely quantifying how bursts merge.
• Mechanism Discovery: By accurately estimating the kernel, one can infer the underlying rules driving complex systems (e.g., whether human activity is driven by memory, external triggers, or internal feedback loops).
• Cross-Disciplinary Applicability: The authors note that the method draws parallels to attachment kernels in network science and coagulation processes in physics. This suggests the MLE framework could be adapted to estimate merging rules in other stochastic processes, such as cluster formation in physical systems or link formation in temporal networks.
• Foundation for Future Models: The ability to rigorously estimate these kernels enables the construction of more accurate generative models for bursty time series, improving predictions and simulations in fields ranging from epidemiology to finance and seismology.