RModularity 0.3.0

Python library to calculate Robustness modularity of networks

Robustness Modularity

Small utility to calculate the robustness modularity, information modularity and modularity difference.

License

The software is distributed under the MIT license.

Authors

• Filipi N. Silva [e-mail]
• Santo Fortunato [e-mail]

Dependencies

Robustness Modularity requires the following dependencies:

• Python 3.6+
• Numpy
• graph-tool
• louvain
• python-igraph

Except for graph-tool all the other packages can be installed using pip:

pip install -r requirements.txt

To install graph-tool follow the instructions in the graph-tool documentation.

We recommend to install it using conda:

conda install -c conda-forge graph-tool

Installation

After installing graph-tool dependency, the tool can be installed using pip:

pip install RModularity

or from source:

pip git+https://github.com/filipinascimento/RModularity.git

Usage

We provide three networks for testing in the SampleNetworks folder. A full usage example can be found in example.py.

First import the RModularity module:

import RModularity

For this example we will be using igraph to load the sample networks and pathlib to deal with the paths:

import igraph as ig
from pathlib import Path

When multiprocessing is enabled, the all the calculations need to be done in the main process, thus use if __name__ == '__main__':. Let's load a network from the SampleNetworks folder and define some paths:

if __name__ == '__main__':
    networkName = "road-euroroad"
    # networkName = "LFR_mu0.1"
    # networkName = "LFR_mu1.0"
    
    outputSuffix = ""
    figurePath = Path("Figures")
    figurePath.mkdir(parents=True, exist_ok=True)

    g = ig.Graph.Read_GML(str(Path("SampleNetworks")/("%s.gml" % networkName)))

You can calculate the approximated robustness modularity using the RModularityFast function, which implements the fast Monte-Carlo algorithm.

    Q_rA = RModularity.RModularityFast(
        g.vcount(), # Number of nodes
        g.get_edgelist(), # Edges list
        g.is_directed(), # Directed or not
        )
    print("Q_rA = ", Q_rA)

You can use the RModularity function to calculate the robustness modularity without approximations:

    Q_r, probabilities, TPRCurve, \
     DLCurvesTrivial, DLCurvesDetected = RModularity.RModularity(
         g.vcount(), # Number of nodes
         g.get_edgelist(), # Edges list
         g.is_directed(), # Directed or not
         outputCurves=True,
         )

    print("Q_r = ", Q_r)

By setting outputCurves to True, the Trivial Partition Ratio (TPR) and the description lengths of the detected and trivial partitions will be returned.

Modularity difference (Q_diff) can be calculated using the modularityDifference function:

    Q_diff = RModularity.modularityDifference(
        g.vcount(),
        g.get_edgelist(),
        g.is_directed()
    )

Information modularity can be calculated using the informationModularity function:

    Q_DL = RModularity.informationModularity(
        g.vcount(),
        g.get_edgelist(),
        g.is_directed()
    )
    print("Q_DL = ", Q_DL)

Here we also illustrate how to generate the TPR and Description lengths plots. First let's import a few extra packages

    import numpy as np
    import matplotlib.pyplot as plt
    import matplotlib.patches as mpl_patches

Let's calculate average and std for the curves:

    avgDLCurvesTrivial = np.mean(DLCurvesTrivial, axis=1)
    avgDLCurvesDetected = np.mean(DLCurvesDetected, axis=1)
    stdDLCurvesTrivial = np.std(DLCurvesTrivial, axis=1)
    stdDLCurvesDetected = np.std(DLCurvesDetected, axis=1)

    diffDLCurves = (DLCurvesTrivial-DLCurvesDetected) / DLCurvesTrivial
    avgDiffDLCurves = np.mean(diffDLCurves, axis=1)
    stdDiffDLCurves = np.std(diffDLCurves, axis=1)

