Hi ! [slide 21]
While following the lecture, I did not get why the threshold function is defined that way.
Does the Coupon Collector problem give an insight of why it is this particular value log(n)/n ?
It probably does but I did not manage to find the link.
The idea is that the coupon collector problem tells us the average number of edges in a graph of n nodes such that every node in the graph has at least a degree of 1.
A bin represents a node and a bin having a ball means that at least one node in the network flipped a coin and decided to draw an edge to this node.
Then, in the Erdös-Rényi random graph model, the expected number of edges is n times E[degree of a node] = n^2 times p. Hence, taking the result from the coupon collector problem, p should be around log(n)/n.
Thanks for the explanation - one small correction: given that an edge has two end points (in an undirected graph), it contributes to the degrees of two nodes --> for this reason, the expected # of edges is in fact
Threshold function - slide 21
Hi ! [slide 21]
While following the lecture, I did not get why the threshold function is defined that way.
Does the Coupon Collector problem give an insight of why it is this particular value log(n)/n ?
It probably does but I did not manage to find the link.
Thanks
1
The idea is that the coupon collector problem tells us the average number of edges in a graph of n nodes such that every node in the graph has at least a degree of 1.
A bin represents a node and a bin having a ball means that at least one node in the network flipped a coin and decided to draw an edge to this node.
Then, in the Erdös-Rényi random graph model, the expected number of edges is n times E[degree of a node] = n^2 times p. Hence, taking the result from the coupon collector problem, p should be around log(n)/n.
Thanks for the explanation - one small correction: given that an edge has two end points (in an undirected graph), it contributes to the degrees of two nodes --> for this reason, the expected # of edges is in fact
\({n \choose 2}p \sim n^2 p / 2\)
1
Add comment