I'm looking for a way to measure how interconnected a graph is.  It's well known that graphs can be broken down into connected components.  It seems, though, that even in the cases where the graph is made of only one connected component, we can measure how interconnected that component is.  Is it almost two components (if we would remove a small number of edges)? What is the correlation between edges (that is, if vertices A and B are each connected to C, is there a higher probability that A and B are themselves connected).  I don't know how to define this measure properly, but I'm sure there are existing measures already defined.It would seem to me that this would be a great way to measure the difficulty of an instance of the SAT problem.  Representing variables as nodes and being in the same clause as edges, it would seem the difficulty of the problem is related to the interconnectedness of the graph.
Measuring the connectedness of a graph, and applying it to NP problems
cc.complexity theory;graph theory;sat
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).