1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
<!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><a class="man-ref" href="modularity.1.html">modularity<span class="s">(1)</span></a>, <a class="man-ref" href="gn.1.html">gn<span class="s">(1)</span></a>, <a class="man-ref" href="cnm.1.html">cnm<span class="s">(1)</span></a></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>
|