Now let's plot the TPR curve:

    fig = plt.figure(figsize=(3*1.61803398875, 3))
    ax = plt.axes((0.2, 0.2, 0.70, 0.70), facecolor='w')
    nodeCount = g.vcount()
    averageDegree = np.mean(g.degree())
    TPRArea = Q_r
    trivialRatios = TPRCurve
    ax.plot(probabilities, trivialRatios, color="#262626", lw=2.0)
    ax.fill_between(probabilities, trivialRatios, 1, color="#E8EAEA")
    ax.set_xlabel("$p$")
    ax.set_ylabel("TPR")
    ax.set_title(networkName)
    ax.set_xlim(-0.00, 1.02)
    ax.set_ylim(-0.020, 1.020)
    handles = [mpl_patches.Rectangle((0, 0), 1, 1, fc="white", ec="white",
                                     lw=0, alpha=0)] * 3
    labels = []
    labels.append("$N$ = %d" % nodeCount)
    labels.append("$\\langle k\\rangle$ = %.2f" % averageDegree)
    labels.append("$Q_{r}$ = %.2f" % TPRArea)

    ax.legend(handles, labels, loc='best',
              fancybox=False, framealpha=0,
              handlelength=0, handletextpad=0)
    ax.spines['right'].set_visible(False)
    ax.spines['top'].set_visible(False)
    for axis in ['bottom', 'left']:
        ax.spines[axis].set_linewidth(1.5)
    ax.tick_params(width=1.5)
    fig.savefig(figurePath/("TPR_%s%s.pdf" % (networkName, outputSuffix)))
    plt.close(fig)

Now let's plot the description length curve:

    fig = plt.figure(figsize=(3*1.61803398875, 3))
    ax = plt.axes((0.2, 0.2, 0.70, 0.70), facecolor='w')
    ax.plot(probabilities, avgDLCurvesDetected, lw=2.0, label="Detected")
    ax.fill_between(probabilities, avgDLCurvesDetected-stdDLCurvesDetected,
                    avgDLCurvesDetected+stdDLCurvesDetected, alpha=0.2)

    ax.plot(probabilities, avgDLCurvesTrivial, lw=2.0, label="Trivial")
    ax.fill_between(probabilities, avgDLCurvesTrivial-stdDLCurvesTrivial,
                    avgDLCurvesTrivial+stdDLCurvesTrivial, alpha=0.2)

    ax.set_xlabel("$p$")
    ax.set_ylabel("DL")
    ax.set_title(networkName)
    ax.set_xlim(-0.00, 1.02)

    ax.legend()
    ax.spines['right'].set_visible(False)
    ax.spines['top'].set_visible(False)
    for axis in ['bottom', 'left']:
        ax.spines[axis].set_linewidth(1.5)
    ax.tick_params(width=1.5)
    fig.savefig(figurePath/("DL_%s%s.pdf" % (networkName, outputSuffix)))
    plt.close(fig)

And finally, let's plot the information modularity along p:

    fig = plt.figure(figsize=(3*1.61803398875, 3))
    ax = plt.axes((0.2, 0.2, 0.70, 0.70), facecolor='w')
    ax.plot(probabilities, avgDiffDLCurves, lw=2.0, label="Detected")
    ax.fill_between(probabilities, avgDiffDLCurves-stdDiffDLCurves,
                    avgDiffDLCurves+stdDiffDLCurves, alpha=0.2)

    ax.set_xlabel("$p$")
    ax.set_ylabel("$Q_\mathrm{DL}$")
    ax.set_title(networkName)
    ax.set_xlim(-0.00, 1.02)

    ax.spines['right'].set_visible(False)
    ax.spines['top'].set_visible(False)
    for axis in ['bottom', 'left']:
        ax.spines[axis].set_linewidth(1.5)
    ax.tick_params(width=1.5)
    fig.savefig(figurePath/("DLDiff_%s%s.pdf" % (networkName, outputSuffix)))
    plt.close(fig)

Please refer to the next section for more details on how to use this library.

Full API documentation

function RModularityFast

RModularity(
    nodeCount,
    edges,
    directed=False,
    perturbationCount=48,
    detectionTrials=1,
    showProgress=True,
    useMultiprocessing=True,
    useCoarseStep = True,
    fineError=0.01,
    coarseError = 0.02,
    minSimilarTrials=2,
)

Computes the approximated Robustness Modularity of a network using a Monte-Carlo approach. Note that this approach can not procude the curves of TPR.

Parameters

