Label Propagation Algorithm

Returns the communities of the constructed graph as detected by synchronous label propagation.

The implementation of the algorithm is based on ^[1] and proceeds as follows; Every vertex is assigned an initial label at random. Looking at the labels of its neighbours, a probability is assigned to observed labels following an increasing function then the vertex’s label is updated with the label with the highest probability. If the new label is the same as the current label, the vertex votes to halt. This process iterates until all vertice labels have converged. The algorithm is synchronous since every vertex updates its label at the same time.

Parameters

• top_c (Int) – The number of top largest communities to return. If not specified, Raphtory will return all detected communities. (default: None)

Returns

• total (Int) – Number of detected communities.
• communities (List[List[Long]]) – Communities sorted by their sizes. Returns largest top_c communities if specified.

Notes

• This implementation of LPA incorporated probabilistic elements which makes it non-deterministic; The returned communities may differ on multiple executions.

Examples

In this example, the temporal network spans a time period $t \in [1,3]$ and is built into (3) snapshots of window size 1.

Running LPA on all snapshots;

curl -X POST 127.0.0.1:8081/RangeAnalysisRequest \
-H "Content-Type: application/json" \
--data-binary @- << EOF 
{
	"jsonrpc":"2.0",
	"jobID":"lpaExample1",
	"analyserName":"com.raphtory.core.analysis.Algorithms.LPA",
	"start":1,
	"end":3,
	"jump":1,
	"windowType":"true",
	"windowSize": 1
}
EOF

This returns:

{"time":1,"windowsize":0,"top5":[4],"total":1,"totalIslands":0,"communities": [[1,2,6,5]],"proportion":1.0, "viewTime":36}
{"time":2,"windowsize":0,"top5":[4,2],"total":2,"totalIslands":0,"communities": [[4,3,1,2],[6,5]],"proportion":0.6666667, "viewTime":29}
{"time":3,"windowsize":0,"top5":[3,3],"total":2,"totalIslands":0,"communities": [[5,6,7],[4,1,3]],"proportion":0.5, "viewTime":33}

Running LPA on the aggregated graph;

curl -X POST 127.0.0.1:8081/ViewAnalysisRequest \
-H "Content-Type: application/json" \
--data-binary @- << EOF 
{
	"jsonrpc":"2.0",
	"jobID":"lpaExample2",
	"analyserName":"com.raphtory.core.analysis.Algorithms.LPA",
	"timestamp":3
}
EOF

This returns:

{"time":3,"top5":[4,3],"total":2,"totalIslands":0,"proportion":0.5714286, "communities":[[4,3,2,1],[6,7,5]],"viewTime":30}

Specifying that only the largest community be returned (as specified by top_c)

curl -X POST 127.0.0.1:8081/ViewAnalysisRequest \
-H "Content-Type: application/json" \
--data-binary @- << EOF 
{
	"jsonrpc":"2.0",
	"jobID":"lpaExample3",
	"analyserName":"com.raphtory.core.analysis.Algorithms.LPA",
	"timestamp":3,
	"args":["1"]
}
EOF

This returns:

{"time":3,"top5":[4,3],"total":2,"totalIslands":0,"proportion":0.5714286, "communities":[[3,2,1,4]],"viewTime":33}

References

^{[1] Li, S., Lou, H., Jiang, W., & Tang, J. (2015). Detecting community structure via synchronous label propagation. Neurocomputing, 151, 1063-1075.}