Estimating Graph Dynamics from Population Observations

This paper proposes and analyzes two consistent and asymptotically normal estimators for the edge existence probability of a dynamic Erdős–Rényi graph by observing only the population distribution of individuals moving across its vertices, without direct access to the graph's structure.

The Gist

Imagine you are a detective trying to figure out the rules of a game, but you aren't allowed to see the game board or the players' cards. You can only see the scoreboard.

That is essentially what this paper is about.

The Setup: A Shifting Dance Floor

Imagine a large dance floor with $n$ spots (vertices). There are $M$ dancers (individuals) moving around.

• The Invisible Floor: The dance floor itself is magical. Every single second, the connections between the spots (the edges) completely disappear and reappear randomly. Sometimes a spot is connected to many others; sometimes it's isolated. This is the "Dynamic Random Graph."
• The Dancers: The dancers follow a simple rule: If they are standing on a spot with many connections, they are likely to jump to a neighbor. If the spot has no connections, they stay put.
• The Mystery: You, the observer, cannot see the dance floor. You cannot see who is connected to whom. You can only see a counter on each spot telling you how many dancers are standing there at every second.

The Goal: Based only on the changing numbers on the counters, can you figure out the "magic probability" ($p$) that determines how likely it is for a connection to exist on the dance floor?

The Problem: The "Ghost" Connection

In a normal world, if you watch one dancer, you might guess their next move. But here, all the dancers are influenced by the same invisible, shifting floor.

• If the floor suddenly becomes very connected, all dancers become more active at the same time.
• If the floor becomes empty, all dancers get stuck.

This creates a hidden "groupthink" among the dancers. Even though they don't talk to each other, their movements are linked because they are all reacting to the same invisible changes. The paper asks: Can we reverse-engineer the rules of the invisible floor just by watching the crowd's collective behavior?

The Solution: Two Detective Tools

The authors propose two different mathematical "detective tools" (estimators) to solve this puzzle.

Tool 1: The "Memory" Method (Method of Moments)

Think of this as looking at how much the crowd's behavior remembers the past.

• If the floor is very stable (low probability of change), dancers tend to stay where they are. The number of people on a spot today will look very similar to the number of people there yesterday. High "memory."
• If the floor changes wildly (high probability of change), the crowd scrambles. The number of people today has almost no relation to yesterday. Low "memory."

The authors found a mathematical formula that links this "memory" (correlation) directly to the hidden probability $p$. By measuring how much the crowd's numbers correlate from one second to the next, they can calculate the exact value of $p$.

Tool 2: The "Best Guess" Method (Least Squares)

This tool is like trying to fit a curve to a messy scatter plot.

• The authors know exactly what the dancers should do on average if they knew the rules.
• They take their observations, compare them to the "ideal" behavior, and adjust their guess for $p$ until the difference between the "real" data and the "ideal" prediction is as small as possible.
• Bonus: This method is clever because it doesn't even need to assume the system has been running for a long time to settle down (stationarity); it works even if the system is still chaotic.

The Results: Do They Work?

The authors proved mathematically that both tools work perfectly if you watch long enough (as time goes to infinity).

• Consistency: If you watch for a long time, your guess will get closer and closer to the true answer.
• Normality: If you ran this experiment a thousand times, your guesses would form a nice, predictable bell curve around the true answer.

Which tool is better?
The authors ran computer simulations (like running the dance floor experiment a few thousand times on a computer) to see which tool made fewer mistakes.

• When the floor is very unstable (connections change constantly), the "Best Guess" tool is slightly better.
• When the floor is more stable, the "Memory" tool is slightly better.
• However, for most realistic scenarios, they are roughly equal in performance.

Why Does This Matter?

This isn't just about dancing or math puzzles. This is a model for real-world problems where we can't see the whole picture:

• Epidemics: We can count how many people are sick in different cities, but we can't see every single handshake or conversation that spread the virus. This paper helps us estimate how "connected" the population is based on infection counts.
• Social Media: We see how many likes a post gets, but we don't see the hidden network of who is following whom.
• Traffic: We see how many cars are at an intersection, but not the traffic light patterns or road closures causing the flow.

The Takeaway

The paper shows that even when you are blind to the underlying structure of a system (the "invisible dance floor"), you can still deduce the rules of the game by carefully watching how the crowd moves together over time. It turns a "ghost" problem into a solvable math puzzle.

Technical Summary

Here is a detailed technical summary of the paper "Estimating Graph Dynamics from Population Observations" by Braunsteins, Mandjes, and Montalescot.

1. Problem Statement

The paper addresses an inverse problem in the context of doubly stochastic networks. Specifically, the authors consider a system where:

• The Network: A dynamic Erdős–Rényi random graph with $n$ vertices and an edge existence probability $p$. Crucially, the graph is resampled independently at every discrete time step $t=1, \dots, T$.
• The Process: A population of $M$ individuals (random walkers) moves on this graph. The movement of an individual depends on the current graph structure: if an individual is at a vertex with $k$ neighbors, it jumps to a uniformly chosen neighbor with probability $k/(k+1)$ and stays put with probability $1/(k+1)$.
• The Observation Constraint: The observer does not see the graph structure or the individual trajectories. The only available data is the population count $M_{i,t}$ at each vertex $i$ at each time $t$.

