skojaku / qstest

A generalised significance test for individual communities in networks

qstest

Python codes for the (q, s)-test, a significance test for individual communities in networks.

Please cite

Kojaku, S. and Masuda, N. "A generalised significance test for individual communities in networks". Sci. Rep. 8, 7351 (2018)

Contents

• LICENSE - License of qstest

• README.md - README file for Github

• README.txt - README file (text file)

• setup.py - Script for installing qstest

• requirements.txt - List of libraries installed by setup.py

• test.py - Test code for Travis CI

• .gitignore - Configuration file for GitHub

• .travis.yml - Configuration file for Travis CI

• qstest/ - Python codes for the (q, s)-test:

  • qstest/_init_.py - Header file
  • qstest/cdalgorithm_wrapper.py - Codes for community-detection algorithms
  • qstest/qstest.py contains - Codes for the (q, s)-test
  • qstest/quality_functions.py - Codes for calculating quality functions of a community
  • qstest/size_functions.py - Codes for calculating the size of a community

• examples/ - example codes:

  • examples/example1.py - Usage of qstest with a built-in quality function, community-size function and community detection algorithm
  • examples/example2.py - Usage of qstest with a user-defined quality function
  • examples/example3.py - Usage of qstest with a user-defined community-size function
  • examples/example4.py - Usage of qstest with a user-defined community-detection algorithm

Installation

You can install qstest with pip, a package management system for Python.

To install, run

pip install qstest

If this does not work, try

python setup.py install

Usage

sg, p_values = qstest(network, communities, qfunc, sfunc, cdalgorithm, num_of_rand_net = 500, alpha = 0.05, num_of_thread = 4)

Input

• network - Networkx Graph class instance

• communities - C-dimensional list of lists. communities[c] is a list containing the IDs of nodes belonging to community c. Node and community indices start from 0.

• qfunc - Quality of a community. The following quality functions are available:

  • qmod - Contribution of a community to the modularity
  • qint - Internal average degree
  • qexp - Expansion　
  • qcnd - Conductance 　 To pass your quality function to qstest, see "How to pass your quality function to qstest" below.

• sfunc - Community-size function (i.e., size of a community). The following community-size functions are available:

  • n - Number of nodes in a community
  • vol - Sum of the degrees of nodes in a community

  To pass your community-size function to qstest, see "How to pass your community-size function to qstest" below.

• cdalgorithm - Community-detection algorithm. The following algorithms are available:

  • louvain - "Louvain algorithm"
  • label_propagation - "Label propagation algorithm"

  To pass your community-detection algorithm to qstest, see "How to pass your community-detection algorithm to qstest" below.

• num_of_rand_net (optional) - Number of randomised networks (Default: 500)

• alpha (optional) - Statistical significance level before the Šidák correction (Default: 0.05)

• num_of_thread (optional) - Maximum number of CPU threads (Default: 4)

Output

• sg - Results of the significance test (C-dimensional list). sg[c] = True or False indicates that community c is significant or insignificant, respectively.
• p_values - P-values for the communities (C-dimensional list). p_values[c] is the p-value for community c.

Example (examples/example1.py)

import networkx as nx
import qstest as qs

network = nx.karate_club_graph()
communities = qs.louvain(network)
sg, p_values = qs.qstest(network, communities, qs.qmod, qs.vol, qs.louvain)

How to pass your quality function to qstest

Write a quality function of a community as follows:

q = my_qfunc(network, community)

Input

• network - Networkx Graph class instance
• community - List of nodes belonging to a community

Output

• q - Quality of the community

Then, pass my_qfunc to qstest:

sg, p_values = qstest(network, communities, my_qfunc, sfunc, cdalgorithm)

Example (examples/example2.py)

import networkx as nx
import qstest as qs

# Number of intra-community edges
def my_qfunc(network, nodes):
    return network.subgraph(nodes).size()

network = nx.karate_club_graph()
communities = qs.louvain(network)
sg, p_values = qs.qstest(network, communities, my_qfunc, qs.vol, qs.louvain)

How to pass your community-size function to qstest

Write a community-size function of a community as follows:

s = my_sfunc(network, community)

Input

• network - Networkx Graph class instance
• community - List of the IDs of nodes belonging to a community

Output

• s - Size of the community

Then, pass my_sfunc to qstest:

sg, p_values = qstest(network, communities, qfunc, my_sfunc, cdalgorithm)

Example (examples/example3.py)

import networkx as nx
import qstest as qs

# Square of the number of nodes in a community
def my_sfunc(network, nodes):
    return len(nodes) * len(nodes)

network = nx.karate_club_graph()
communities = qs.louvain(network)
sg, p_values = qs.qstest(network, communities, qs.qmod, my_sfunc, qs.louvain)

How to pass your community-detection algorithm to qstest

To pass your community-detection algorithm to qstest, write a wrapper function of the following form:

communities = my_cdalgorithm(network)

Input

• network - Networkx Graph class instance

Output

• communities - C-dimensional list of lists. communities[c] is a list containing the IDs of nodes belonging to community c.

Then, pass my_cdalgorithm to qstest:

sg, p_values = qstest(network, communities, qfunc, sfunc, my_cdalgorithm)

If the community-detection algorithm requires parameters such as the number of communities, then pass the parameters as global variables, e.g., define a global variable X, then use X within the cdalgorithm.

Example (examples/example4.py)

import networkx as nx
import qstest as qs
from networkx.algorithms import community as nxcdalgorithm

# Wrapper function for async_fluidc implemented in Networkx 2.0
def my_cdalgorithm(network):
    communities = []
    subnets = nx.connected_component_subgraphs(network)
    for subnet in subnets:
        coms_iter = nxcdalgorithm.asyn_fluidc(subnet, min([C, subnet.order()]), maxiter)
        for nodes in iter(coms_iter):
            communities.append(list(nodes))
    return communities

# Pareameters of async_fluidc
C = 3
maxiter = 10

network = nx.karate_club_graph()
communities = my_cdalgorithm(network)
sg, p_values = qs.qstest(network, communities, qs.qmod, qs.vol, my_cdalgorithm)

Requirements

• Python 2.7, 3.4 or later
• SciPy 1.0 or later
• Networkx 2.0 or later
• python-louvain 0.9

qstest's Issues

Installation fails

Hi there,

Just to let you know that both pip install qstest and python setup.py install failed to install the module. Installation was attempted on a Ubuntu 18.04 in a python3.6 virtual environment.

It seems pip could not download the installation files into ./venv/lib/python3.6/site-packages/--only qstest-1.1.0.dist-info was present. Could this be related to Github's token authentication?

I finally got it installed by cloning your repo and running python /path/to/repo/setup.py install