Graph diameter versus maximum node degree
Since I have had amazing luck in the past with questions to the readers of this blog, I have another question.
The diameter of a graph is the longest distance between any two nodes. The degree of a node is the number of edges or links from and to this node.
Intuitively, the higher the node degrees, the denser the graph. If you have n nodes and the maximal degree of the nodes is n-1, then the graph diameter is 1. If you have lesser maximal degrees, then you can get an infinite diameter by producing a disconnected graph.
An interesting question (to me) is:
Given a maximal node degree, and a number of nodes n, what is the smallest possible diameter?
I am sure this is textbook material, but I could not find the answer quickly. Using a hyper-rectangle, I am able to construct a graph having n nodes and log n diameter. Simply start with a 4-node rectangular graph: you have 4 nodes and a diameter of 2. Move to a 8-node cubic graph: you have 8 nodes and a diameter of 3. Generalizing this construction, you have 2d nodes and a diameter of d. Is this the best you can do?
Anyhow. Why do I care about the answer? Because I keep reading that hubs are necessary in graphs to ensure that we have a small diameter. I am trying to quantify this statement. There are about 233 human beings. By my construction above, if everyone knows 33 people, then it is possible to get a diameter of 33. It seems like a relatively large diameter.
An obvious technique to shrink the diameter without using hubs, is to increase the maximal node degree. I am wondering by how much I need to increase the maximal node degree so that I can a 6 degree of separation between any two human beings.
(Yes, I know that social networks are not homogeneous. But stay with me. Assume they were.)
You might find http://en.wikipedia.org/wiki/Moore_graph relevant — it gives an upper bound for n in terms of degree and diameter (equivalently a lower bound for diameter in terms of degree and n) due to Hoffman and Singleton (1960), that is unfortunately tight only in a small number of cases.
Comment by D. Eppstein — 6/5/2008 @ 10:33
do you want specific numbers or asymptotics ? it’s fairly clear that if the max degree is any constant, the diameter can’t be less than log n, just by an expansion argument.
Comment by Suresh — 6/5/2008 @ 12:21
Suresh: I was hoping for a precise result.
Comment by Daniel Lemire — 6/5/2008 @ 12:37
suresh did give a precise result
let v be number of nodes
let b be max degree
we want min diameter d so
b^d >= v
gives us that
d = log(v,b)
Comment by Don — 7/7/2008 @ 3:12
Don: that is a bound, not an exact result.
Comment by Daniel Lemire — 7/7/2008 @ 7:20
Exact result depends on whether n is a nice number relative to m. If it is, and the following is an integer:
2 * ( log[base m] ( (n / 2 -1 ) / m ) + 1 )
you have your exact result.
idea - spread the points on a ball and no two points can be more than 1/2 ball away. The diameter is 1/2 the ball. The integer stuff is like trying to cover a ball with different polygons. Triangles, pentigons and hexigons work perfectly. Other polygons will leave weird gaps. Still we can mash our ball to force it to fit since the points do not have to be perfectly symetrical.
We can cover 1/2 the ball with a tree and the other half with an identical tree. Hence the 2 log (n/2). The point we pick as root is special since it can have an extra child. This gives the 2 log ((n/2-1)/m)+1.
Some care must be taken to join the two halves but they can be connected in such a way that any point is indistinguishable from root when the ball is turned (the even distribution).
If the formula comes out to not be an integer my belief is the result is to add one and round but I cannot fully justify this claim.
Under .5 and the extra points can be distributed on 1/2 of the ball adding at most one to the diameter. And .5 or more suggest points must be distributed on both halves of the ball potentially adding 2 to the diameter.
Anyway the problem interest me because I am currently seeking other applications of the diameter. I think it can be used for genome sequencing during the contig scaffolding phase but I am finding other applications and no literature beyond use as a metric.
Comment by Don — 8/7/2008 @ 1:35