highlyConnSG
Compute highly connected subgraphs for an undirected graph
Compute highly connected subgraphs for an undirected graph
 Keywords
 models
Usage
highlyConnSG(g, sat=3, ldv=c(3,2,1))
Arguments
 g
 an instance of the
graph
class withedgemode
“undirected”  sat
 singleton adoption threshold, positive integer
 ldv
 heuristics to remove lower degree vertice, a decreasing sequence of positive integer
Details
A graph G with n vertices is highly connected if its connectivity k(G) > n/2. The HCS algorithm partitions a given graph into a set of highly connected subgraphs, by using minimumcut algorithm recursively. To improve performance, the approach is refined by adopting singletons, removing low degree vertices and merging clusters.
On singleton adoption: after each round of partition, some highly connected subgraphs could be singletons (i.e., a subgraph contains only one node). To reduce the number of singletons, therefore reduce number of clusters, we try to get "normal" subgraphs to "adopt" them. If a singleton, s, has n neighbours in a highly connected subgraph c, and n > sat, we add s to c. To adapt to the modified subgraphs, this adoption process is repeated until no further such adoption.
On lower degree vertices: when the graph has low degree vertices, minimumcut algorithm will just repeatedly separate these vertices from the rest. To reduce such expensive and noninformative computation, we "remove" these low degree vertices first before applying minimumcut algorithm. Given ldv = (d1, d2, ..., dp), (d[i] > d[i+1] > 0), we repeat the following (i from 1 to p): remove all the highlyconnectedsubgraph found so far; remove vertices with degrees < di; find highlyconnectedsubgraphs; perform singleton adoptions.
The Boost implementation does not support selfloops, therefore we
signal an error and suggest that users remove selfloops using the
function removeSelfLoops
function. This change does affect
degree, but the original article makes no specific reference to selfloops.
Value

A list of clusters, each is given as vertices in the graph.
References
A Clustering Algorithm based on Graph Connectivity by E. Hartuv, R. Shamir, 1999.
See Also
Examples
con < file(system.file("XML/hcs.gxl",package="RBGL"))
coex < fromGXL(con)
close(con)
highlyConnSG(coex)