network-archaeology

A collection of algorithms for inferring the history of random networks generated by the generalized preferential attachment model.

Pull requests are welcome.

Table of content

1. Usage
   1. Dependencies
   2. Compilation
   3. Repository layout and sample code
2. Paper
3. Miscellaneous

Usage

Dependencies

• python3
• networkx >= 2.0
• cmake (to build the sampler)
• SamplableSet >= 2.0 (used for the SMC sampler)

Compilation

The code is written in python, but it interfaces with a number of executables written in C++. These should be compiled prior to using the package. We provide a simple script compile.sh that will compile everything.

Repository layout and sample code

• example.py is script that showcases how to use the code available in this repository. The function consistency_check.run(...) carries out every step of the process automatically (network construction, obfuscation, inference, de-obfuscation, comparison). One simply needs to specify the generative model (generalized_gn or gn), its parameters (b and gamma, via a dict), and the inference technique to use (available: degree, OD, SMC).

• tools/ contains python wrappers around all important parts of the software. These modules can be imported separately if only parts of the consistency check pipeline are needed.

• generator/ contains C++ code to generate networks from various growth models (many of which are not discussed in the paper below). A wrapper is available in tools.

Paper

Phase transition in the recoverability of network history

J.-G. Young, G. St-Onge, E. Laurence, C. Murphy, L. Hébert-Dufresne and P. Desrosiers
Phys. Rev. X, 9, 041056 (2019)
Journal link (open) | arXiv link

Miscellaneous

The code used to compute the automorphisms statistics of the generated networks is more or less all in this GitHub gist. It is a small wrapper around nauty's Dreadnaut.