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$
    – Boris Bukh
    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$
    – fdesmond
    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$
    – Boris Bukh
    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.

Not the answer you're looking for? Browse other questions tagged .