/**
* This program is free software: you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
* published by the Free Software Foundation, either version 3 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see
* .
*
* (c) Vincenzo Nicosia 2009-2017 --
*
* This file is part of NetBunch, a package for complex network
* analysis and modelling. For more information please visit:
*
* http://www.complex-networks.net/
*
* If you use this software, please add a reference to
*
* V. Latora, V. Nicosia, G. Russo
* "Complex Networks: Principles, Methods and Applications"
* Cambridge University Press (2017)
* ISBN: 9781107103184
*
***********************************************************************
*
* Take a graph and a partition, and compute the modularity function
* associated to that partition.
*
* References:
*
* [1] M. E. J. Newman and M. Girvan. "Finding and evaluating
* community structure in networks". Phys. Rev. E 69, (2004),
* 026113.
*
*/
#include
#include
#include
#include
#include "utils.h"
void usage(char *argv[]){
printf("********************************************************************\n"
"** **\n"
"** -*- modularity -*- **\n"
"** **\n"
"** Compute the modularity function associated to a partition **\n"
"** of the nodes of the graph provided as input. **\n"
"** **\n"
"** If 'graph_in' is equal to '-' (dash), read the edge list **\n"
"** from standard input (STDIN). The parameter 'partition' MUST **\n"
"** be a file in the format: **\n"
"** **\n"
"** node_0 community_0 **\n"
"** node_1 community_1 **\n"
"** node_2 community_2 **\n"
"** ..... **\n"
"** **\n"
"** where 'node_0', 'node_1', etc. are node labels, and **\n"
"** 'community_0', 'community_1', etc. is the label of the **\n"
"** community to which a node belongs. Notice that a node can **\n"
"** belong to exactly one community. This format is compatible **\n"
"** with the output of the programs which compute community **\n"
"** partitions, such as `gn`, `cnm`, `label_prop`, etc. **\n"
"** **\n"
"** The program prints on STDOUT the modularity of the partition, **\n"
"** and prints on STDERR a single line in the format: **\n"
"** **\n"
"** ## nc: NUM_COMMUNITIES **\n"
"** **\n"
"** where 'NUM_COMMUNITIES' is the number of communities in the **\n"
"** partition given as input. **\n"
"** **\n"
"********************************************************************\n"
" This is Free Software - You can use and distribute it under \n"
" the terms of the GNU General Public License, version 3 or later\n\n"
" Please visit http://www.complex-networks.net for more information\n\n"
" (c) Vincenzo Nicosia 2009-2017 (v.nicosia@qmul.ac.uk)\n"
"********************************************************************\n\n"
);
printf("Usage: %s \n", argv[0]);
}
/* This is the function that computes the value of the modularity function */
double compute_modularity(unsigned int *J_slap, unsigned int *r_slap, unsigned int N,
unsigned int *part, unsigned int nc){
static double *e, *a;
unsigned int i, j, n, K, deg_i;
unsigned int ci, cj;
double Q;
if(!e)
e = malloc((N+1) * sizeof(double));
if(!a)
a = malloc((N+1) * sizeof(double));
memset(e, 0, (N+1) * sizeof(double));
memset(a, 0, (N+1) * sizeof(double));
K = r_slap[N];
for (i=0; i