Community Detection Label Propagation (LP)

Information about the LP CGE graph algorithm

URI

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

Description

The Label Propagation algorithm is used for detecting communities in networks and assigns vertices in the graph to communities. Each vertex is initially assigned to its own community. At every step, each vertex looks at the community affiliation of all its neighbors, and updates their state to the mode community affiliation. The mode community affiliation takes into account the edge weights.

The Label Propagation algorithm is relatively inexpensive, but convergence is not guaranteed.

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
The number of steps that the algorithm executes. Currently an early exit is not included if convergence is detected. Therefore, the algorithm executes the number of steps specified in the input.	`20`

Outputs

A call to the Label Propagation 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: Label Propagation

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_LP(5)
PRODUCING ?vertex ?comm
}
ORDER BY ?comm