Welcome to the Label Propagation Algorithm page.
Here you can see illustrated operation of
some published label propagation algorithms for various graphs we have preloaded, and those that you can load in
also a fixed size display box of height 800 pixels (width is based on your browser width)
is used which also limits the size of networks to try.
You need a modern browser, for example Internet Explorer v9 or newer, or later versions of Chrome or FireFox
to use this site.
Please send corrections and suggestions to:
info atsign opcoast dot com
First, select a graph, or load one in PAJEK format in the Graph Selection box.
When you use the button
"Show PAJEK Loader" a text area comes up where you can load you own PAJEK formatted data. The
text area is initially shown with the text for a small graph, you can find graphs at:
Network Data Repository, note
that we need to use undirected graphs. The reader only considers Vertices and Edges.
Next, select an algorithm to try from the combobox. Each of the algorithms
may encounter ties in assigning a new label (community) to a node -- if the "Randomize Ties" checkbox
is off, then the method chooses based on the first one that is tied for best. If "Randomize Ties" is on
then ties are broken randomly using the stream of random numbers as seeded.
Next, select the update style. The Asynchronous option will cause the node
labels to be updated as each node is considered. That is the label of a node changes during the algorithm
operation. The order of these is from first to last (from the Pajek file), unless the "Randomize Update Order"
is checked, in which case a stream of random numbers as seeded is used to define the order.
This ordering changes in each iteration as the random stream for this purpose is reused.
If the option
Synchronous is chosen, the node labels are fixed until all the nodes are considered, and then all of
them are updated accordingly. You will note that this can cause more oscillatory action than the
Finally, use the "Forward" button to advance the algorithm by one step. The
"Forward & Gather" button will move the algorithm one step and issue the gather function on
the graph which collects communities together visually.
If at any time, the "Reset" button is used or any changes are made to settings, the
graph will reset to its initial state. Note that the initial state shows the graph without labels (communities)
and the first step after this is actually the initialization, which puts each node into its own community.
The community labels are shown above the node.
At any time, you can click on the "Gather by Commuity" button and the graph will be redrawn attempting
to group nodes in the same community together -- also note that after the initialization that color
coding of the node is used to indicate labeling (community membership). The position of each node is
'jittered' a bit to aid in seeing connections, that is to hopefully ease overlapping edges that would
occur for linearly placed nodes.
Note that the random number streams are independent for each of the tie breaking,
graph creation or update ordering to allow for repeatable usage. It uses
for this purpose. Seeds can be any text string, they are not restricted to numbers.
X. Liu, T. Murata, "Advanced modularity-specialized label propagation algorithm
for detecting communities in networks," Physica A: Statistical Mechanics and its Applications,
Volume 389, Issue 7, 1 April 2010, Pages 1493-150
Usha Nandini Raghavan, Reka Albert, Soundar Kumara,
"Near linear time algorithm to detect community structures in large-scale networks,"
Physical Review E 76, 036106 (2007)
M. E. J. Newman, M. Girvan, "Finding and evaluating community structure in networks,"
Phys. Rev. E 69, 026113 (2004)
D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, S. M.
Dawson, "The bottlenose dolphin community of Doubtful Sound features
a large proportion of long-lasting associations," Behavioral Ecology and Sociobiology 54 (2003) pp 396-405.
M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002)
W. W. Zachary, "An information flow model for conflict and fission in small groups,"
Journal of Anthropological Research 33, 452-473 (1977).
On December 10, 2016 this code was updated to correct a problem in seeding the
tie-breaking random number generator, due to input from Charalampos Lemonitsakis - many thanks.
Before, the tie breaking seed was based on the checkbox value and not the provided seed,
now the seed value is used correctly.
Select a Graph:Creating larger, high density graphs may cause script runtime warnings/freezes