"Two-scale" network?

38 Views Asked by At

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$?

1

There are 1 best solutions below

0
On BEST ANSWER

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.