Reconstructing propagation networks with temporal similarity metrics

Hao Liao, An ZengarXiv 2014 · OpenReview

TL;DR

This paper tackles the challenge of reconstructing the underlying structure of networks (like social or biological networks) by analyzing how information or diseases spread through them. They found that traditional methods struggle when the spread is too fast or too slow, and introduce a novel "temporal similarity metric" that uses the timing of information spread to significantly improve reconstruction accuracy.

What Problem Does This Paper Address?

Understanding the structure of complex networks is crucial for many applications, from predicting link formation to identifying communities. However, directly observing the full network topology can be difficult, especially for large-scale systems like social networks or biological processes. This paper focuses on a specific problem: reconstructing the network's structure (its "propagation network") by observing how something (like news or a virus) spreads through it. The challenge is that existing methods, which rely on how similar nodes are based on shared information, are sensitive to the rate at which the information spreads. Specifically, they found that when the "infection rate" (how quickly information spreads) is too high or too low, these methods become unreliable, sometimes dropping to near-zero accuracy. This is a significant limitation because the actual infection rate in real-world scenarios can vary widely.

Methods

The core of the paper is the development and evaluation of node similarity metrics for network reconstruction. They start by using the Susceptible-Infected-Removed (SIR) model to simulate news propagation on networks.

The paper then evaluates several existing node similarity metrics:

  • Common Neighbors (CN): Simply counts shared news items.
  • Jaccard Index (Jac): Normalizes common neighbors by the total number of unique news items seen by the pair, aiming to reduce the bias towards high-degree nodes.
  • Resource Allocation (RA): Measures the overlap of resources received, effectively giving more weight to shared neighbors with fewer connections.
  • Leicht-Holme-Newman (LHN): Another metric designed to account for node degrees.

The key innovation is the introduction of temporal similarity metrics. These methods augment the existing metrics by incorporating the time at which nodes receive the news. This is done by adding a term that penalizes similarity if nodes receive common news at very different times. Examples include:

  • Temporal Common Neighbors (TCN)
  • Temporal Jaccard Index (TJac)
  • Temporal Resource Allocation Index (TRA)
  • Temporal Leicht-Holme-Newman Index (TLHN)

These temporal metrics are designed to capture the idea that nodes receiving information around the same time are more likely to be connected.

Datasets

The authors evaluate their methods on:

  • Artificial Networks:
    • Scale-free networks (generated by the Barabasi-Albert model).
  • Small-world networks (Watts-Strogatz model).
  • Real-world Networks:
    • Undirected: Dolphin, Word, Jazz, E. coli, USAir, Netsci, Email, TAP, PPI.
  • Directed: Prisoners, SM FW, Neural, Metabolic, PB.

Key Insights and Ideas

  • The "Too Much Information" Problem: When the infection rate ($\beta$) is high, information spreads so rapidly that it saturates the network. This "too much information" scenario makes it difficult for similarity metrics to distinguish between true network structure and random connections, leading to poor reconstruction.
  • The "Special Range" of $\beta$: For certain similarity metrics (like Jaccard and LHN), there's a "special range" of infection rates where their performance, particularly precision and degree correlation, drops dramatically. This is attributed to the normalization terms in these metrics over-penalizing high-degree nodes when the news distribution becomes highly heterogeneous.
  • Temporal Information is Crucial: Incorporating the timing of information spread significantly improves reconstruction accuracy, especially when the infection rate is high. This is because it provides a more nuanced signal than just knowing if a node received information.
  • Resource Allocation (RA) is Robust: Among the non-temporal methods, the Resource Allocation metric showed good performance across various metrics and network types, making it a reliable choice.
  • TRA is the Best Temporal Method: The Temporal Resource Allocation (TRA) method generally achieved the highest accuracy across the board, demonstrating the power of combining temporal information with a robust similarity measure.

Key Results

  • Traditional similarity metrics (CN, Jac, LHN) show a pronounced peak in performance (AUC, Precision) at a specific infection rate ($\beta$), but their accuracy drops sharply outside this range.
  • The Temporal Common Neighbors (TCN) and Temporal Jaccard (TJac) methods significantly outperform their non-temporal counterparts, especially at higher infection rates.
  • The Temporal Resource Allocation (TRA) method consistently provides the highest AUC and Precision, showing remarkable improvement over classic methods, particularly in challenging scenarios (high $\beta$). For instance, TRA can maintain high AUC even when $\beta$ is large, where other methods fail.
  • While temporal methods improve AUC and Precision, they don't necessarily improve degree correlation, which is still heavily influenced by the normalization factor of the underlying similarity metric.
  • Reconstructing directed networks is generally more difficult than undirected networks, with lower average AUC and Precision.

Limitations and Future Work

  • Full Time Information Requirement: The proposed temporal methods require complete time information for all news propagation events. The authors acknowledge that a future direction is to develop methods that can work with partial time information.
  • Simple Spreading Model: The study uses the basic SIR model. Future work could explore more complex epidemic or information spreading models.
  • Link Prediction vs. Reconstruction: The paper highlights the distinction between link prediction and network reconstruction, noting that methods performing well in one might fail in the other. This suggests further research into tailoring methods for specific network inference tasks.
  • Other Fields: The authors suggest that their temporal similarity approach could be adapted to other fields where temporal information is available, such as link prediction in evolving networks or improving community detection.

Summary updated

Abstract

Node similarity is a significant property driving the growth of real networks. In this paper, based on the observed spreading results we apply the node similarity metrics to reconstruct propagation networks. We find that the reconstruction accuracy of the similarity metrics is strongly influenced by the infection rate of the spreading process. Moreover, there is a range of infection rate in which the reconstruction accuracy of some similarity metrics drops to nearly zero. In order to improve the similarity-based reconstruction method, we finally propose a temporal similarity metric to take into account the time information of the spreading. The reconstruction results are remarkably improved with the new method.
BibTeX
@misc{liao2014reconstructing,
  author = {Hao Liao and An Zeng},
  title = {{Reconstructing propagation networks with temporal similarity metrics}},
  year = {2014},
  eprint = {1409.8481},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1409.8481},
}
Figure