A scalable directed graph model with reciprocal edges

Nurcan Durak, Tamara G. Kolda, Ali Pinar, C. Seshadhri

Abstract

Degree distributions are arguably the most important property of real-world networks. The classic edge configuration model or Chung-Lu model can generate an undirected graph with any desired degree distribution, serving as a robust null model for experimental studies. However, real-world networks are often directed and exhibit a significant proportion of reciprocal edges—mutual connections that represent stronger relations than one-way edges. Despite their importance, reciprocal edges have been largely disregarded by existing directed graph models. We propose the Fast Reciprocal Directed (FRD) model, a null model inspired by the Chung-Lu framework that matches the in-, out-, and reciprocal-degree distributions of real graphs. Our algorithm is highly scalable, requiring $O(m)$ random numbers to generate a graph with $m$ edges.

Introduction

In network science, null models are essential baselines for testing algorithms. While the Chung-Lu and configuration models are standard for undirected graphs, real-world networks—such as Twitter, Flickr, or the World Wide Web—are directed and exhibit high reciprocity. Reciprocity occurs when a directed edge from node A to B is matched by an edge from B to A. Most existing directed graph generators, such as Forest Fire (FF) or Stochastic Kronecker Graphs (SKG), focus on total in- and out-degree distributions but fail to replicate reciprocal structures, treating edges as simple one-way streets.

Methods: The FRD Model

The FRD generator treats a directed graph as a composition of three distinct degree distributions: reciprocal degree ($d^\leftrightarrow$), one-way in-degree ($d^\leftarrow$), and one-way out-degree ($d^\rightarrow$). The generation process occurs in two phases:

  1. Reciprocal Phase: An undirected Chung-Lu-style approach generates the "skeleton" of mutual edges.
  2. Directed Phase: A "Fast Directed" (FD) generator fills in the remaining one-way edges.

The Poisson Problem and the Blowup Factor

A common challenge in random graph generators is accurately matching the count of low-degree nodes (specifically degree-1). Standard models often under-produce these nodes because the resulting degrees follow a Poisson distribution, whereas real networks often exhibit heavy tails. To resolve this, we introduce a blowup factor ($b$). By artificially enlarging the pool of low-degree nodes during sampling, the model can precisely match the high frequency of degree-1 nodes found in real data.

The blowup factor allows the FD model to accurately match the count of low-degree nodes in the soc-Epinions1 dataset.

Results and Evaluation

We evaluated the FRD model against several large-scale networks, including citation networks (cit-HepPh), web graphs (web-NotreDame), and social networks (soc-Epinions1, YouTube, and LiveJournal).

Accuracy in Reciprocity

While models like FF and SKG can approximate total degree distributions, they produce nearly zero reciprocal edges. In contrast, FRD matches the reciprocal degree distribution of real datasets almost perfectly across all scales, as demonstrated in the soc-Epinions1 dataset.

Comparison of FRD against other models on the soc-Epinions1 dataset. FRD accurately captures in-, out-, and reciprocal-degree distributions, whereas competitors fail on reciprocity.

Scalability

Scalability is a primary design goal. The FRD algorithm requires only $O(m)$ random numbers, where $m$ is the number of edges. In empirical tests, FRD generated the soc-LiveJournal graph (over 77 million edges) in approximately 42 seconds, whereas the Forest Fire model required over 2.5 hours.

Conclusion

The FRD model provides a robust, scalable null model for directed graphs by treating reciprocity as a first-order structural property. While it successfully matches degree distributions and reciprocity, it is a static null model rather than a growth model and does not explicitly capture higher-order structures like clustering coefficients. Future work will focus on integrating triadic closure and community structures into this scalable framework while maintaining the efficiency demonstrated here.

Summary updated

Abstract

Degree distributions are arguably the most important property of real world networks. The classic edge configuration model or Chung-Lu model can generate an undirected graph with any desired degree distribution. This serves as a good null model to compare algorithms or perform experimental studies. Furthermore, there are scalable algorithms that implement these models and they are invaluable in the study of graphs. However, networks in the real-world are often directed, and have a significant proportion of reciprocal edges. A stronger relation exists between two nodes when they each point to one another (reciprocal edge) as compared to when only one points to the other (one-way edge). Despite their importance, reciprocal edges have been disregarded by most directed graph models. We propose a null model for directed graphs inspired by the Chung-Lu model that matches the in-, out-, and reciprocal-degree distributions of the real graphs. Our algorithm is scalable and requires $O(m)$ random numbers to generate a graph with $m$ edges. We perform a series of experiments on real datasets and compare with existing graph models.
BibTeX
@inproceedings{durak2013scalable,
  author = {Nurcan Durak and Tamara G. Kolda and Ali Pinar and C. Seshadhri},
  title = {{A scalable directed graph model with reciprocal edges}},
  booktitle = {NSW},
  year = {2013},
  doi = {10.1109/nsw.2013.6609190},
}
Figure