communities

tcmts.share.communities · #sbnrrfh5 · function · runs anywhere

The communities of a weighted graph (Louvain): n nodes and links as [a, b, weight], either way round; each community a list of its nodes, the nodes that link to each other more than to the rest.

export function communities(n: number, links: [number, number, number][]): number[][] {
  let adj = Array.from({ length: n }, () => new Map<number, number>());
  for (const [a, b, w] of links) {
    if (a === b) continue;
    adj[a]!.set(b, (adj[a]!.get(b) ?? 0) + w);
    adj[b]!.set(a, (adj[b]!.get(a) ?? 0) + w);
  }
  let members = Array.from({ length: n }, (_, j) => [j]);
  for (let level = 0; level < 8; level++) {
    // move each node to the neighbouring community that gains the most modularity, until none moves
    const size = adj.length;
    const deg = adj.map((m) => [...m.values()].reduce((s, w) => s + w, 0));
    const total = deg.reduce((s, d) => s + d, 0) || 1;
    const of = [...Array(size).keys()];
    const tot = deg.slice();
    let moved = true;
    let any = false;
    while (moved) {
      moved = false;
      for (let v = 0; v < size; v++) {
        const from = of[v]!;
        const into = new Map<number, number>();
        for (const [u, w] of adj[v]!) if (u !== v) into.set(of[u]!, (into.get(of[u]!) ?? 0) + w);
        tot[from]! -= deg[v]!;
        let best = from;
        let gain = (into.get(from) ?? 0) - (tot[from]! * deg[v]!) / total;
        for (const [c, w] of into) {
          const g = w - (tot[c]! * deg[v]!) / total;
          if (g > gain + 1e-9) {
            gain = g;
            best = c;
          }
        }
        tot[best]! += deg[v]!;
        if (best !== from) {
          of[v] = best;
          moved = any = true;
        }
      }
    }
    if (!any) break;
    // then each community becomes a node, and again
    const ids = [...new Set(of)];
    const index = new Map(ids.map((c, j) => [c, j]));
    const next = ids.map(() => [] as number[]);
    const nextAdj = ids.map(() => new Map<number, number>());
    members.forEach((ms, v) => next[index.get(of[v]!)!]!.push(...ms));
    adj.forEach((m, v) => {
      for (const [u, w] of m) {
        const a = index.get(of[v]!)!;
        const b = index.get(of[u]!)!;
        nextAdj[a]!.set(b, (nextAdj[a]!.get(b) ?? 0) + w);
      }
    });
    members = next;
    adj = nextAdj;
  }
  return members;
}

communities

used by