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.

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

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