PROperty Computation in EnSembleS of NETworkS ($\texttt{ProcessNets}$)

This repository contains scripts for implementation of the $\texttt{ProcessNets}$ framework to compute four network science measures, namely, degree centrality, component size, PageRank (PR) centrality, and closeness centrality, in an ensemble of networks. Details regarding this workflow, a related $\texttt{nc}$-tree, and associated data and results are explained in detail in the following manuscript.

• [insert citation here]

Overview of the Project

Given an ensemble of undirected unweighted networks, each defined on the same set of nodes, but with different edge sets, this project develops a systematic and versatile framework to efficiently compute different local/global network science measures in each of the networks. The framework exploits the structural similarity among the networks to hierarchically organize them into a $\texttt{nc}$-tree and computes a network science measure by repeatedly applying an incremental dynamic algorithm. The current version of this project is implemented only for four network science measures, namely, degree centrality, component size, PageRank (PR) centrality, and closeness centrality and for five configurations of the framework and two configurations of the baseline approach.

The five configurations of the framework are designed to run on $5$ cores, wherein one core is designated for each configuration. However, we also provide the code for sequential execution of all configurations. If only a subset of these seven configurations needs to be executed, then the corresponding codes can also be easily modified. It may be noted here that the current version of the project supports only undirected and unweighted networks as the static graph and incremental dynamic graph algorithms are implemented accordingly, and can be easily modified to support other variants of networks by modifying the graph algorithms.

The project is implemented using the following programming languages:

• Preprocessing of real-world datasets: R version 4.4.2
• Functions for computations and analyses: Python versions 3.10 and 3.12. Packages like numpy, pandas, scipy, random, corals.correlation and statsmodel have been used repeatedly.
• Workflows combining several scripts: Bourne Again SHell (BASH) scripting language

Getting Started

This section will help you set up the project for the first time — from cloning the repository to running a complete example. Please follow each step in the given order.

1. Clone/download the project from GitHub to your local machine.

git clone https://github.com/BIRDSgroup/ProcesssNets PNets
cd PNets/ProcessNets

If you face any issues due to $5$ core allocation, then please use:

git clone https://github.com/BIRDSgroup/ProcesssNets PNets
cd "PNets/Miscellaneous/ProcessNets - sequential"

If you want to print the I/O and Processing Time of the codes as well, then please use:

git clone https://github.com/BIRDSgroup/ProcesssNets PNets
cd "PNets/Miscellaneous/IOP Time/ProcessNets"

2. Prepare input data.
   As previously mentioned, this framework takes as input an ensemble of networks. Suppose your ensemble is titled Ensemble. Then please create a folder titled graphs_Ensemble, and store your networks inside this folder. Each network $G_i$ should be stored in the file i.csv and should contain the edge list of the i^th network - each row representing an edge in the network. Please don't add any other extra headers and column indexes to the files.

For example, using the Python programming language, if the A variable stores the adjacency matrix of the i^th network, then you may use:

import numpy as np
edges = np.argwhere(A)
np.savetxt('graphs_Ensemble/' + str(i) + '.csv', edges, delimiter=',', fmt='%d')

Similarly, if your i^th network $G_i$ is constructed using the networkx Python package and represented using the variable Gi, then please use:

import numpy as np
import networkx as nx
#edges = list(Gi.edges()) # required only if you want to generate the list of edges
nx.write_edgelist(Gi, 'graphs_Ensemble/' + str(i) + '.csv', delimiter=",", data=False)

Additionally, a metadata file titled edge count.tsv containing information regarding of the size of each network should be present in the graphs_Ensemble folder. Every row of the file should contain the id of the network, number of nodes in the network and the number of edges in the network separated by tab. For example, suppose you have $B$ networks. Then change your working directory to graphs_Ensemble using:

cd graphs_Ensemble

If you are using Python, then please run the following script to generate edge count.tsv.

import numpy as np
for b in range(B): # replace B with the number of networks in your ensemble
   edges = np.genfromtxt(str(b) + '.csv', delimiter = ',', dtype=int)
   with open('edge count.tsv', 'a') as file:
      print(b, len(np.unique(edges)), len(edges), sep='\t', end='\n', file=file)
   file.close()

