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
198
199
200
201
|
<!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>gn(1) - Find communities using the Girvan-Newman algorithm</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'>gn(1)</li>
<li class='tc'>www.complex-networks.net</li>
<li class='tr'>gn(1)</li>
</ol>
<h2 id="NAME">NAME</h2>
<p class="man-name">
<code>gn</code> - <span class="man-whatis">Find communities using the Girvan-Newman algorithm</span>
</p>
<h2 id="SYNOPSIS">SYNOPSIS</h2>
<p><code>gn</code> <var>graph_in</var></p>
<h2 id="DESCRIPTION">DESCRIPTION</h2>
<p><code>gn</code> finds the communities in <var>graph_in</var> using the Girvan-Newman
algorithm, based on the successive removal of edges with high
betweenness. The program prints on STDOUT the partition corresponding
to the highest value of the modularity function, and reports on STDERR
the number of communities after each edge removal and the
corresponding value of modularity.</p>
<p><code>N.B.</code>: the program recomputes the edge betweenness of the graph after
the removal of each edge, so it is not feasible to use it on large
graphs.</p>
<h2 id="PARAMETERS">PARAMETERS</h2>
<dl>
<dt><var>graph_in</var></dt><dd> undirected input graph (edge list). If is equal to <code>-</code> (dash), read
the edge list from STDIN.</dd>
</dl>
<h2 id="OUTPUT">OUTPUT</h2>
<p>The program prints on STDOUT the partition corresponding to the
highest value of modularity, in the format:</p>
<pre><code> ## nc: NUM_COMM Q_max: Q_MAX
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> and the
corresponding value of modularity <code>Q_MAX</code> of the partition.</p>
<p>The program prints on STDERR the number of communities (connected
components) after the removal of each edge, and the corresponding
value of modularity, in the format:</p>
<pre><code> nc_1 Q_1
nc_2 Q_2
nc_3 Q_3
....
</code></pre>
<p>where <code>nc_i</code> is the number of communities after the i-th edge has been
removed and <code>Q_i</code> is the corresponding value of modularity.</p>
<h2 id="EXAMPLES">EXAMPLES</h2>
<p>We can use <code>gn</code> to find communities in the graph <code>karate_club_unweighted.txt</code>
(Zachary Karate Club network) with the command:</p>
<pre><code> $ gn karate_club_unweighted.net 2> karate_gn_trace
### nc: 4 Q_max: 0.365631
0 1
1 1
2 2
3 1
4 3
5 3
6 3
...
30 2
31 2
32 2
33 2
$
</code></pre>
<p>In this run, the command has found a partition with 4 communities
corrisponding to a modularity Q=0.365631. Notice that node 0, 1, 3,
are in community 1, node 2 is in community 2, node 4,5,6, are in
community 3 and so forth. In general, different runs will provide
different partitions, since any tie in betweenness values is broke by
choosing one of the edges with equal betweenness uniformly at
random. In this example, we have chosen to save the information about
number of communities and modularity after each edge removal in the
file <code>karate_gn_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">cnm<span class="s">(1)</span></span>, <span class="man-ref">label_prop<span class="s">(1)</span></span></p>
<h2 id="REFERENCES">REFERENCES</h2>
<ul>
<li><p>M. Girvan and M. E. J. Newman. "Community structure in social and
biological networks". P. Natl. Acad. Sci. USA 99 (2002), 7821--7826.</p></li>
<li><p>V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles,
Methods and Applications", Appendix 17, 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'>gn(1)</li>
</ol>
</div>
</body>
</html>
|
