Let $G = (V, E)$ be an Erdős-Rényi graph, with $N = |V|$ nodes, $L = |E|$ edges. The distribution of the degree of any particular node is binomial (or Poisson under certain condition). Suppose that the average node degree is $\bar{k}$.

Fix a node $i$ in the graph with degree $k_i$. Then randomly pick another node $j$ which is in the neighborhood of $i$ (randomly = with uniform probability).

What can I say about the distribution of the degree of $j$ knowing that it is in the neighborhood of node $i$ with degree $k_i$?

  • $\begingroup$ You managed to misspell both of the names of those people :-) Note that in most languages that use diacritics, the letters with and without diacritics have only a historical connection and are pronounced quite differently nowadays. Thus leaving off the diacritics is about as bad a misspelling as changing the vowels completely; you might as well have written "Erdas-Runyi". If you can't produce letters with diacritics, you can always copy them from the Web, e.g. from the corresponding Wikipedia articles (which you can find by Googling the names without diacritics :-). $\endgroup$ – joriki Feb 14 '13 at 13:18
  • $\begingroup$ There are two different Erdős-Rényi models, one with a given number of edges and one with a given probability for independent existence of the possible edges -- which one are you talking about? $\endgroup$ – joriki Feb 14 '13 at 13:23
  • 2
    $\begingroup$ @joriki I agree that it’s a worthwhile endeavour to spell names correctly as a basic sign of respect, but… I notice you used double prime (") rather than quotation marks (“”), and a simulated en dash (--) rather than an em dash (—). I’m not criticizing these approximations (I use them all the time), just saying that it’s only human to take some shortcuts in typing. $\endgroup$ – Erick Wong Feb 14 '13 at 14:40
  • $\begingroup$ @Erick: Point taken :-) There's a difference though between adapting one's own language to computers and adapting other languages to one's own. (Also I do use proper dashes in posts, just not in comments because – doesn't work here for some reason and it doesn't seem worth copying one just for a comment. Which confirms your point about taking some shortcuts -- yet there are different levels of shortcuts, and it matters whether they are just typographical or severely affect the pronunciation of people's names.) $\endgroup$ – joriki Feb 14 '13 at 15:26
  • $\begingroup$ @joriki I'm using the model $G(N, p)$, where $N$ is the number of nodes and $p$ is the probability that an edge exists. $\endgroup$ – the_candyman Feb 15 '13 at 10:10

Your Answer

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

Browse other questions tagged or ask your own question.