1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 | import * as util from '../../util';
|
8 |
|
9 |
|
10 | let defaults = util.defaults({
|
11 | expandFactor: 2,
|
12 | inflateFactor: 2,
|
13 | multFactor: 1,
|
14 | maxIterations: 20,
|
15 | attributes: [
|
16 | function(edge) {
|
17 | return 1;
|
18 | }
|
19 | ]
|
20 | });
|
21 |
|
22 |
|
23 | let setOptions = ( options ) => defaults( options );
|
24 |
|
25 |
|
26 | if( process.env.NODE_ENV !== 'production' ){
|
27 | var printMatrix = function( M ) {
|
28 | let n = Math.sqrt(M.length);
|
29 | for ( let i = 0; i < n; i++ ) {
|
30 | let row = '';
|
31 | for ( let j = 0; j < n; j++ ) {
|
32 | row += Number(M[i*n+j]).toFixed(3) + ' ';
|
33 | }
|
34 | console.log(row);
|
35 | }
|
36 | console.log('');
|
37 | };
|
38 | }
|
39 |
|
40 |
|
41 | let getSimilarity = function( edge, attributes ) {
|
42 | let total = 0;
|
43 | for ( let i = 0; i < attributes.length; i++ ) {
|
44 | total += attributes[i]( edge );
|
45 | }
|
46 | return total;
|
47 | };
|
48 |
|
49 | let addLoops = function( M, n, val ) {
|
50 | for (let i = 0; i < n; i++) {
|
51 | M[i * n + i] = val;
|
52 | }
|
53 | };
|
54 |
|
55 | let normalize = function( M, n ) {
|
56 | let sum;
|
57 | for ( let col = 0; col < n; col++ ) {
|
58 | sum = 0;
|
59 | for ( let row = 0; row < n; row++ ) {
|
60 | sum += M[row * n + col];
|
61 | }
|
62 | for ( let row = 0; row < n; row++ ) {
|
63 | M[row * n + col] = M[row * n + col] / sum;
|
64 | }
|
65 | }
|
66 | };
|
67 |
|
68 |
|
69 | let mmult = function( A, B, n ) {
|
70 | let C = new Array( n * n );
|
71 |
|
72 | for ( let i = 0; i < n; i++ ) {
|
73 | for ( let j = 0; j < n; j++ ) {
|
74 | C[i * n + j] = 0;
|
75 | }
|
76 |
|
77 | for ( let k = 0; k < n; k++ ) {
|
78 | for ( let j = 0; j < n; j++ ) {
|
79 | C[i * n + j] += A[i * n + k] * B[k * n + j];
|
80 | }
|
81 | }
|
82 | }
|
83 | return C;
|
84 | };
|
85 |
|
86 | let expand = function( M, n, expandFactor /** power **/ ) {
|
87 | let _M = M.slice(0);
|
88 |
|
89 | for ( let p = 1; p < expandFactor; p++ ) {
|
90 | M = mmult( M, _M, n );
|
91 | }
|
92 | return M;
|
93 | };
|
94 |
|
95 | let inflate = function( M, n, inflateFactor /** r **/ ) {
|
96 | let _M = new Array( n * n );
|
97 |
|
98 |
|
99 | for ( let i = 0; i < n * n; i++ ) {
|
100 | _M[i] = Math.pow( M[i], inflateFactor );
|
101 | }
|
102 |
|
103 | normalize( _M, n );
|
104 |
|
105 | return _M;
|
106 | };
|
107 |
|
108 | let hasConverged = function( M, _M, n2, roundFactor ) {
|
109 |
|
110 | for ( let i = 0; i < n2; i++ ) {
|
111 | let v1 = Math.round( M[i] * Math.pow(10, roundFactor) ) / Math.pow(10, roundFactor);
|
112 | let v2 = Math.round( _M[i] * Math.pow(10, roundFactor) ) / Math.pow(10, roundFactor);
|
113 |
|
114 | if ( v1 !== v2 ) {
|
115 | return false;
|
116 | }
|
117 | }
|
118 | return true;
|
119 | };
|
120 |
|
121 | let assign = function( M, n, nodes, cy ) {
|
122 | let clusters = [];
|
123 |
|
124 | for ( let i = 0; i < n; i++ ) {
|
125 | let cluster = [];
|
126 | for ( let j = 0; j < n; j++ ) {
|
127 |
|
128 | if ( Math.round( M[i * n + j] * 1000 ) / 1000 > 0 ) {
|
129 | cluster.push( nodes[j] );
|
130 | }
|
131 | }
|
132 | if ( cluster.length !== 0 ) {
|
133 | clusters.push( cy.collection(cluster) );
|
134 | }
|
135 | }
|
136 | return clusters;
|
137 | };
|
138 |
|
139 | let isDuplicate = function( c1, c2 ) {
|
140 | for (let i = 0; i < c1.length; i++) {
|
141 | if (!c2[i] || c1[i].id() !== c2[i].id()) {
|
142 | return false;
|
143 | }
|
144 | }
|
145 | return true;
|
146 | };
|
147 |
|
148 | let removeDuplicates = function( clusters ) {
|
149 |
|
150 | for (let i = 0; i < clusters.length; i++) {
|
151 | for (let j = 0; j < clusters.length; j++) {
|
152 | if (i != j && isDuplicate(clusters[i], clusters[j])) {
|
153 | clusters.splice(j, 1);
|
154 | }
|
155 | }
|
156 | }
|
157 | return clusters;
|
158 | };
|
159 |
|
160 | let markovClustering = function( options ) {
|
161 | let nodes = this.nodes();
|
162 | let edges = this.edges();
|
163 | let cy = this.cy();
|
164 |
|
165 |
|
166 | let opts = setOptions( options );
|
167 |
|
168 |
|
169 | let id2position = {};
|
170 | for( let i = 0; i < nodes.length; i++ ){
|
171 | id2position[ nodes[i].id() ] = i;
|
172 | }
|
173 |
|
174 |
|
175 | let n = nodes.length, n2 = n * n;
|
176 | let M = new Array( n2 ), _M;
|
177 | for ( let i = 0; i < n2; i++ ) {
|
178 | M[i] = 0;
|
179 | }
|
180 |
|
181 | for ( let e = 0; e < edges.length; e++ ) {
|
182 | let edge = edges[e];
|
183 | let i = id2position[ edge.source().id() ];
|
184 | let j = id2position[ edge.target().id() ];
|
185 |
|
186 | let sim = getSimilarity( edge, opts.attributes );
|
187 |
|
188 | M[i * n + j] += sim;
|
189 | M[j * n + i] += sim;
|
190 | }
|
191 |
|
192 |
|
193 |
|
194 |
|
195 | addLoops( M, n, opts.multFactor );
|
196 |
|
197 |
|
198 | normalize( M, n );
|
199 |
|
200 | let isStillMoving = true;
|
201 | let iterations = 0;
|
202 | while ( isStillMoving && iterations < opts.maxIterations ) {
|
203 |
|
204 | isStillMoving = false;
|
205 |
|
206 |
|
207 | _M = expand( M, n, opts.expandFactor );
|
208 |
|
209 |
|
210 | M = inflate( _M, n, opts.inflateFactor );
|
211 |
|
212 |
|
213 | if ( ! hasConverged( M, _M, n2, 4 ) ) {
|
214 | isStillMoving = true;
|
215 | }
|
216 |
|
217 | iterations++;
|
218 | }
|
219 |
|
220 |
|
221 | let clusters = assign( M, n, nodes, cy );
|
222 |
|
223 |
|
224 | clusters = removeDuplicates( clusters );
|
225 |
|
226 | return clusters;
|
227 | };
|
228 |
|
229 | export default {
|
230 | markovClustering,
|
231 | mcl: markovClustering
|
232 | };
|