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

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

ConnectedGraphQ test whether a graph is connected

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

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

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

New to Mathematica? Find your learning path »
Have a question? Ask support »