35 grid->delete_top_level_A =
false;
38 grid->agglomerate_regardless =
false;
41 double modularity = 0;
42 int *ia =
A->ia, *ja =
A->ja;
44 double *deg, *a =
A->a;
50 double *indeg =
gv_calloc(n,
sizeof(
double));
51 for (i = 0; i < n; i++){
54 for (j = ia[i]; j < ia[i+1]; j++){
56 if (ja[j] == i) indeg[i] = a[j];
60 deg_total = fmax(deg_total, 1);
61 for (i = 0; i < n; i++){
62 modularity += (indeg[i] - deg[i]*deg[i]/deg_total)/deg_total;
64 grid->deg_total = deg_total;
66 grid->modularity = modularity;
77 if (
grid->level == 0) {
94 int n =
grid->
n, level =
grid->level, nc = 0;
95 double modularity = 0;
96 int *ia =
A->ia, *ja =
A->ja;
97 double *deg =
grid->deg;
98 int i, j, jj, jc, jmax;
99 double inv_deg_total = 1./
grid->deg_total;
102 double total_gain = 0;
103 modularity =
grid->modularity;
105 double *deg_new =
gv_calloc(n,
sizeof(
double));
106 double *deg_inter =
gv_calloc(n,
sizeof(
double));
108 for (i = 0; i < n; i++) mask[i] = -1;
111 for (i = 0; i < n; i++) matching[i] =
UNMATCHED;
117 for (i = 0; i < n; i++){
120 for (j = ia[i]; j < ia[i+1]; j++){
122 if (jj == i)
continue;
126 deg_inter[jc] = a[j];
128 deg_inter[jc] += a[j];
135 for (j = ia[i]; j < ia[i+1]; j++){
137 if (jj == i)
continue;
140 gain = (2*a[j] - 2*deg[i]*deg[jj]*inv_deg_total)*inv_deg_total;
142 if (deg_inter[jc] > 0){
144 gain = (2*deg_inter[jc] - 2*deg[i]*deg_new[jc]*inv_deg_total)*inv_deg_total;
151 if (jmax < 0 || gain > maxgain){
159 if (maxgain > 0 ||
grid->agglomerate_regardless){
160 total_gain += maxgain;
164 matching[i] = matching[jmax] = nc;
165 deg_new[nc] = deg[i] + deg[jmax];
169 deg_new[jc] += deg[i];
173 assert(maxgain <= 0);
175 deg_new[nc] = deg[i];
181 if (
Verbose) fprintf(stderr,
"modularity = %f new modularity = %f level = %d, n = %d, nc = %d, gain = %g\n", modularity, modularity + total_gain,
182 level, n, nc, total_gain);
184 if (ncluster_target > 0){
185 if (nc <= ncluster_target && n >= ncluster_target){
186 if (n - ncluster_target > ncluster_target - nc){
188 }
else if (n - ncluster_target <= ncluster_target - nc){
189 fprintf(stderr,
"ncluster_target = %d, close to n=%d\n", ncluster_target, n);
190 for (i = 0; i < n; i++) matching[i] = i;
194 }
else if (n < ncluster_target){
195 fprintf(stderr,
"n < target\n");
196 for (i = 0; i < n; i++) matching[i] = i;
202 if (nc >= 1 && (total_gain > 0 || nc < n)){
209 for (i = 0; i < n; i++){
231 cgrid->
deg = deg_new;
239 if (ncluster_target > 0 && nc > ncluster_target && !(
grid->agglomerate_regardless)){
247 for (i = 0; i < n; i++) matching[i] = i;
276 if (
A != A0)
grid->delete_top_level_A =
true;
282 int *nclusters,
int **assignment,
double *modularity){
301 assert(
A->m ==
A->n);
314 double *u =
gv_calloc(cgrid->
n,
sizeof(
double));
315 for (i = 0; i < cgrid->
n; i++) u[i] = (
double) (cgrid->
matching)[i];
316 *nclusters = cgrid->
n;
329 matching = *assignment;
332 *assignment = matching;
334 for (i = 0; i <
grid->n; i++) (matching)[i] = (int) u[i];
343 int *nclusters,
int **assignment,
double *modularity){
359 assert(
A->m ==
A->n);
363 if (!inplace &&
B ==
A) {
SparseMatrix SparseMatrix_from_coordinate_format(SparseMatrix A)
SparseMatrix SparseMatrix_transpose(SparseMatrix A)
SparseMatrix SparseMatrix_symmetrize(SparseMatrix A, bool pattern_symmetric_only)
SparseMatrix SparseMatrix_coordinate_form_add_entry(SparseMatrix A, int irn, int jcn, const void *val)
bool SparseMatrix_is_symmetric(SparseMatrix A, bool test_pattern_symmetry_only)
void SparseMatrix_multiply_vector(SparseMatrix A, double *v, double **res)
SparseMatrix SparseMatrix_multiply(SparseMatrix A, SparseMatrix B)
void SparseMatrix_delete(SparseMatrix A)
SparseMatrix SparseMatrix_copy(SparseMatrix A)
SparseMatrix SparseMatrix_set_entries_to_real_one(SparseMatrix A)
SparseMatrix SparseMatrix_get_real_adjacency_matrix_symmetrized(SparseMatrix A)
SparseMatrix SparseMatrix_remove_diagonal(SparseMatrix A)
SparseMatrix SparseMatrix_new(int m, int n, int nz, int type, int format)
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
static Multilevel_Modularity_Clustering Multilevel_Modularity_Clustering_establish(Multilevel_Modularity_Clustering grid, int ncluster_target)
void modularity_clustering(SparseMatrix A, bool inplace, int ncluster_target, int *nclusters, int **assignment, double *modularity)
static Multilevel_Modularity_Clustering Multilevel_Modularity_Clustering_new(SparseMatrix A0, int ncluster_target)
static Multilevel_Modularity_Clustering Multilevel_Modularity_Clustering_init(SparseMatrix A, int level)
static void hierachical_modularity_clustering(SparseMatrix A, int ncluster_target, int *nclusters, int **assignment, double *modularity)
static void Multilevel_Modularity_Clustering_delete(Multilevel_Modularity_Clustering grid)
Multilevel_Modularity_Clustering prev
bool agglomerate_regardless
Multilevel_Modularity_Clustering next