3 ms·

For someone unfamiliar with power laws and scale in networks, that introduction has me totally bamboozled with multiple repeating negatives. A scale-free netwo

For someone unfamiliar with power laws and scale in networks, that introduction has me totally bamboozled with multiple repeating negatives. A scale-free network is one that follows power laws, which manifests as having specific hubs that are much more interconnected than others. A random network does not follow power laws. Hubs and edges are distributed relatively evenly. Is that right?

hammock 9y ago
Scale-free: distribution of connections follows power law across hubs. Other type: it doesnt
- esrauch 9y ago
  But "it doesn't" can include things that are both distrubuted with fatter or thinner tails? And if it is normally distrubuted below some range, and then power law above that it also wouldn't be scale free under this paper?
  - marcosdumay 9y ago
    For the first question, yes. "Not power law" means anything else. But I am quite confused on what you mean with power laws "above" or "below" some range.
    - esrauch 9y ago
      It seems that the reason power laws are important is the frequency of arbitrarily large values, and the implications those have on data processing. Under a definition that strict it doesn't sound useful: imagine the most common degree / # of connections is 10 and 5 is less popular: isn't that already not a power law? Regardless of how the distribution behaves for degree 100, 1000, etc. It seems like under many models you have some unimportant distribution of low-degree connections and then close to a power law distribution if you consider above some threshold: in terms of algorithm selection and design under those conditions the dominating factor seems like it can typically still be just the frequency of large degrees which can still be close to a power law and rejected as one by this paper, right?
      - hammock 9y ago
        Yeah , I sort of agree that practically power laws are pretty useful, even if they are approximators. I think the paper is trying to say though, the same people (including myself) who use power law to generate these models often say that these processes are actually power law processes. When in fact they may not be. Which is surprising to me (Zipfs law and all of that)
oakridge 9y ago
The article is a bit vague on these so I'll take a stab: Random network are generated randomly, i.e. drawn from some distribution. An example would be the Erdos-Renyi (ER) network, where edges are drawn from a Bernoulli distribution between each node in the network. The simplest way to measure random networks is to determine the degree distribution. ER networks hence result to degree distributions that follow the Binomial distribution (Poisson as N->infty, Np->const). Since the edge probabilities are rather simple and drawn independently, one can take the ER network as sort of a "null model" of random networks. Scale-free networks, on the other hand, do not follow this degree distribution. Rather, they follow a power-law distribution p(k) ~ x^-a. A process to explain this is that the network is generated by preferential attachment: nodes are more likely to be connected to nodes which are highly connected in the first place. Most of the discussion and the following arguments on this are in the article.

hammock 9y ago

Scale-free: distribution of connections follows power law across hubs. Other type: it doesnt

esrauch 9y ago
But "it doesn't" can include things that are both distrubuted with fatter or thinner tails? And if it is normally distrubuted below some range, and then power law above that it also wouldn't be scale free under this paper?
- marcosdumay 9y ago
  For the first question, yes. "Not power law" means anything else. But I am quite confused on what you mean with power laws "above" or "below" some range.
  - esrauch 9y ago
    It seems that the reason power laws are important is the frequency of arbitrarily large values, and the implications those have on data processing. Under a definition that strict it doesn't sound useful: imagine the most common degree / # of connections is 10 and 5 is less popular: isn't that already not a power law? Regardless of how the distribution behaves for degree 100, 1000, etc. It seems like under many models you have some unimportant distribution of low-degree connections and then close to a power law distribution if you consider above some threshold: in terms of algorithm selection and design under those conditions the dominating factor seems like it can typically still be just the frequency of large degrees which can still be close to a power law and rejected as one by this paper, right?
    - hammock 9y ago
      Yeah , I sort of agree that practically power laws are pretty useful, even if they are approximators. I think the paper is trying to say though, the same people (including myself) who use power law to generate these models often say that these processes are actually power law processes. When in fact they may not be. Which is surprising to me (Zipfs law and all of that)

oakridge 9y ago

The article is a bit vague on these so I'll take a stab: Random network are generated randomly, i.e. drawn from some distribution. An example would be the Erdos-Renyi (ER) network, where edges are drawn from a Bernoulli distribution between each node in the network. The simplest way to measure random networks is to determine the degree distribution. ER networks hence result to degree distributions that follow the Binomial distribution (Poisson as N->infty, Np->const). Since the edge probabilities are rather simple and drawn independently, one can take the ER network as sort of a "null model" of random networks. Scale-free networks, on the other hand, do not follow this degree distribution. Rather, they follow a power-law distribution p(k) ~ x^-a. A process to explain this is that the network is generated by preferential attachment: nodes are more likely to be connected to nodes which are highly connected in the first place. Most of the discussion and the following arguments on this are in the article.