- 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.
- 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.