@graphty/algorithms / index / indexed / grsbm
Function: grsbm() ​
grsbm(
s,options?):GrsbmResult
Defined in: indexed/grsbm.ts:113
GRSBM over a snapshot: recursive spectral bisection. Each cluster's Laplacian (over the arcs between its members, self-loops left out) gives an approximate Fiedler vector; members are sorted by it and cut at the point between 20% and 80% that maximises modularity; the split is kept only when it raises the modularity of the whole partition (every other cluster held as it is). The change is the two halves' community terms minus the cluster's, so scoring a cut costs the arcs of the cluster alone. Clusters are split breadth first. The cut and the modularity arithmetic are the legacy grsbm's; the acceptance rule is not (legacy compared the two halves' terms alone with the parent split's, and kept a split that lowered that by up to 0.01, issue #960), nor is the bisection vector, because legacy's iteration converged to the eigenvector of the Laplacian's largest eigenvalue rather than the Fiedler vector. The port draws from its own generator instead of replacing Math.random.
Modularity uses weightedDegree() (a self-loop counts twice) against totalWeight(), or degree() against the edge count when unweighted. A self-loop follows the standard convention (left out of the Laplacian, twice in the degree), so on a graph with self-loops the result differs from legacy's, which scores the whole graph as one community above 0. On a directed graph the unweighted path keeps legacy's halving of internal arcs; the weighted path does not, so there the whole graph as one community scores 0. Weights must be finite and non-negative (RangeError).
Parameters ​
s ​
GraphSnapshot
The snapshot
options? ​
GrsbmOptions = {}
Returns ​
The leaf partition and the hierarchy