3. Executing the Framework
   Suppose your input ensemble has $B$ networks, each defined on $n$ nodes and generated from a dataset with $s$ samples. Let Results be the output folder to store all $\texttt{nc}$-trees, measurement values and other outputs. Then please run the following command from the terminal.

mkdir Results graphs_orig_Ensemble
time ./main.sh Results n B s Ensemble [options]

If you don't have the information pertaining to the number of samples on which the networks are constructed, then please use the value $-1$ for $s$ i.e.,

mkdir Results graphs_orig_Ensemble
time ./main.sh Results n B -1 Ensemble [options]

4. Optional Arguments
   Please mention the required values next to the corresponding option separated by space

   1. --measures Specifies which measures to compute.
      Valid values:
      | Value | Description |
      |----------|-------------|
      | degree | Degree centrality |
      | connectivity | Component Size |
      | pr | PageRank centrality |
      | cc | Closeness centrality |
      If nothing is specified, then all measures are computed.

   2. --config Specifies which configurations of the framework to use, i.e., the measures should be computed using which of the five $\texttt{nc}$-trees.
      Valid values:
      | Value | Description |
      |----------|-------------|
      | rstar | $\mathrm{rstar}$ |
      | slink | $\mathrm{slink}$ |
      | fpa | $\mathrm{fpa}$ |
      | upgma | $\mathrm{upgma}$ |
      | wpgmc | $\mathrm{wpgmc}$ |
      If nothing is specified, then all configurations are used.

   3. --tself Specifies if the measures should be computed using the self-implementation variant of baseline approach.
      Valid values:
      | Value | Description |
      |----------|-------------|
      | T | Compute all specified measures using this variant |
      | F | Does not compute the specified measures using this variant |
      Default value is T

   4. --tnx Specifies if the measures should be computed using the networkx package with baseline approach.
      Valid values:
      | Value | Description |
      |----------|-------------|
      | T | Compute all specified measures using this variant |
      | F | Does not compute the specified measures using this variant |
      Default value is T.

An example run: Suppose you want to compute degree centrality and PR centrality only using $\mathrm{rstar}$ and $\mathrm{slink}$ $\texttt{nc}$-trees only on an ensemble titled Eg_Ensemble with $B=100$ networks and each network defined on $n=500$ nodes. And you also want to compute the same two measures using the self-implementation variant of baseline approach but not using networkx package, then please execute the code as follows:

time ./main.sh Results 500 100 -1 Eg_Ensemble --measure degree pr --config rstar slink --tnx F

