Graph Components and Connectivity

A graph may not be fully connected. For instance, only about 25% of the web graph is estimated to be in the largest strongly connected component. Another 25% is estimated to be in the in-component and 25% in the out-component of the strongly connected core. The remaining 25% is made up of smaller isolated components. For social graphs, one is often interested in -core components that indicate groups of people that are connected in a limited way.

ReferenceReference

Connected Components

ConnectedComponents give groups of vertices that are strongly connected

WeaklyConnectedComponents give groups of vertices that are weakly connected

KCoreComponents give groups of vertices that are connected to at least others

ConnectedGraphQ  ▪  WeaklyConnectedGraphQ

Vertex Components

VertexComponent give the component for a set of vertices

VertexOutComponent give the out-component for a set of vertices

VertexInComponent give the in-component for a set of vertices

Vertex Connectivity

FindVertexCut find a minimal set of vertices that, if cut, makes the graph disconnected

VertexConnectivity minimal number of vertices to cut to disconnect the given graph

KVertexConnectedComponents give the k-vertex connected components

KVertexConnectedGraphQ test whether a graph is k-vertex connected

Edge Connectivity

FindEdgeCut find a minimal set of edges that, if cut, makes the graph disconnected

EdgeConnectivity minimal number of edges to cut to disconnect the given graph

KEdgeConnectedComponents give the k-edge connected components

KEdgeConnectedGraphQ test whether a graph is k-edge connected

Cuts and Partitions

FindMinimumCut find a partition of vertices that minimize the edges to cut

FindGraphPartition find a balanced partition of vertices that minimizes the edges to cut