README.md

Python code for examining the effect of micro-scale structures on communities in network science

This code accompanies the paper Micro, Meso, Macro: the effect of triangles on communities in networks (Sophie Wharrie, Lamiae Azizi, Eduardo G. Altmann). It provides two generative models for networks with a tunable density of triangles and four community detection techniques. The user can experiment with their own choice of parameter values to examine the effect of triangles on communities.

Code authored by Sophie Wharrie - 2018 Honours student in Applied Mathematics at the University of Sydney.

---

Setup

As a result of the nature of this work drawing upon community detection methods developed by other researchers, there are a number of software packages that must be installed prior to running the code.

Download the code.

Install the (required) dependencies:

• NetworkX: https://networkx.github.io/
• python-igraph: http://igraph.org/python/
• graph-tool: https://graph-tool.skewed.de/
• MATLAB Engine for Python: https://au.mathworks.com/help/matlab/matlab-engine-for-python.html

Note: since some users may not be able to easily install all the above dependencies on their system, it is possible to comment out the relevant import statements and still run parts of the code. A guide on how to do this is given at the bottom of this page.

---

Usage tutorial

The Network class creates network objects from the generative models and provides methods for examining the community structure.

To get started with the code, first import the Network class:

>>> from network import *

Generating networks

A network is generated by initialising an object from the Network class, specifying three parameters:

Parameter	Description	Accepted values
model	the generative network model	triadic_closure or configuration
N	the network size (number of nodes)	a positive integer
t	the clustering tuning parameter (density of triangles in the network)	model dependent: corresponds to 0 <= p <= 1 for the triadic_closure model and 0 <= c <= 0.2 for the configuration model

For example, to generate a network of size 500 nodes from the triadic closure model with a high density of triangles:

>>> example_network1 = Network(model=triadic_closure, N=500, t=0.9)

Or, to generate a network of size 100 nodes from the configuration model with a low density of triangles:

>>> example_network2 = Network(model=configuration, N=100, t=0.01)

Community detection

The get_communities() function allows the user to choose from four methods (modularity, infomap, spectral, sbm) and returns a list of integers indicating the community assignment of each node:

>>> sbm_communities = example_network1.get_communities(method='sbm')

>>> print(sbm_communities)
[2, 1, 1, 2, 2, 1, 3, 4, 5, 1, 5, 3, 6, 4, 5, 3, 7, 8, 5, 5, 4, 7 ... ]

The number of communities detected can be obtained from the get_number_communities() function:

>>> number_sbm_communities = get_number_communities(sbm_communities) #  equivalently, max(sbm_communities)

>>> print(number_sbm_communities)
9

The communities_summary() function runs all four community detection methods and prints a summary of the number of communities detected and community similarity between different methods:

>>> example_network1.communities_summary()

######################## 

Network model: triadic_closure
Network size: 500
Clustering parameter: 0.9
Clustering coefficient: 0.250

######################## 

NUMBER OF COMMUNITIES

modularity: 15
infomap: 58
spectral: 20
sbm: 9

######################## 

COMMUNITY SIMILARITY (AMI)

modularity-infomap: 0.519
modularity-spectral: 0.652
modularity-sbm: 0.529
infomap-spectral: 0.538
infomap-sbm: 0.406
spectral-sbm: 0.492

######################## 

Community similarity

Community similarity is quantified by the adjusted mutual information (AMI), which can be calculated between community pairs using the get_similarity() function:

>>> modularity_communities = example_network1.get_communities(method='modularity')
>>> infomap_communities = example_network1.get_communities(method='infomap')
>>> ami = get_similarity(modularity_communities, infomap_communities)

>>> print(ami)
0.5430566997920288

Plotting networks

Network plots are saved using a filename specified by the user:

>>> example_network1.plot(filename='plot1.png')

There is an optional communities parameter, and if used colour-codes nodes according to the given community partition:

>>> example_network1.plot(filename='plot2.png', communities=sbm_communities)

NetworkX

We can also retrieve the generated networks as NetworkX Graph objects (using the graph() function) to then apply functions from the NetworkX package (e.g. to calculate the clustering coefficient):

>>> G = example_network1.graph()
>>> C = nx.transitivity(G) # clustering coefficient

>>> print(C)
0.25004831358249774

Extensions

We can use the above functions to perform more complex numerical simulations on generated networks.

For example, we could (using Matplotlib) plot the number of communities detected by the SBM method as a function of the clustering parameter.

>>> ps = np.arange(0,1.1,0.1) # vary p between 0 and 1
>>> numcom = [0]*len(ps) # store number of communities detected
>>> for i in range(len(ps)):
>>>     # for each value of p, generate a triadic closure network and get the number of communities detected
>>>     p = ps[i]
>>>     network = Network(model=triadic_closure, N=1000, t=p)
>>>     sbm_communities = network.get_communities(method='sbm')
>>>     numcom[i] = get_number_communities(sbm_communities)

>>> # plot the data
>>> fig, ax = plt.subplots()
>>> ax.plot(ps, numcom, 'o-')
>>> ax.set_xlabel("$p$")
>>> ax.set_ylabel("$N_c$")
>>> ax.set_title("SBM method")
>>> fig.savefig('sbm_plot.png', dpi=250)

---

References

The Python code was written entirely by Sophie Wharrie, while the MATLAB code in the matlab directory was adapted from code sourced from other authors.

Where the mathematical ideas of other authors have been used, I have cited them in the code. I also draw upon the following code sourced from other authors:

• Modularity method: (A. Clauset, M.E.J. Newman and C. Moore) http://igraph.org/python/doc/igraph.Graph-class.html#community_fastgreedy (also available at https://www.cs.unm.edu/~aaron/research/fastmodularity.htm)
• Infomap method: (M. Rosvall and C. T. Bergstrom) http://igraph.org/python/doc/igraph.Graph-class.html#community_infomap (also available at http://www.mapequation.org/code.html)
• Spectral method: (A. Saade, F. Krzakala and L. Zdeborova) http://mode_net.krzakala.org/
• Stochastic block model (SBM) method: (T.P. Peixoto) https://graph-tool.skewed.de/
• Adjusted mutual information (AMI): (N.X. Vinh, J. Epps and J. Bailey) http://users.monash.edu.au/~vinhn/software.htm

---

Note on import statements

The following guide explains how to run parts of the code without installing all the dependent packages. For example, a user may not have MATLAB installed on their system, but may still wish to run the SBM method from the graph-tool package.

To disable	Comment out (from community_detection.py)	Functions no longer usable
MATLAB	import matlab.engine eng = matlab.engine.start_matlab() eng.addpath('matlab') eng.addpath('matlab/spectral_subroutines')	spectral method: get_communities(method='spectral'), communities_summary() adjusted mutual information (AMI): get_similarity()
graph-tool	from graph_tool import Graph import graph_tool.inference as gt import graph_tool.generation as gen	sbm method: get_communities(method='sbm'), communities_summary()
igraph	import igraph as ig	modularity method: get_communities(method='method'), communities_summary() infomap method: get_communities(method='infomap'), communities_summary()