DANI: A Fast Diffusion Aware Network Inference Algorithm

Maryam Ramezani, Hamid R. Rabiee, Maryam Tahani, Arezoo RajabiarXiv 2017 · OpenReview

Abstract

The fast growth of social networks and their privacy requirements in recent years has led to increasing difficulty in obtaining the complete topology of these networks. However, diffusion information over these networks is available, and many algorithms have been proposed to infer the underlying networks by using this information. The previously proposed algorithms only focus on inferring more links and do not pay attention to the important characteristics of the underlying social networks. In this paper, we propose a novel algorithm, called DANI, to infer the underlying network structure while preserving its properties by using the diffusion information. Moreover, the running time of the proposed method is considerably lower than the previous methods. We applied the proposed method to both real and synthetic networks. The experimental results showed that DANI has higher accuracy and lower run time compared to well-known network inference methods.

Introduction

In modern social networks, accessing the full topology—the map of connections—is often impossible due to privacy settings and the dynamic nature of the networks. However, "cascades"—the observable paths of information, memes, or viruses—are often visible through timestamps. The challenge of "Network Inference" is to work backward from these timestamps to reconstruct the underlying graph.

Existing tools like NETINF or MultiTree often struggle to capture the "modular" nature of social networks, where nodes form dense clusters or communities. Furthermore, these tools typically rely on slow, iterative optimization processes that do not scale to massive datasets. DANI (Diffusion Aware Network Inference) addresses these gaps by prioritizing community structure preservation and computational efficiency.

Methodology

DANI shifts away from greedy optimization toward a probabilistic Markov Chain approach. It utilizes two primary signals to infer links:

  1. Diffusion Signal: Based on the Markov Property, nodes infected closer together in time are more likely to be directly connected.
  2. Community Signal: Using a Jaccard-like similarity index, DANI assumes that nodes appearing together in many different cascades likely belong to the same community.
Illustration of diffusion cascades across a network with modular community structures.

Unlike baseline methods that add edges iteratively, DANI computes a global transition matrix and selects the top $K$ edges in a single pass. To ensure robustness against varying diffusion speeds, DANI converts raw timestamps into discrete "infection labels" based on their sequence in a cascade.

Key Insights

A core premise of DANI is that communities act as diffusion buffers: information spreads rapidly within a community but slows down when crossing "weak ties" between them. By rewarding node pairs that co-participate in many cascades, DANI effectively identifies intra-community links.

Furthermore, by reframing the inference problem as a Markov Chain transition matrix calculation, the authors achieved a complexity of $O(M \times \bar{n}_c^2)$, where $M$ is the number of cascades and $\bar{n}_c$ is the average cascade size. This allows DANI to remain accurate even with short cascades, a scenario where traditional methods often fail.

Experimental Evaluation

The researchers evaluated DANI against three major baselines (NETINF, DNE, and MultiTree) using synthetic LFR-Benchmarks and real-world datasets including NetScience, LinkedIn, and News of the World.

  • Accuracy: DANI demonstrated significant improvements in F-measure, showing a 35.1% improvement over NETINF on the LinkedIn dataset and a 77.91% improvement on the News of the World dataset.
  • Speed and Scalability: DANI is significantly faster than NETINF and MultiTree. In a large-scale Twitter test involving 124,023 nodes, DANI inferred nearly 80% of links in approximately 4 minutes, while competing methods failed to produce reasonable results in a comparable timeframe.
  • Structural Integrity: The inferred networks consistently matched the ground truth in terms of density and conductance, outperforming methods that ignore community structure.

Conclusion

DANI provides a high-speed, accurate solution for network inference that respects the modular nature of social structures. While it currently requires the number of links ($K$) as an input, it represents a major step forward in scalability. Future work may involve detecting communities directly from diffusion data to further optimize computational resources.

Summary updated

Abstract

The fast growth of social networks and their privacy requirements in recent years, has lead to increasing difficulty in obtaining complete topology of these networks. However, diffusion information over these networks is available and many algorithms have been proposed to infer the underlying networks by using this information. The previously proposed algorithms only focus on inferring more links and do not pay attention to the important characteristics of the underlying social networks In this paper, we propose a novel algorithm, called DANI, to infer the underlying network structure while preserving its properties by using the diffusion information. Moreover, the running time of the proposed method is considerably lower than the previous methods. We applied the proposed method to both real and synthetic networks. The experimental results showed that DANI has higher accuracy and lower run time compared to well-known network inference methods.
BibTeX
@misc{ramezani2017dani,
  author = {Maryam Ramezani and Hamid R. Rabiee and Maryam Tahani and Arezoo Rajabi},
  title = {{DANI: A Fast Diffusion Aware Network Inference Algorithm}},
  year = {2017},
  eprint = {1706.00941},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1706.00941},
}

Loading related content...

Figure