Louvain Parallel Extension

CHAMP can be used with partitions generated by any community detection algorithm. One of the most popular and fast algorithms is known as Louvain [1] . We provide an extension to the python package developed by Vincent Traag, louvain_igraph [2] to run Louvain in parallel, while calculating the coefficients necessary for CHAMP. Currently, this extension only support single-layer network. The random seed is set within each parallel process to ensure that the results are stochastic over each run. In general this is desireable because Louvain uses a greedy optimization schema that finds local optima.

champ.louvain_ext.parallel_louvain(graph, start=0, fin=1, numruns=200, maxpt=None, numprocesses=None, attribute=None, weight=None, node_subset=None, progress=False)

Generates arguments for parallel function call of louvain on graph

Parameters:

• graph – igraph object to run Louvain on
• start – beginning of range of resolution parameter \(\gamma\) . Default is 0.
• fin – end of range of resolution parameter \(\gamma\). Default is 1.
• numruns – number of intervals to divide resolution parameter, \(\gamma\) range into
• maxpt (int) – Cutoff off resolution for domains when applying CHAMP. Default is None
• numprocesses – the number of processes to spawn. Default is number of CPUs.
• weight – If True will use ‘weight’ attribute of edges in runnning Louvain and calculating modularity.
• node_subset – Optionally list of indices or attributes of nodes to keep while partitioning
• attribute – Which attribute to filter on if node_subset is supplied. If None, node subset is assumed to be node indices.
• progress – Print progress in parallel execution

Returns:

PartitionEnsemble of all partitions identified.

We also have created a convenient class for managing and merging groups of partitions called champ.louvain_ext.PartitionEnsemble . This class stores the partitions in membership vector form ( i.e. a list of N community assignments), as well as the coefficients for the partitions. As part of its class methods, the PartitionEnsemble is able to apply CHAMP to its own partitions and store their domains.

class champ.louvain_ext.PartitionEnsemble(graph=None, listofparts=None, name='unnamed_graph', maxpt=None)

Group of partitions of a graph stored in membership vector format

The attribute for each partition is stored in an array and can be indexed

Variables:

• graph – The graph associated with this PartitionEnsemble. Each ensemble can only have a single graph and the nodes on the graph must be orded the same as each of the membership vectors.
• partitions – List of membership vectors for each partition
• int_edges – Number of edges internal to the communities
• exp_edges – Number of expected edges (based on configuration model)
• resoltions – If partitions were idenitfied with Louvain, what resolution were they identified at (otherwise None)
• orig_mods – Modularity of partition at the resolution it was identified at if Louvain was used (otherwise None).
• numparts – number of partitions
• ind2doms – Maps index of dominant partitions to boundary points of their dominant domains

add_partitions(partitions, maxpt=None)

Add additional partitions to the PartitionEnsemble object

Parameters:partitions (dict,list) – list of partitions to add to the PartitionEnsemble

apply_CHAMP(maxpt=None)

Apply CHAMP to the partition ensemble.

Parameters:maxpt (int) – maximum domain threshhold for included partition. I.e partitions with a domain greater than maxpt will not be included in pruned set

calc_expected_edges(memvec)

Uses igraph Vertex Clustering representation to calculate expected edges. see louvain_ext.get_expected_edges()

Parameters:memvec (list) – membership vector for which to calculate the expected edges Returns:expected edges under null Return type:float

calc_internal_edges(memvec)

Uses igraph Vertex Clustering representation to calculate internal edges. see louvain_ext.get_expected_edges()

Parameters:memvec (list) – membership vector for which to calculate the internal edges. Returns:

get_CHAMP_indices()

Get the indices of the partitions that form the pruned set after application of CHAMP

Returns:list of indices of partitions that are included in the prune set sorted by their domains of dominance Return type:list

get_CHAMP_partitions()

Return the subset of partitions that form the outer envelop. :return: List of partitions in membership vector form of the paritions :rtype: list

get_adjacency()

Calc adjacency representation if it exists

Returns:self.adjacency

get_coefficient_array()

Create array of coefficents for each partition

Returns:np.array with coefficents for each of the partions

get_partition_dictionary(ind=None)

Get dictionary representation of partitions with the following keys:

‘partition’,’resolution’,’orig_mod’,’int_edges’,’exp_edges’

Parameters:ind (int, list) – optional indices of partitions to return. if not supplied all partitions will be returned. Returns:list of dictionaries

merge_ensemble(otherEnsemble)

Combine to PartitionEnsembles. Checks for concordance in the number of vertices. Assumes that internal ordering on the graph nodes for each is the same.

Parameters:otherEnsemble – otherEnsemble to merge Returns:new PartitionEnsemble with merged set of partitions

static open(filename)

Loads pickled PartitionEnsemble from file.

Parameters:file – filename of pickled PartitionEnsemble Object Returns:writes over current instance and returns the reference

save(filename=None)

Use pickle to dump representation to compressed file

Parameters:filename –

Partition Ensemble Example

We use igraph to generate a random ER graph, call louvain in parallel, and apply CHAMP to the ensemble.

import champ
from champ import louvain_ext

import igraph as ig
import tempfile
import numpy as np
import matplotlib.pyplot as plt

np.random.seed(0)
test_graph=ig.Graph.Erdos_Renyi(500,p=.05)
#Create temporary file for calling louvain
tfile=tempfile.NamedTemporaryFile('wb')
test_graph.write_graphmlz(tfile.name)

#non-parallelized wrapper
ens1=louvain_ext.run_louvain(tfile.name,nruns=30,gamma=1)

#parallelized wrapper
ens2=louvain_ext.parallel_louvain(test_graph,
                                  numruns=10,
                                  numprocesses=2,
                                  progress=True)

#Output as gzipped file
ens2.save("test_esemble_file.gz")



#Apply Champ to Coefficients
coeffs2=ens2.get_coefficient_array()
ind2dom2=champ.get_intersection(coeffs2)
plt.close()
ax=champ.plot_single_layer_modularity(ind2dom2)
plt.show()

References

[1]	Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, pages P10008, 2008.

[2]	Vincent Traag. Louvain igraph. http://github.com/vtraag/louvain-igraph.

• Index
• Search Page