**NAME**
**gcfnd** - **g**reedy **c**ommunity **f**inding 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.