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 PAJEK format. Note that the execution is via Javascript on your computer, so network sizes should not be too large, 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 Asynchronous option.
- 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 David Bau’s JavaScript random number generator v2.3.1 for this purpose. Seeds can be any text string, they are not restricted to numbers.
References
- 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).
Update
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.