| 36 | } |
| 37 | |
| 38 | function normalizedLaplacian(affinity: Matrix): Matrix { |
| 39 | const n = affinity.rows; |
| 40 | const degrees = new Array(n); |
| 41 | for (let i = 0; i < n; i++) { |
| 42 | let sum = 0; |
| 43 | for (let j = 0; j < n; j++) { |
| 44 | if (i !== j) sum += affinity.get(i, j); |
| 45 | } |
| 46 | degrees[i] = sum; |
| 47 | } |
| 48 | |
| 49 | const data = new Array(n); |
| 50 | for (let i = 0; i < n; i++) { |
| 51 | data[i] = new Array(n); |
| 52 | for (let j = 0; j < n; j++) { |
| 53 | if (i === j) { |
| 54 | data[i][j] = 1; |
| 55 | } else { |
| 56 | const di = degrees[i]; |
| 57 | const dj = degrees[j]; |
| 58 | data[i][j] = (di > 1e-10 && dj > 1e-10) ? -affinity.get(i, j) / Math.sqrt(di * dj) : 0; |
| 59 | } |
| 60 | } |
| 61 | } |
| 62 | return new Matrix(data); |
| 63 | } |
| 64 | |
| 65 | function findOptimalK(eigenvalues: number[], maxK: number): number { |
| 66 | const sorted = [...eigenvalues].sort((a, b) => a - b); |