Given a graph, what is the degree distribution of the same?

Is degree distribution the same as a histogram of the degrees? As in, is the degree distribution a plot of the number of nodes that have a particular degree?

Secondly, is there a probability component to degree distribution?

Thanks in advance!

  • 1
    $\begingroup$ The degree distribution $P(k)$ of a network is then defined to be the fraction of nodes in the network with degree $k$. Thus if there are $n$ nodes in total in a network and $n_k$ of them have degree $k$, we have $P(k) = n_k/n$. en.wikipedia.org/wiki/Degree_distribution $\endgroup$ – hhsaffar Dec 12 '13 at 15:48
  • $\begingroup$ @hhsaffar So it is essentially just the fraction of nodes having a degree k. Similar to a histogram? $\endgroup$ – Pravesh Parekh Dec 13 '13 at 10:18

The degree distribution of a nonempty finite graph $G$ with vertex set $V(G)$ is the measure $\mu$ on $\mathbb N_0$ defined by $\mu(\{n\})=\#\{x\in V(G)\mid\deg_G(x)=n\}/\#V(G)$ for every $n$ in $\mathbb N_0$.

In words, the degree distribution assigns to each nonnegative integer a weight equal to the proportion of vertices whose degree is this integer. Likewise, for every property blabla, the blabla distribution assigns to each set of values of blabla a weight equal to the proportion of vertices whose blabla is in this set.

If $G$ is a random graph, that is, if $G$ is a random variable defined on some probability space $(\Omega,\mathfrak F,P)$ with values in the space of nonempty finite graphs suitably endowed with a sigma-algebra, then $\mu$ defined as before becomes a random distribution on $\mathbb N_0$, defined by $$\mu(\omega)(\{n\})=\#\{x\in V(G(\omega))\mid\deg_{G(\omega)}(x)=n\}/\#V(G(\omega)), $$ for every $n$ in $\mathbb N_0$.

  • $\begingroup$ Thanks for the answer. I know I sound naive but I am not a mathematician. Could you perhaps put it in simpler words? Thanks again! $\endgroup$ – Pravesh Parekh Dec 12 '13 at 15:37
  • 1
    $\begingroup$ Could you perhaps mention which words are not simple enough to be understood by you, not a mathematician? $\endgroup$ – Did Dec 12 '13 at 15:39
  • 1
    $\begingroup$ @PraveshParekh Suppose you want to know what fraction of the nodes in the graph has a degree equal to $n$. $\mu(n)$ gives you the ratio $\endgroup$ – hhsaffar Dec 12 '13 at 15:44
  • $\begingroup$ @Did Pardon my naivety but I was wondering if you could explain the answer in words. Understanding it in symbols is a little complex. Thanks. $\endgroup$ – Pravesh Parekh Dec 18 '13 at 7:03
  • $\begingroup$ So, "in simpler words" actually meant "with no maths symbols"? See Edit. $\endgroup$ – Did Dec 18 '13 at 9:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.