<!DOCTYPE html> <html> <head> <meta http-equiv='content-type' value='text/html;charset=utf8'> <meta name='generator' value='Ronn/v0.7.3 (http://github.com/rtomayko/ronn/tree/0.7.3)'> <title>label_prop(1) - Find communities using label propagation</title> <style type='text/css' media='all'> /* style: man */ body#manpage {margin:0} .mp {max-width:100ex;padding:0 9ex 1ex 4ex} .mp p,.mp pre,.mp ul,.mp ol,.mp dl {margin:0 0 20px 0} .mp h2 {margin:10px 0 0 0} .mp > p,.mp > pre,.mp > ul,.mp > ol,.mp > dl {margin-left:8ex} .mp h3 {margin:0 0 0 4ex} .mp dt {margin:0;clear:left} .mp dt.flush {float:left;width:8ex} .mp dd {margin:0 0 0 9ex} .mp h1,.mp h2,.mp h3,.mp h4 {clear:left} .mp pre {margin-bottom:20px} .mp pre+h2,.mp pre+h3 {margin-top:22px} .mp h2+pre,.mp h3+pre {margin-top:5px} .mp img {display:block;margin:auto} .mp h1.man-title {display:none} .mp,.mp code,.mp pre,.mp tt,.mp kbd,.mp samp,.mp h3,.mp h4 {font-family:monospace;font-size:14px;line-height:1.42857142857143} .mp h2 {font-size:16px;line-height:1.25} .mp h1 {font-size:20px;line-height:2} .mp {text-align:justify;background:#fff} .mp,.mp code,.mp pre,.mp pre code,.mp tt,.mp kbd,.mp samp {color:#131211} .mp h1,.mp h2,.mp h3,.mp h4 {color:#030201} .mp u {text-decoration:underline} .mp code,.mp strong,.mp b {font-weight:bold;color:#131211} .mp em,.mp var {font-style:italic;color:#232221;text-decoration:none} .mp a,.mp a:link,.mp a:hover,.mp a code,.mp a pre,.mp a tt,.mp a kbd,.mp a samp {color:#0000ff} .mp b.man-ref {font-weight:normal;color:#434241} .mp pre {padding:0 4ex} .mp pre code {font-weight:normal;color:#434241} .mp h2+pre,h3+pre {padding-left:0} ol.man-decor,ol.man-decor li {margin:3px 0 10px 0;padding:0;float:left;width:33%;list-style-type:none;text-transform:uppercase;color:#999;letter-spacing:1px} ol.man-decor {width:100%} ol.man-decor li.tl {text-align:left} ol.man-decor li.tc {text-align:center;letter-spacing:4px} ol.man-decor li.tr {text-align:right;float:right} </style> <style type='text/css' media='all'> /* style: toc */ .man-navigation {display:block !important;position:fixed;top:0;left:113ex;height:100%;width:100%;padding:48px 0 0 0;border-left:1px solid #dbdbdb;background:#eee} .man-navigation a,.man-navigation a:hover,.man-navigation a:link,.man-navigation a:visited {display:block;margin:0;padding:5px 2px 5px 30px;color:#999;text-decoration:none} .man-navigation a:hover {color:#111;text-decoration:underline} </style> </head> <!-- The following styles are deprecated and will be removed at some point: div#man, div#man ol.man, div#man ol.head, div#man ol.man. The .man-page, .man-decor, .man-head, .man-foot, .man-title, and .man-navigation should be used instead. --> <body id='manpage'> <div class='mp' id='man'> <div class='man-navigation' style='display:none'> <a href="#NAME">NAME</a> <a href="#SYNOPSIS">SYNOPSIS</a> <a href="#DESCRIPTION">DESCRIPTION</a> <a href="#PARAMETERS">PARAMETERS</a> <a href="#OUTPUT">OUTPUT</a> <a href="#EXAMPLES">EXAMPLES</a> <a href="#SEE-ALSO">SEE ALSO</a> <a href="#REFERENCES">REFERENCES</a> <a href="#AUTHORS">AUTHORS</a> </div> <ol class='man-decor man-head man head'> <li class='tl'>label_prop(1)</li> <li class='tc'>www.complex-networks.net</li> <li class='tr'>label_prop(1)</li> </ol> <h2 id="NAME">NAME</h2> <p class="man-name"> <code>label_prop</code> - <span class="man-whatis">Find communities using label propagation</span> </p> <h2 id="SYNOPSIS">SYNOPSIS</h2> <p><code>label_prop</code> [SYNC|ASYNC] <var>graph_in</var> [<var>max_epochs</var>]</p> <h2 id="DESCRIPTION">DESCRIPTION</h2> <p><code>label_prop</code> finds the communities in <var>graph_in</var> 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 graphs.</p> <h2 id="PARAMETERS">PARAMETERS</h2> <dl> <dt><code>SYNC</code>|<code>ASYNC</code></dt><dd><p> The first parameter is used to choose between synchronous (<code>SYNC</code>) or asynchronous (<code>ASYNC</code>) label update.</p></dd> <dt><var>graph_in</var></dt><dd><p> undirected input graph (edge list). If is equal to <code>-</code> (dash), read the edge list from STDIN.</p></dd> <dt><var>max_epochs</var></dt><dd><p> Sets the maximum number of epochs to run (optional).</p></dd> </dl> <h2 id="OUTPUT">OUTPUT</h2> <p>The program prints on STDOUT the partition obtained where no more label flips are possible, in the format:</p> <pre><code> ## nc: NUM_COMM Q_max: Q_MAX Epochs: EPOCHS node_1 comm_1 node_2 comm_2 node_3 comm_3 ... </code></pre> <p>where <code>comm_i</code> is the community to which <code>node_i</code> belongs. The first output line reports the number of communities <code>NUM_COMM</code>, the corresponding value of modularity <code>Q_MAX</code>, and the number of epochs <code>EPOCHS</code> used to find the partition.</p> <p>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:</p> <pre><code> 1 Q_1 flips_1 2 Q_2 flips_2 3 Q_3 flips_3 .... </code></pre> <p>where <code>Q_i</code> is the modularity of the partition at the i-th epoch, and <code>flips_i</code> is the number of label flips performed during that epoch.</p> <h2 id="EXAMPLES">EXAMPLES</h2> <p>We can use <code>label_prop</code> to find communities in the graph <code>karate_club_unweighted.net</code> (Zachary Karate Club network) with the command:</p> <pre><code> $ 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 $ </code></pre> <p>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 <code>karate_label-prop_trace</code>.</p> <h2 id="SEE-ALSO">SEE ALSO</h2> <p><span class="man-ref">modularity<span class="s">(1)</span></span>, <span class="man-ref">gn<span class="s">(1)</span></span>, <span class="man-ref">cnm<span class="s">(1)</span></span></p> <h2 id="REFERENCES">REFERENCES</h2> <ul> <li><p>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.</p></li> <li><p>V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Appendix 19, Cambridge University Press (2017)</p></li> <li><p>V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Chapter 9, Cambridge University Press (2017)</p></li> </ul> <h2 id="AUTHORS">AUTHORS</h2> <p>(c) Vincenzo 'KatolaZ' Nicosia 2009-2017 <code><v.nicosia@qmul.ac.uk></code>.</p> <ol class='man-decor man-foot man foot'> <li class='tl'>www.complex-networks.net</li> <li class='tc'>September 2017</li> <li class='tr'>label_prop(1)</li> </ol> </div> </body> </html>