3
$\begingroup$

Given a d-regular graph $G=<V,E>$ (connected, unweighted & simple), and a node $v$.

denote all nodes with distance $k$ from $v$ $$L_k=\{u\in V : dis(v,u) = k\}$$ Let's call it "the k-th layer", where the distance $dis$ is taken as the length of the minimal path.

so, for instance, $L_0 = \{v\}$ and $|L_1|=d$.

In general: What is the size of the k-th layer? specifically, what is the size of the largest layer?

Do we know the answer under any interesting assumption?

e.g.

  1. Do we know the expected answer for uniformly random d-regular graph for constant $d$ and $n\rightarrow\infty$ ?

  2. If we take $v \in V$ uniformly at random?

  3. If we take $v$ as the central node or The peripheral node?

  4. other assumptions?

$\endgroup$
3
  • $\begingroup$ We know that in random regular graph w.h.p. there are ~$log_d(n)$ layers ([Béla Bollobás, W. Fernandez de la Vega][1]), but what is the size of each layer? $\endgroup$
    – slouis
    Sep 14 '15 at 6:34
  • $\begingroup$ Random regular graphs are locally tree-like, so at least for $k$'s which are much smaller than the diameter, you have an answer. $\endgroup$
    – Bach
    Sep 14 '15 at 12:46
  • $\begingroup$ You are correct - the first layers are tree-like, but when do they are loosing this property? this leads to further interesting question: What is the critical distance where the graph is changing from 'tree-like' to 'cyclic'? $\endgroup$
    – slouis
    Sep 15 '15 at 5:12
2
$\begingroup$

The magic words are "expander graph". A random regular graph is an expander, which means that the size of the layers is expanding until half the vertices are consumed. This (more or less) answers your questions 1, 2. As for 3, I have no idea what central/peripheral node means.

$\endgroup$
2
  • $\begingroup$ It is true that it is probably an expander, and it is true that it the layers are expanding - but note that (as Bach wrote in the comment on the question), the first layers are tree-like, but the large layers are totally not tree-like: there are many cycles in the big layers! In Simulations I ran the biggest layers have almost the same size and there are only 'few' edges in between the layers, which means that the 'expanding' property fades away in the most significant interesting layers! What is the size of those largest layer? Can you please detail the 'more or less'? $\endgroup$
    – slouis
    Sep 15 '15 at 5:09
  • $\begingroup$ by 'central node' I meant - a vertex that achieves the radius of the graph. By 'peripheral node' I meant for the vertex that achieves the diameter of the graph. $\endgroup$
    – slouis
    Sep 15 '15 at 7:46
0
$\begingroup$

This question is actually equivalent to the distribution of shortest path lengths in random graphs - Mor Nitzan, Eytan Katzav, Reimer Kühn, and Ofer Biham, Distance distribution in configuration-model networks, Phys. Rev. E 93, 062309 (2016).

In the case of random regular graphs there is an exact result, which is a Gompertz distribution. The tail distribution is given by

$$P(L> \ell) = \exp \left[ - \eta \left( e^{b \ell} - 1 \right) \right]$$

with $\eta=\frac{c}{(c-2)(N-1)}$ and $b=\ln(c-1)$

and where $c$ is the degree of all nodes (a random regular graph)

You can get the probability mass function via

$$P(L=\ell) = P(L > \ell - 1) - P(L > \ell)$$

and the expected number of nodes in each shell is simply $N \times P(L=\ell)$

Hope this helps

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.