0
$\begingroup$

I've read that networks can be:

  • random (Erdős–Rényi model),

  • scale-free (Albert–Barabási model),

  • small-world (Watts–Strogatz model).

But can a real world network be “two-scale”, in the sense that its degree distribution only consists of two different degrees, for example $(5,5,5,5,4,4,4,...)$ where the number nodes of degree $4$ is equal to $9$?

$\endgroup$
  • $\begingroup$ Real world, no. But for a random network as you wish, yes, simply adapt the usual construction starting with half-edges attached to each vertex. $\endgroup$ – Did Aug 28 '18 at 5:57
  • $\begingroup$ It can't be real world because it doesn't have a power law degree distribution? Would the degree distribution for a "two scale" network just be a line segment with negative slope? $\endgroup$ – Ultradark Aug 28 '18 at 13:17
  • $\begingroup$ It can't be real world because it doesn't have a power law degree distribution? – Many real networks do not have such a distribution and it is still up to debate to what extents observations of such distributions in real networks are a measurement artefact. The models you list are just that: models. Any given real network will substantially differ from the typical output of these models. (And note that I use typical here only because all of the models involve randomness and therefore can produce all sorts of things with a very low probability.) $\endgroup$ – Wrzlprmft Jan 14 at 18:25
1
$\begingroup$

The concept of “real-world networks” is not well defined. Usually, as soon as you find some kind of natural data, from which your network emerges it can be considered a real-world network. Most real-world data has certain properties that are significantly different from random networks (i.e., the Erdős–Rényi model), e.g., its degree distribution or the small-world property.

If you are asking whether there exists a graph that has that particular degree sequence, then the answer is yes, and here is an example given by its edge list: $ [(0, 11), \; (0, 3), \; (0, 3), \; (0, 10), \; (0, 6), \; (1, 4), \; (1, 3), \; (1, 11), \; (1, 10), \; (1, 5), \; (2, 5), \; (2, 7), \; (2, 7), \; (2, 4), \; (2, 3), \; (3, 5), \; (4, 8), \; (4, 8), \; (5, 6), \; (6, 9), \; (6, 11), \; (7, 7), \; (8, 12), \; (8, 10), \; (9, 10), \; (9, 12), \; (9, 11), \; (12, 12)]$

In general, this is known as the graph-realization problem and there are efficient (i.e. in polynomial time) algorithms that, given a degree sequence, can decide whether this sequence can be realized as a degree sequence of a graph or not.

Also note that networks can fall in much more than just these three categories, and the Watts–Strogatz model with $0$ randomness actually does not exhibit the small-world property.

$\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.