label_prop - Find communities using label propagation
label_prop [SYNC|ASYNC] graph_in [max_epochs]
label_prop finds the communities in graph_in using the label
propagation algorithm proposed by Raghavan, Albert, and Kumara. The
program prints on STDOUT the partition obtained where no more label
flips are possible, and reports on STDERR the number of communities
and the corresponding value of modularity at each epoch. When used in
ASYNC mode, the algorithm is suitable to find communities in large
The first parameter is used to choose between synchronous (
or asynchronous (
ASYNC) label update.
undirected input graph (edge list). If is equal to
- (dash), read
the edge list from STDIN.
Sets the maximum number of epochs to run (optional).
The program prints on STDOUT the partition obtained where no more label flips are possible, in the format:
## nc: NUM_COMM Q_max: Q_MAX Epochs: EPOCHS node_1 comm_1 node_2 comm_2 node_3 comm_3 ...
comm_i is the community to which
node_i belongs. The first
output line reports the number of communities
corresponding value of modularity
Q_MAX, and the number of epochs
EPOCHS used to find the partition.
The program prints on STDERR the epoch number, the value of modularity of the partition at that epoch, and the number of flips made in that epoch, in the format:
1 Q_1 flips_1 2 Q_2 flips_2 3 Q_3 flips_3 ....
Q_i is the modularity of the partition at the i-th epoch, and
flips_i is the number of label flips performed during that
We can use
label_prop to find communities in the graph
karate_club_unweighted.net (Zachary Karate Club network) with the command:
$ label_prop ASYNC karate_club_unweighted.net 2> karate_label-prop_trace ### nc: 2 Q_max: 0.371795 Epochs: 6 0 0 1 0 2 0 3 0 ... 30 1 31 1 32 1 33 1 $
The program has found a partition with 2 communities corrisponding to
a modularity Q=0.371795. Notice that node 0, 1, 2, 3, are in community
0, while node 30, 31, 32, 33 are in community 1. In this example, we
have chosen to save the information about the modularity and number of
flips at each epoch in the file
U. N. Raghavan, R. Albert, and S. Kumara. "Near linear time algorithm to detect community structures in large-scale networks". Phys. Rev. E 76 (2007), 036106.
V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Appendix 19, Cambridge University Press (2017)
V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Chapter 9, Cambridge University Press (2017)
(c) Vincenzo 'KatolaZ' Nicosia 2009-2017