Measuring the connectedness of a graph, and applying it to NP problems
A standard measure of "interconnectedness" is how expanding the graph is. There are several ways to define expansion that are all related. The algebraic way is by measuring the second largest eigenvalue (in absolute value) of the adjacency matrix. The largest eigenvalue is a graph in which all vertices have degree D is always D. If the second largest eigenvalue is much smaller than D, then every two sets of vertices in the graph have roughly as many edges between them as if the edges were chosen at random (this is the expanding mixing lemma).
For more info about graph expansion, see this course:
http://www.math.ias.edu/~boaz/ExpanderCourse/

If the graph is an expander, the entire graph is one big, very interconnected, component.
This is the case with random SAT instances that are believed to be hard (for the appropriate clauses ratio).