NAME
     gcfnd - greedy community finding algorithm based on modularity
             maximization

INDEX
     NAME
     SYNOPSIS
     DESCRIPTION
     DOWNLOAD
     SEE ALSO
     AUTHORS

SYNOPSIS
     #include "gcfnd.h"

     void
     gcfnd(int nv, edge *elst, int ne, int *cid, int *cnb, double *Q);

DESCRIPTION
     The gcfnd() function implements a community finding greedy algorithm
     based on modularity maximization. This algorithm was proposed by Newman
     and further improved by Clauset et al.. In the current implementation
     we use different data structures and achieve an improvement of at least
     a factor of 2 both in time and space. We also implement a prioritizer
     suggested by Noack and Rotta.

     gcfnd function computes a community partition for an undirected graph
     with nv vertices and ne edges, being elst the list of edges. The edge
     type is defined in gcfnd.h as follows:

     typedef struct {
             int u;
             int v;
     } edge;

     gcfnd returns no value. It stores the number of communities in cnb, the
     maximum achieved modularity in Q and, assuming that communities are
     numbered from 0 to cnb - 1, it stores in the pre-allocated array cid of
     size nv the community for each vertex.

DOWNLOAD
     Source code is available. Files included:

     gcfnd.h         Implementation of the function gcfnd.
     gcfnd.c

     pqueue.h        Priority queue implementation based on binary heaps.
     pqueue.c

     unfnd.h         Disjoint-set data structure implementation.
     unfnd.c
     
     cfind.c         Simple application using gcfnd.
     
     Makefile        Makefile to build cfind application.

     cfind reads a graph from stdin and assumes the following format:

     <number of vertices> <number of edges>
     <edge 1 vertex 1> <edge 1 vertex 2>
     ...

     Vertices must be numbered from 0 to number of vertices minus one.
     Input example:

     7 10
     0 1
     1 2
     2 0
     2 3
     3 4
     4 5
     5 6
     6 3
     4 6
     3 5

SEE ALSO
     A. P. Francisco and A. L. Oliveira. On community detection in very
     large networks. In Complex Networks, volume 116 of CCIS, pages
     208-216. Springer, 2010. 

     A. Noack and R. Rotta. Multi-level algorithms for modularity
     clustering. In: Experimental Algorithms, volume 5526 of LNCS,
     pages 257-268. Springer, 2009.

     A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure
     in very large networks. Physical Review E, 70:066111, 2004.

     M. E. J. Newman. Fast algorithm for detecting community structure in
     networks. Physical Review E, 69:066133, 2004.

AUTHORS
     Alexandre P. Francisco and Arlindo L. Oliveira, INESC-ID and IST,
     Technical University of Lisbon.