The random-graphs tag has no wiki summary.
2
votes
1answer
41 views
Mean number of edges between two equal partitions
For a random undirected graph with $n$ nodes, where each node has $k$ incident edges ($nk/2$ edges in total), the vertex set is partitioned into two sets each having $n/2$ nodes.
What is the ...
2
votes
1answer
102 views
What is the probability of friendship conditioned on the number of mutual friends
Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends?
I am ...
9
votes
1answer
153 views
Number of clique in random graphs
There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of ...
