Consider a network of $N$ nodes with no self loops described by the adjacency matrix $A \in \{0, 1\}^{N \times N}.$ Let's define as $$\deg(v) = \sum_{w=1}^N a_{v,w}$$ the degree of node $v$. Let's assume that $\deg{v} \geq 1$ for all $v$. Suppose that the distribution of degrees is known, i.e.:

$$\mathbb{P}(\deg(v) = k) = p_k,$$

for $k \in \{1, \ldots, N-1\}$. Suppose now that:

  1. We randomly extract a node $v$ from the network;
  2. We randomly extract a node $w$ from the neighbourhood of $v$ (i.e. $\{w : a_{v,w} = 1\}$).

How can I calculate

$$\mathbb{P}(\deg(w) = k_w |\deg(v) = k_v)$$

knowing just $p_k$?

Addendum 1 I'm particularly interested into finding this conditional distribution for scale free (preferential attachment) and Erdos-Renyi graphs.

  • $\begingroup$ Knowing the distribution of degrees you essentially want to deduce the distribution of degrees for pairs of neighbors. That won't work. $\endgroup$ – Michal Adamaszek Sep 29 '18 at 18:56
  • $\begingroup$ @MichalAdamaszek thanks, this is what my intuition is suggesting to me. Anyway, how can I have a formal reasoning instead of an intuition? $\endgroup$ – the_candyman Sep 29 '18 at 19:03
  • 1
    $\begingroup$ You can imagine a bipartite graph where all vertices on the left have even and all on the right have odd degrees. Then the conditional probability you are asking for is very biased, but just knowing the degree distribution doesn't tell you that. $\endgroup$ – Michal Adamaszek Sep 29 '18 at 19:08
  • $\begingroup$ @MichalAdamaszek this is an interesting picture. However, is it really wrong to assume that $\mathbb{P}(\deg(w) = k_w |\deg(v) = k_v) = p_k$? In the average, and for large graph, this could work well, no? $\endgroup$ – the_candyman Sep 29 '18 at 19:11
  • $\begingroup$ I suppose you have to know the random model which generates your graphs. $\endgroup$ – Michal Adamaszek Sep 29 '18 at 19:15

This is used a lot in research related to epidemic spreading on networks in SIS models. To calculate this, you need to know the joint degree distribution which is usually denoted by $e(k,k')$ which gives the probability that an edge chosen uniformly at random has nodes with degrees $k,k'$ at its ends. Then, the quantity you are interested in is exactly $\frac{e(k,k')}{q(k')}$ where $q(k')$ is the marginal of the joint distribution $e(\cdot,\cdot)$. For more information, have a look at:

-- Epidemic spreading in complex networks with degree correlations (Marian Boguna, Romualdo Pastor-Satorras, Alessandro Vespignani)

-- The "majority illusion" in social networks (K Lerman, X Yan, XZ Wu)

Hope this helps.

  • $\begingroup$ +1 This is a good starting point. Thanks. $\endgroup$ – the_candyman Oct 25 '18 at 16:03
  • $\begingroup$ Glad it helps. Also, if the network has no degree correlations (e.g. randomly connected edges), the conditional is the same as $q(k')$. $\endgroup$ – Ben Oct 25 '18 at 16:12

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.