• nodeCount : int
  The number of nodes in the network.
• edges : list of tuples
  A list of the edges in the network.
• directed : int, optional
  Whether the network is directed or not.
• perturbationCount : int, optional
  The number of perturbations to perform. (defaults to 25)
• detectionTrials : int, optional
  The number of times to perform community detection for each perturbed network. (defaults to 1)
• rewireResolution : int, optional
  The number values points for the rewire probabilities (from 0 to 1) to calculate the Trivial Partition Ratio (TPR) curves and Robustness Modularity. (defaults to 51)
• showProgress : bool, optional
  Shows a progress bar if enabled. (defaults to True)
• useMultiprocessing: bool, optional
  Uses parallel processing to calculate Rmodularity. (defaults to True)
• useCoarseStep: bool, optional Finds the plateal region using a binary search before applying the Monte-Carlo approach. (defaults to True)
• fineError: float, optional Error tolerance for the fine step. (defaults to 0.01)
• coarseError: float, optional Error tolerance for the coarse step. (defaults to 0.02)
• minSimilarTrials: int, optional The minimum number of similar trials to perform before stopping the Monte-Carlo approach.(defaults to 2)

Returns

• float if outputCurves is False
  The Robustness Modularity of the network.

---

function RModularity

RModularity(
    nodeCount,
    edges,
    directed=False,
    perturbationCount=25,
    detectionTrials=1,
    rewireResolution=51,
    outputCurves=False,
    showProgress=True,
    useMultiprocessing=True
)

Computes the Robustness Modularity of a network.

Parameters

• nodeCount : int
  The number of nodes in the network.
• edges : list of tuples
  A list of the edges in the network.
• directed : int, optional
  Whether the network is directed or not.
• perturbationCount : int, optional
  The number of perturbations to perform. (defaults to 25)
• detectionTrials : int, optional
  The number of times to perform community detection for each perturbed network. (defaults to 1)
• rewireResolution : int, optional
  The number values points for the rewire probabilities (from 0 to 1) to calculate the Trivial Partition Ratio (TPR) curves and Robustness Modularity.(defaults to 51)
• outputCurves : bool, optional
  Whether to save the TPR and DL curves. (defaults to False)
• showProgress : bool, optional
  Shows a progress bar if enabled. (defaults to True)
• useMultiprocessing: bool, optional
  Uses parallel processing to calculate Rmodularity. (defaults to True)

Returns

• float if outputCurves is False
  The Robustness Modularity of the network.
• (float, np.array dim=1, np.array dim=1, np.array dim=2, np.array dim=2) if outputCurves is True
  Returns a tuple of 4 values containing the Robustness Modularity, the rewire probabilities, the TPR curves, and the Description lenghts for the detected and trivial partitions.

---

function modularityDifference

modularityDifference(
    nodeCount,
    edges,
    directed=False,
    detectionTrials=100,
    nullmodelCount=100,
    detectionTrialsNullModel=10,
    showProgress=True,
    useMultiprocessing=True
)

Computes the Modularity Difference of a network.

Parameters

• nodeCount : int
  The number of nodes in the network.
• edges : list of tuples
  A list of the edges in the network.
• directed : int, optional
  Whether the network is directed or not.
• detectionTrials : int, optional
  The number of times to perform community detection for the input network (defaults to 100)
• nullmodelCount : int, optional
  The number of realizations of the null-model (configuration model) used to calculate the null-model modularity. (defaults to 100)
• detectionTrialsNullModel : int, optional
  The number of times to perform community detection for each perturbed network (defaults to 10)
• showProgress : bool, optional
  Shows a progress bar if enabled. (defaults to True)
• useMultiprocessing: bool, optional
  Uses parallel processing to calculate Rmodularity. (defaults to True)

Returns

• float
  The Modularity Difference of the network.

function informationModularity

informationModularity(nodeCount, edges, directed=False)

Computes the Information Modularity of a network.

Parameters

• nodeCount : int
  The number of nodes in the network.
• edges : list of tuples
  A list of the edges in the network.
• directed : int, optional
  Whether the network is directed or not.

Returns

• float
  The Information Modularity of the network.