1 | /* $Id$Revision: */ |
2 | /* vim:set shiftwidth=4 ts=8: */ |
3 | |
4 | /************************************************************************* |
5 | * Copyright (c) 2011 AT&T Intellectual Property |
6 | * All rights reserved. This program and the accompanying materials |
7 | * are made available under the terms of the Eclipse Public License v1.0 |
8 | * which accompanies this distribution, and is available at |
9 | * http://www.eclipse.org/legal/epl-v10.html |
10 | * |
11 | * Contributors: See CVS logs. Details at http://www.graphviz.org/ |
12 | *************************************************************************/ |
13 | |
14 | #ifndef MG_H |
15 | #define MG_H |
16 | |
17 | typedef struct Multilevel_MQ_Clustering_struct *Multilevel_MQ_Clustering; |
18 | |
19 | struct Multilevel_MQ_Clustering_struct { |
20 | int level;/* 0, 1, ... */ |
21 | int n; |
22 | SparseMatrix A; /* n x n matrix */ |
23 | SparseMatrix P; |
24 | SparseMatrix R; |
25 | Multilevel_MQ_Clustering next; |
26 | Multilevel_MQ_Clustering prev; |
27 | int delete_top_level_A; |
28 | int *matching; /* dimension n. matching[i] is the clustering assignment of node i */ |
29 | |
30 | /* |
31 | |
32 | . |E(i,i)| |E(i,j)| |
33 | MQ/2 = (1/k) * \sum_{i=1...k} ------------ - (1/(k*(k-1))) * \sum_{i<j} ------------------- |
34 | . |V(i)|^2 |V(i)|*|V(j)| |
35 | . = mq_in/k - mq_out/(k*(k-1)) |
36 | */ |
37 | |
38 | real mq; |
39 | real mq_in, mq_out;/* mqs(A) = deg_in(A)/|A|^2 - deg_out(A)/|A|/(|V|-|A|) */ |
40 | int ncluster; /* number of clusters */ |
41 | |
42 | real *deg_intra;/* dimension n. deg[i] equal to the sum of edge weights within cluster i */ |
43 | real *dout;/* dimension n, dout[i] = \sum_{j -- i} a(i,j)/|j| is the scaled sum of outdegree */ |
44 | real *wgt; /* total vertex weight each coarse grid vertex represent */ |
45 | }; |
46 | |
47 | /* find a clustering of vertices by maximize modularity quality |
48 | A: symmetric square matrix n x n. If real value, value will be used as edges weights, otherwise edge weights are considered as 1. |
49 | inplace: whether A can e modified. If true, A will be modified by removing diagonal. |
50 | |
51 | maxcluster: used to specify the maximum number of cluster desired, e.g., maxcluster=10 means that a maximum of 10 clusters |
52 | . is desired. this may not always be realized, and modularity quality may be low when this is specified. Default: maxcluster = 0 (no limit) |
53 | |
54 | use_value: whether to use the entry value, or treat edge weights as 1. |
55 | nclusters: on output the number of clusters |
56 | assignment: dimension n. Node i is assigned to cluster "assignment[i]". 0 <= assignment < nclusters. |
57 | . If *assignment = NULL on entry, it will be allocated. Otherwise used. |
58 | mq: achieve modularity |
59 | */ |
60 | void mq_clustering(SparseMatrix A, int inplace, int maxcluster, int use_value, |
61 | int *nclusters, int **assignment, real *mq, int *flag); |
62 | |
63 | #endif |
64 | |