2
$\begingroup$

In order to generate scale-free networks, we can use this algorithm, derived from Barabási–Albert model:

1) we assign every node a "weight" $\theta_i$ (or two in the direct case).

2) we place $m$ edges between nodes by choosing the ends of the edges with probabilities proportional to the weights.

With the right choice of the coefficients $\{\theta\}$ we can generate a graph with the desired power-law distribution. A very popular method is the so-called Chung-Lu Model and it's, for example, used in the power.law.game function in the igraph library. This model prescribes to number the nodes from 1 to N and then assign to each node a $\theta_i = i^{-\alpha}$, with $\alpha \in [0,1)$, then select nodes as the ends of an edge with probability $p_{ij} \propto \theta_i \theta_j$, and repeating for all the edges to put in. The resulting graph will have a degree distribution $p(k) \propto k^{-\gamma}$, with $\gamma = \frac{\alpha}{\alpha +1}$.

My question is: why can't we simply consider a power-law distribution with a finite extent $p(x) = \frac{1-\gamma}{x_{max}^{1-\gamma} - x_{min}^{1-\gamma}} x^{-\gamma}$, then sample our $\theta_i$ from this distribution? This is more intuitive from my perspective, because if my expected degrees follow a power-law distribution, I expect that the graph degree distribution follows the same power-law.

$\endgroup$
  • $\begingroup$ Maybe the question is more appropriate for math stack Exchange? ShouldI copy paste this post? $\endgroup$ – Francesco Di Lauro Sep 30 '17 at 8:26
1
$\begingroup$

I don't know if my solution is correct, but after some searching, I eventually came up to this conclusion:

The algorithm that is used to build the graph is not compatible with a different choice other than $\theta_i = i^{-\alpha}$.

This is because the algo is derived from the Barabási–Albert with some modifies. We start with N nodes, and we add a link between a couple of nodes every time step until we have added $mN$ edges. First we normalized the weights so they will be the probability that we choose the node $i, \;$ $\sum_{i=1}^{N} i^{-\alpha} \sim \frac{1-\alpha}{N^{1-\alpha}}$. We can easily compute the rate at which the node acquires links, since it will be proportional to its degree: \begin{equation} \frac{d\,k_i}{dt} = \frac{k_i}{2mN} = \frac{1-\alpha}{N^{1-\alpha} i^\alpha}, \end{equation} this means that we will select the node $i$ with probability $p(i) = k_i ^{-\frac{1}{\alpha}}$. This is equal to the probability that a node has a degree $k>k_i$, so it is related to the cumulative probability distribution: \begin{equation} P(k>\bar{k}) \sim k^{-\frac{1}{\alpha}} \rightarrow p(k) \sim k^{-\frac{1}{\alpha} -1} \equiv k^{-\gamma}, \end{equation} where $\gamma = \frac{1+\alpha}{\alpha}$. Is this a good answer?

$\endgroup$

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.