Power Laws

Sparseness, clustering and small diameter are not the only distinctive properties of large real-world graphs. The degree sequence — the number of vertices with each possible number of edges from 0 to n — 1 — is also important. You know the degree sequence of a lattice is simple. All vertices have the same number of edges, so plotting the degree sequence for all the vertices forms a single sharp spike. Any randomness in the graph broadens this peak. In the limiting case of an entirely random graph, the degree sequence forms a Poisson distribution, falling off exponentially away from the peak value on both sides. Now the probability of finding a vertex with k edges grows negligibly small for large k because of the exponential decline.

Real graphs such as the World Wide Web graph behave differently. A power law describes the distribution of degrees and not an exponential. That is, the number of vertices of degree k is given not by e—k (an exponential) but by k—g (a power law, where the power g is a positive constant). The power-law distribution slopes away more gradually than would an exponential. It is this drop off that permits highly connected vertices of very large degree. We discuss graphs of a closed and an open circulation in their respective chapters.

0 0

Post a comment