Skip to main content

Python code for the (q,s)-test

Project description

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". Preprint arXiv: 1712.00298 (2017)
———————————————————————————————————————————————————————————————————————————
Contents

LICENSE - License of qstest

README.md - README file for Github

README.txt - This README 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 (http://perso.crans.org/aynaud/communities/index.html)

label_propagation - Label propagation algorithm (https://networkx.github.io/documentation/stable/reference/algorithms/community.html)

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
———————————————————————————————————————————————————————————————————————————
Last updated: 29 November 2017

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for qstest, version 1.1.0
Filename, size File type Python version Upload date Hashes
Filename, size qstest-1.1.0.tar.gz (4.2 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page