5. Outputs
   The framework output the folder Results, containing the following information:
   1. For each constructed $\texttt{nc}$-tree $\mathrm{tree} \in \{\mathrm{rstar}, \mathrm{slink}, \mathrm{fpa}, \mathrm{upgma}, \mathrm{wpgmc}\}$, a folder, titled TREE containing the following files.
      1. A file corresponding to each branch of the tree, containing the list of incremental edges along the same branch. These incremental edges are stored in the row-major flattened index, i.e., the edge $e = {i,j}$ between nodes $i$ and $j$ are stored as $i \times n + j$. Here, $i,j \in \{1,2,\ldots,n\}$.
      2. root.csv - a file containing the edge list of the root network
      3. info.tsv - a tab-separated file containing the branch id, source network id, destination network id, and number of incremental edges along the branch.
      4. child_count.tsv - this file is generated only for the tree constructed using $\mathrm{rstar}$ and contains the number of children of each branching point.
         For example, consider the branch $(G_I, G_J)$ from $G_I$ to $G_J$ with the id $x$. The list of incremental edges along this branch, i.e., $E(G_J) \setminus E(G_I)$ is stored in the file x.csv. Suppose $|E(G_J) \setminus E(G_I)| = y$. Then, the $x$^th line in info.tsv stores x \t I \t J \t y.
   2. edge count.tsv - a tab-separated file containing the number of nodes and number of edges of each network in the input ensemble
   3. error.txt - stores the total running time taken by the framework and errors, if any.
   4. output.txt - stores terminal outputs, if any.
   5. jsi.txt - stores the $\mathtt{MPJS}$ value of the ensemble.
   6. If degree centrality is computed, then:
      1. For each $\mathtt{ProcessNets}$ configuration, $\mathrm{config}$, that is executed, a file titled config degree.csv.
      2. For the baseline approach with self-implementation, if executed, a file titled mytrivial degree.csv.
      3. For the baseline approach using networkx package, if executed, a file titled trivial degree.csv.
   7. If component size is computed, then:
      1. For each $\mathtt{ProcessNets}$ configuration, $\mathrm{config}$, that is executed, a file titled config connectivity.csv.
      2. For the baseline approach with self-implementation, if executed, a file titled mytrivial connectivity.csv.
      3. For the baseline approach using networkx package, if executed, a file titled trivial connectivity.csv.
   8. If PR centrality is computed, then:
      1. For each $\mathtt{ProcessNets}$ configuration, $\mathrm{config}$, that is executed, a file titled config pr.csv.
      2. For the baseline approach with self-implementation, if executed, a file titled mytrivial pr.csv.
      3. For the baseline approach using networkx package, if executed, a file titled trivial pr.csv.
   9. Running times are stored in the following files:
      1. For each $\mathtt{ProcessNets}$ configuration, $\mathrm{config}$, that is executed, a file titled config.txt.
      2. For the baseline approach with self-implementation, if executed, a file titled mytrivial.txt.
      3. For the baseline approach using networkx package, if executed, a file titled trivial.txt.

Example Run

An example ensemble of $100$ networks constructed on $50$ nodes, along with the results it should generate, is provided in the example folder. To replicate the results, please do the following:

1. Copy the folder Example/graphs_Example to the ProcessNets folder as:

cp -a Example/graphs_Example ProcessNets

2. Create the Results directory as:

mkdir ProcessNets/Results

3. Copy the seed file as:

cp Example/seed.txt ProcessNets/Results

4. Execute the code as follows:

cd ProcessNets
time ./main.sh Results 50 100 -1 Example

All results generated will be contained in ProcessNets/Results, and will replicate Example/Results.

Replication of Results

For each dataset, we provide codes both for parallel and sequential execution of different ensembles, constructed using the same procedure on the respective datasets but with different values of the parameters. Note that, for parallel execution, each ensemble runs on dedicated $5$ cores and at most $10$ ensembles are run at a time, implying that, a minimum of $50$ cores is required for the parallel executions.

Before replicating the results, we start with cloning/downloading the project from GitHub to your local machine.

git clone https://github.com/BIRDSgroup/ProcesssNets PNets
cd PNets

• To replicate the results in Simulated Ensemble I, use:

cd "Simulated Ensemble I"

• To replicate the results in Simulated Ensemble II, use:

cd "Simulated Ensemble II"

• To replicate the results in Real-World Ensembles on variants from the Muscle Skeletal tissue, use:

cd "Real World Ensembles"/"Muscle Skeletal"

• To replicate the results in Real-World Ensembles on all chosen tissues, use:

cd "Real World Ensembles"/"All Chosen Tissues"

For executing the programs and replicating the results, please do the following:

If you want parallel execution:

time ./run_parallel.sh

If you want sequential execution:

time ./run_seq.sh

Replication of results showing I/O Time and Processing Time

To replicate these results, then please use the following:

cd "PNets/Miscellaneous/IOP Time/ProcessNets"

If you want to replicate results on ensembles from Category A, then:

cp -r "../MS - Cat A - n_1000/graphs_Muscle_Skeletal" .
cp -r "../MS - Cat A - n_1000/Muscle_Skeletal" .
time ./main.sh Muscle_Skeletal/1000 1000 1000 -1 Muscle_Skeletal

If you want to replicate results on ensembles from Category B, then:

cp -r "../MS - Cat B - n_1000/graphs_Muscle_Skeletal" .
cp -r "../MS - Cat B - n_1000/Muscle_Skeletal" .
time ./main.sh Muscle_Skeletal/1000 1000 1000 -1 Muscle_Skeletal