Community Detection Parallel Louvain Method (PLM)

Information about the PLM CGE graph algorithm

URI

<http://cray.com/graphAlgorithm.community_detection_PLM>

Description

The Parallel Louvain Method is used for detecting communities in networks and assigns vertices in the graph to communities. The community_dection_PLM method is a distributed memory implementation using CoarrayC++ and is inspired by the shared-memory Parallel Louvain Method in NetworKit, an open-source package (https://networkit.iti.kit.edu), and corresponding paper “Engineering Parallel Algorithms for Community Detection in Massive Networks” by Christian L. Staudt and Henning Meyerhenke. The algorithm can take up to two input parameters. The first parameter controls the maximum number of PLM steps taken. The second parameter is number of initial Label Propagation steps to take to initialize the starting communities before running the PLM steps. If the number of Label Propagation steps is set to 0, each vertex is initially assigned to its own community.

If no vertices are moved during a PLM step, the routine will exit early, returning the community assignments corresponding to the largest computed modularity score found up to this point.

Inputs and Default Values

The input graph to the Label Propagation function is expected to contain triples of the form (vertex1, weight, vertex2), where weight is an integer.


Input	Default Value
Maximum number of PLM steps. An early exit is included if convergence is detected (if no vertices are moved during a PLM step, the process has converged).	`20`
Number of Label Propagation steps to be run to initialize the starting community assignments prior to running the PLM steps.	(Input number of PLM steps)/2

Outputs

A call to the function returns an array of vertex IDs paired with an array of community IDs These IDs can be used to identify which community each vertex was assigned to.

Example: Parallel Louvain

PREFIX cray: <http://cray.com/>
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>
SELECT ?vertex ?comm
WHERE{
CONSTRUCT {
     ?sub ?weight ?obj .
} WHERE {
     ?sub <http://wga/isLinked> ?obj .
     ?sub <http://wga/hasWeightLink> ?weightURI .
     ?obj <http://wga/hasWeightLink> ?weightURI .
     ?weightURI <http://wga/hasWeight> ?weight
}
INVOKE cray:graphAlgorithm.community_detection_PLM(25,5)
PRODUCING ?vertex ?comm
}
ORDER BY ?comm