Arborescence Hierarchicalness
Arborescence Hierarchicalness
implemented by me
Download ZIP File
This is the companion data and code for the paper “An Arborescence Score to Estimate Hierarchicalness in Directed Complex Networks”, submitted to the PLoS One journal.
The archive contains six folders:
– “01_implementation”: here you can find the implementations of the arborescence score described in the paper. Given a directed network, it will return a score from zero to one proportional to its degree of hierarchicalness. The code requires the Python library “Networkx” and the graph passed as input is assumed to be a networkx object. To use it, place the “hierarchicalness.py” file in the folder containing your scripts and refer to this minimal example:
import hierarchicalness as h # Import your graph as networkx object stored in variable "G" arb = h.arborescence(G)
The arborescence function takes several optional parameters:
– reverse: if the edge directions in your graph need to be reversed, because they express dependence instead of control.
– return_extras: if you want the function to return the number of edges in the collapsed graph besides the arborescence score.
– return_roots: if you want to have the set of nodes in the roots of the arborescence forest instead of the score itself.
The rest of the functions are provided as utility, since currently the Global Reaching Centrality is not implemented in Networkx, but will be in the next version — implementation from the draft function for Networkx 2.0.
– “02_synth_tests”: a series of Python, Gnuplot and Bash scripts to reproduce Figures 3 to 5. Simply run the scripts one after the other and you will obtain on standard output or file output the results discussed in the paper. Gnuplot needed to visualize the figures. Tested with Python 2.7 and the standard terminal in Ubuntu 16.04 LTS.
– “03_yeast” and “04_hiring”: the two folders contain the tests to replicate part of Table 1, and Figures 6 and 7. Simply run “01_calculate_scores.py” to generate the null score distributions and obtain the number of standard deviations separating the observed score from the null ones. Note that these scripts will only generate a hundred null models while in the paper we used 25000, to save time for verifying the results. Simply change the loop parameter to increase the number of iterations.
The hiring network has an additional script: “02_find_roots.py”. One you run it, it will return the node(s) in the root according to GRC and the arborescence score.
– “05_scalability”: a Python script to replicate Figure 8. Run the file passing “arb”, “fh” or “grc” as single command-line argument to generate the runtime table for each method. GRC will take some time and memory for the node test, you can reduce the node list by deleting all values above 20k.
– “06_agony” contains the scripts to reproduce the agony results for all figures and tables where Agony is mentioned. Notice that you have to compile the C++ agony code from subfolder 01. This is necessary, because you need our modified Agony code (Tatti’s implementation will not work). Credit for the implementation should go to Tatti