Objective: Estimate the edge probability parameter $p$ solely based on the time-series of population counts $\{ \mathbf{M}_t \}_{t=1}^T$, without observing the underlying graph or individual movements.

2. Methodology

The authors propose and analyze two distinct estimators for $p$, both relying on the temporal correlation structure of the population counts.

A. Method-of-Moments Estimator ($\hat{p}_T$)

This estimator exploits the temporal covariance between the population count at a vertex at time $t$ and time $t+1$.

1. Theoretical Derivation:
   • The authors derive the conditional expectation $E[M_{i,t+1} | \mathbf{M}_t]$ using auxiliary functions $F(p)$ and $G(p)$, which represent the probabilities of staying or moving to a specific vertex.
   • They calculate the theoretical covariance $c(p) = \text{Cov}(M_{i,t}, M_{i,t+1})$. This derivation is non-trivial because the individuals are not independent; they share the same random graph realization, creating a complex dependence structure.
   • To compute the second moment $E[M_{i,t}^2]$ required for the covariance, the authors analyze the joint stationary distribution of two walkers, deriving a ratio $\kappa(p)$ based on four transition scenarios (both stay, one moves, both move from same source, both move from different sources).
2. Estimation:
   • An empirical covariance $\hat{c}_T$ is calculated from the data.
   • The estimator $\hat{p}_T$ is defined as the solution to $\hat{c}_T = c(p)$.
   • Since $c(p)$ is a strictly decreasing function of $p$, the inverse $c^{-1}(\cdot)$ is well-defined and can be computed via bisection.

B. Least-Squares Estimator ($\bar{p}_T$)

This estimator minimizes the sum of squared errors between the observed next-step population and the theoretical conditional expectation.

1. Formulation:
   • The objective is to minimize $\sum_{i,t} (M_{i,t+1} - E[M_{i,t+1} | \mathbf{M}_t])^2$.
   • Unlike the method-of-moments approach, this estimator does not require the assumption of stationarity for the derivation of the estimating equation, though asymptotic analysis assumes it.
2. Simplification:
   • Through algebraic manipulation, the first-order condition simplifies to an equation involving only the function $I(p)$ (derived from $F(p)$) and empirical moments of the data ($\sum M_{i,t}M_{i,t+1}$ and $\sum M_{i,t}^2$).
   • The estimator is given by $\bar{p}_T = I^{-1}(\text{empirical ratio})$.
   • Notably, this approach avoids the complex calculation of $\kappa(p)$ required by the method-of-moments estimator.

3. Key Contributions and Results

Theoretical Results

• Consistency and Asymptotic Normality: The paper proves that both $\hat{p}_T$ and $\bar{p}_T$ are consistent and asymptotically normal as the observation horizon $T \to \infty$ (with fixed $n$ and $M$).
• Central Limit Theorem (CLT): Using the Cramér–Wold device and the delta method, the authors establish that:
  $$\sqrt{T}(\hat{p}_T - p) \xrightarrow{d} \mathcal{N}(0, \sigma^2_{\hat{p}})$$
  $$\sqrt{T}(\bar{p}_T - p) \xrightarrow{d} \mathcal{N}(0, \sigma^2_{\bar{p}})$$
  Explicit formulas for the asymptotic variances are derived in terms of the derivatives of the moment functions and the covariance structure of the underlying Markov chain.
• Inverse Problem Insight: The work demonstrates that even with highly limited information (only aggregate counts, no graph topology), the edge probability $p$ is identifiable and estimable due to the induced dependence among walkers.

Numerical Experiments

• Normality Verification: QQ-plots confirm that the empirical distributions of both estimators align well with the theoretical normal distribution for finite $T$.
• Performance Comparison:
  • The authors define a performance metric $\nu(p)$ combining the sensitivity of the moment functions and the variability of the estimators.
  • Low $p$: The Least-Squares estimator ($\bar{p}_T$) generally has lower variance.
  • High $p$: The Method-of-Moments estimator ($\hat{p}_T$) performs slightly better.
  • Large Systems: As $n$ and $M$ increase simultaneously, the performance of both estimators becomes essentially equivalent.

4. Significance

• Bridging Static and Dynamic Models: The paper extends the literature from static random graphs and fully observed dynamic networks to the challenging regime of partially observed dynamic networks.
• Practical Applicability: The model is highly relevant to real-world scenarios where network topology is unobservable, such as:
  • Epidemiology: Estimating contact rates from infection counts without knowing the specific contact network.
  • Social Networks: Inferring connection dynamics from opinion or activity counts.
  • Financial Networks: Assessing interbank exposure dynamics from aggregate transaction data.
• Methodological Rigor: The paper provides a rigorous mathematical framework for handling the "doubly stochastic" nature of the problem, where the randomness of the graph and the randomness of the process are coupled. It highlights that even in simple settings, subtle dependence structures emerge that must be accounted for to achieve consistent estimation.

In summary, this paper provides a robust statistical framework for inferring the structural parameter of a rapidly changing random graph solely from the aggregate behavior of agents moving upon it, offering both theoretical guarantees and practical numerical insights.