I'm starting to study random graphs (I read a few things about Erdös-Rényi model here).
What are the most useful variables to describe the topology of a random graph?
I guess:
$$\alpha = \text{average (over all nodes) of the number of edges from a given node}$$
$$\beta = \text{standard deviation (over all nodes) of the number of edges from a given node}$$
$$\gamma = \text{average (over all pairs of nodes) of shortest distance between two nodes}$$
are useful, what are the typical quantitative metrics that we use to distinguish, say:
x_1 -- x_2 -- ... -- x_N (just a long chain) from a dense graph with many links between nodes,
or which quantitative indicators an measure the presence or absence of "clusters"?
Two fundamental notions along these lines are the vertex connectivity and the edge connectivity of $G$, which tell us how many vertices or edges respectively need to be deleted to disconnect $G$.
A fancier answer is the Cheeger constant/isoperimetric number of the graph. To find it, we minimize $$ \frac{e(S, V(G) \setminus S)}{|S|} $$ over all subsets $S \subseteq V(G)$ with $|S| \le \frac12|V(G)|$, where $e(A,B)$ denotes the number of edges between vertices in $A$ and vertices in $B$. The idea is that the set $S$ minimizing this ratio is a cluster in the graph: it's a relatively large set of vertices with few edges leaving it.
Of course, computing this quantity requires checking lots of subsets $S$ (and computing the connectivity of a graph is hard, too), and there's a more algebraic approach: the algebraic connectivity of the graph $G$. This is the second-smallest eigenvalue of the Laplacian matrix of $G$. (The smallest eigenvalue is always $0$, corresponding to the all-$1$'s eigenvector.)
This is related to the isoperimetric number by an inequality: the isoperimetric number is at least half the algebraic connectivity. A rough idea of the connection between the two is that the indicator vector of the set $S$ is a good approximation of an eigenvector of the Laplacian matrix with a small eigenvalue. The algebraic connectivity is also at most the vertex connectivity.