What are some measures of connectedness in graphs?

I am not a mathematician (I am an engineer who is working on improving his mathematics), so I apologize in advance if my question is trivial.

Consider a graph of $N$ nodes, with some defined criterion as to whether two nodes are connected or not. What are some measures of the graph's connectedness? I can think of several such measures, but I'm not sure which ones make the most mathematical sense:

1. Whether the entire graph is connected or not. This is, however, a binary measure, and does not capture much information.
2. The size of the largest intra-connected sub graph ($0 \leq n \leq N$). This, however, tells you nothing about what's happening in the rest of the graph.
3. The number of intra-connected (but not inter-connected) sub-graphs in the graph ($0 \leq n \leq N$).
4. Each node $i\in \{1,2,\dots,N\}$ is assigned a 'score' $s_i\in\{1,2,\dots,N\}$, which measures how many other nodes it is connected to. The graphs' connectedness is then measured as the average of these scores, i.e. $\sum_i s_i / N$, such that it lies in the interval $[0,N]$.

The kind of questions I am interested in are ones like: Is 4. a mathematically sound measure? Can it give rise to anomalies? Are there better measures that are more robust?

Please forgive me if I am not rigorous enough in my explanations. As an engineer, I have been trained to think in 'intuitive' (rather than formal) terms, which can often be a huge help, but at other times a hindrance.

Solution 1:

The most common measures of connectivity are edge-connectivity and vertex-connectivity. The vertex-connectivity, or just connectivity, of a graph is the minimum number of vertices you have to remove before you can even hope to disconnect the graph. A graph is called $k$-vertex-connected, or just $k$-connected, if its connectivity is at least $k$. Edge-connectivity and $k$-edge-connected are defined similarly.

As an example, suppose we've got a tree $T$ with at least 3 vertices. In a tree, any two vertices are connected by exactly one path. In particular, removing any internal (i.e. not one of the endpoints) part of any path from $T$ disconnects the graph. Thus, $T$ has vertex- and edge-connectivity $1$. (We needed at least 3 vertices here to guarantee that we can find a path with interior vertices, though with 2 vertices we still have edge-connectivity $1$. By convention, the tree with two vertices has connectivity $1$.)

As another example, one can show (try it!) that a cycle of length greater than 3 has edge- and vertex-connectivity $2$. (As with trees, for a 3-cycle---there's no such thing as a 1- or 2-cycle---, the edge-connectivity still makes sense and is $2$, but for vertex-connectivity we have to resort to convention: we simply assign it connectivity $2$).

Solution 2:

Sometimes in math turning the question on its head leads to useful definitions. In this case we might ask how few edges are necessary to remove in order to disconnect a graph. If no single edge's removal gives a disconnected graph, we say the graph is doubly connected, etc.

There's a topic called community detection which in loose terms tries to identify vertex subsets of a graph that are more closely connected within themselves than to the other portions.

Solution 3:

The "score" you speak of in (4) is typically called the degree or valence of a node. The average degree is simply $2E/N$, where $E$ is the number of edges in the graph, because adding up the degrees of all the nodes amounts to counting all the edges twice. This is certainly a nice measure: at the smallest possible value $0$, the graph is just a bunch of nodes with no edges; at the largest possible value $N-1$, every node is connected to every other. However, while it does tell you how "dense" the graph is, it doesn't tell you anything about connectedness in the binary sense... unless the value is extremely small or extremely large. More precisely, a graph with average degree less than $2-2/N$ must be disconnected; a graph with average degree more than $N-3+2/N$ must be connected.

The Wikipedia article on connectivity of graphs mentions some other measures that I'm sure you will find interesting. I see some other answers are coming in that describe them in more detail.