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
