lpa

Introduction

Let the label of each node represnts the community the the node belongs in, LPA considers that the label of each node should be the same as the label that is shared by the majority of its neighbors. LPA propagates the labels by assigning label that accounts for the most of a node's neighbors to the node until convergence. At the end of LPA, nodes that are with the same label forms one community.

Parameters

use --help param to view detailed help information.

Input Format

Input files should be formatted as follows:

<src>,<dst>

where <src> and <dst> are integers of type uint32_t, representing the end nodes of an edge. Note that Plato treats every input graph as undirected by default. For a directed graph, please ensure both <A, B> and <B, A> appear in the input file if they exist. Edges that appear more than once will be considered as multiple edges between the same pair of nodes.

Input example (Following numbers are synthetic and are for demonstration purpose only.)：

4564,823192
1996,973033

Output Format

Output files are formatted as follows：

<vertex_id>,<cluster_id>

where <vertex_id> represents a node and <cluster_id> gives the id of the cluster that contains the node. Note that cluster ids may not start from 1 or be consecutive as some clusters are merged into bigger clusters hence their ids are ommited.

Output example (Following numbers are synthetic and are for demonstration purpose only.)：

66720,827192
99086,639730

Code

https://github.com/Tencent/plato/tree/master/plato/algo/lpa