@graphty/algorithms / index / indexed / girvanNewman
Function: girvanNewman() ​
girvanNewman(
s,options?):GirvanNewmanResult
Defined in: indexed/girvan-newman.ts:85
Girvan-Newman divisive community detection (PNAS 99:7821, 2002) over an undirected snapshot: repeatedly delete every edge whose betweenness is the maximum (within 1e-10), recording the connected components after each round as one level of a dendrogram.
Edges are deleted by clearing bits of an alive mask over logical edges that the edge betweenness reads, so no graph is rebuilt. Betweenness is unweighted, as in the legacy function; a pair of nodes joined by parallel edges is one neighbour relation whose share goes to the first alive parallel, so the parallels are deleted one round at a time. Modularity reads the edge weights, the exact f64 ones when the snapshot keeps them, with graph-format's weightedDegree() rule (a self-loop counts twice); on a graph without self-loops it equals the legacy function's.
The run stops when no edge is left, after maxIterations rounds, when a level has maxCommunities communities of at least minCommunitySize nodes, or when that count reaches the node count. Every level is returned whole: the legacy function drops communities below minCommunitySize from the lists it returns, which a caller does with levels[i] and a size count.
Parameters ​
s ​
GraphSnapshot
An undirected snapshot
options? ​
GirvanNewmanOptions = {}
Stopping rules
Returns ​
The levels and their modularity
Throws ​
Error on a directed snapshot