diff options
Diffstat (limited to 'doc/gn.1')
| -rw-r--r-- | doc/gn.1 | 110 |
1 files changed, 110 insertions, 0 deletions
diff --git a/doc/gn.1 b/doc/gn.1 new file mode 100644 index 0000000..cf112c5 --- /dev/null +++ b/doc/gn.1 @@ -0,0 +1,110 @@ +.\" generated with Ronn/v0.7.3 +.\" http://github.com/rtomayko/ronn/tree/0.7.3 +. +.TH "GN" "1" "September 2017" "www.complex-networks.net" "www.complex-networks.net" +. +.SH "NAME" +\fBgn\fR \- Find communities using the Girvan\-Newman algorithm +. +.SH "SYNOPSIS" +\fBgn\fR \fIgraph_in\fR +. +.SH "DESCRIPTION" +\fBgn\fR finds the communities in \fIgraph_in\fR 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 +\fBN\.B\.\fR: 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\. +. +.SH "PARAMETERS" +. +.TP +\fIgraph_in\fR +undirected input graph (edge list)\. If is equal to \fB\-\fR (dash), read the edge list from STDIN\. +. +.SH "OUTPUT" +The program prints on STDOUT the partition corresponding to the highest value of modularity, in the format: +. +.IP "" 4 +. +.nf + + ## nc: NUM_COMM Q_max: Q_MAX + node_1 comm_1 + node_2 comm_2 + node_3 comm_3 + \.\.\. +. +.fi +. +.IP "" 0 +. +.P +where \fBcomm_i\fR is the community to which \fBnode_i\fR belongs\. The first output line reports the number of communities \fBNUM_COMM\fR and the corresponding value of modularity \fBQ_MAX\fR of the partition\. +. +.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: +. +.IP "" 4 +. +.nf + + nc_1 Q_1 + nc_2 Q_2 + nc_3 Q_3 + \.\.\.\. +. +.fi +. +.IP "" 0 +. +.P +where \fBnc_i\fR is the number of communities after the i\-th edge has been removed and \fBQ_i\fR is the corresponding value of modularity\. +. +.SH "EXAMPLES" +We can use \fBgn\fR to find communities in the graph \fBkarate_club_unweighted\.txt\fR (Zachary Karate Club network) with the command: +. +.IP "" 4 +. +.nf + + $ 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 + $ +. +.fi +. +.IP "" 0 +. +.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 \fBkarate_gn_trace\fR\. +. +.SH "SEE ALSO" +modularity(1), cnm(1), label_prop(1) +. +.SH "REFERENCES" +. +.IP "\(bu" 4 +M\. Girvan and M\. E\. J\. Newman\. "Community structure in social and biological networks"\. P\. Natl\. Acad\. Sci\. USA 99 (2002), 7821\-\-7826\. +. +.IP "\(bu" 4 +V\. Latora, V\. Nicosia, G\. Russo, "Complex Networks: Principles, Methods and Applications", Appendix 17, Cambridge University Press (2017) +. +.IP "\(bu" 4 +V\. Latora, V\. Nicosia, G\. Russo, "Complex Networks: Principles, Methods and Applications", Chapter 9, Cambridge University Press (2017) +. +.IP "" 0 +. +.SH "AUTHORS" +(c) Vincenzo \'KatolaZ\' Nicosia 2009\-2017 \fB<v\.nicosia@qmul\.ac\.uk>\fR\. |