Detecting graph topology.

Question

I have a set of graphs and I need to classify them with respect to their topology. Is there an algorithm which can detect the topology (random, regular, scale-free, etc.) of a given undirected graph?

Answer 1

The things you are calling "topology" are a hodgepodge of different notions (especially given that it's unclear what you mean by "etc.") and there's no natural algorithm that handles all of them at once. However, many things of this flavor are easy to test for.

A graph is regular if the degree of every vertex is the same, and we can easily compute the degree sequence of a graph and check if this holds.

A graph is scale-free if its degree sequence approximately follows a power law. So we can kind of test for this property by finding the degree sequence and doing a regression. Say that $n_k$ is the number of vertices with degree $k$. Then we want $n_k \approx C k^{-\gamma}$ or $\log n_k \approx \log C - \gamma \log k$, so the $R^2$ value of a linear regression on the points $(\log n_k, \log k)$ will tell us how accurate a power law model is. We probably want to stick to a range of $k$ for which $n_k$ is decently large.

Of course, this will not give us a yes-or-no answer any longer: it will give us a value saying how close the network is to being scale-free. In that respect, this property is closer to what we have to deal with when we consider random graphs...

...where is meaningless to say that we "test a graph for being random". A specific graph can't be "random" or "not random", but we have different random graph models that can generate graphs. What we can ask is whether it's plausible that a graph we're looking at was generated by a certain model.

There are many random graph models. Off-hand, we have:

• $G(n,\frac12)$, which will be equally likely to generate any labeled graph on $n$ vertices.
• More generally, the Erdos-Renyi model $G(n,p)$, which independently decides the presence of each edge with probability $p$.
• We can generate a uniformly random $d$-regular graph.
• Many random graphs such as the Barabasi-Albert model generate a random graph with a scale-free degree distribution.

As a simple test, we can start by asking "what is the probability that random graph model $M$ generated the graph we see?" This is good at deciding between random graph models. It is less good at dealing with the alternative hypothesis "none of these models are a good fit".

We can also look at parameters of interest such as degree distribution, clustering coefficient, path lengths, and so forth, and compare them to what we'd expect from a random graph model. This is a more useful way to tell if any random graph model is a good model for our data.