2
$\begingroup$

I would like to know when an ER graph is locally treeing like. In this post. I found this comment:

I think $N$ is $\log2|V|$, or something like that, in that paper. They consider binary vectors of length $N$. Furthermore, "most" sparse graphs have logarithmic diameter (say, random regular graphs of constant degree $d\geq3$, or the giant component of Erdos-Rényi random graphs with $p=\frac{c}{n}$ and $c>1$ a constant), rather than linear.

Where can I found this result about ER graphs?

Improve this question
$\endgroup$
3
  • $\begingroup$ Did you look into any book on random graphs? $\endgroup$ Commented Oct 13, 2016 at 14:18
  • 1
    $\begingroup$ @BorisBukh I'm reading: van der Hofstad. Random Graphs and Complex Networks, 2016. win.tue.nl/~rhofstad/NotesRGCN.html. And I haven't found it. $\endgroup$ Commented Oct 13, 2016 at 15:56
  • 4
    $\begingroup$ I was not familiar with the book, and I concede the point: that book does analyze the giant component in a way from which it is impossible to extract the bound on the diameter. (Since it analyzes the complement of the giant component). Have a look at Theorem 10.19 in Bollobas's book on random graphs. It should also be contained in Janson-Luczak-Rucinski, but I do not have it handy. $\endgroup$ Commented Oct 13, 2016 at 17:35

1 Answer 1

Reset to default
1
$\begingroup$

it has to do with the clustering coefficient.

See the bottom of page 5 here:

https://aaronclauset.github.io/courses/3352/csci3352_2021_L3.pdf

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.