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.

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  ▪  ConnectedGraphComponents  ▪  WeaklyConnectedGraphComponents

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

VertexOutComponentGraph  ▪  VertexInComponentGraph

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

FindMaximumCut — find a partition of vertices that maximize the edges to cut

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