Post #202

Graphs with the same degree distribution Degree distribution plays a key distinctive role between graphs. In networks science there are specific models that generate you a graph according to some distribution of degrees. For example, scale-free networks are the ones with power law degree distribution, which we observe in real world (e.g. social networks). Scale-free networks use preferential attachment mechanism that mimics the way people connect with others in a new society: we connect to people with high degree and people that we know. The Barabási–Albert model is the most famous example of such a model. What's interesting in some cases is to provide explicitly the degrees that you expect to have in a graph and then generate a graph with this sequence of degrees. There is a model for that too: it's called Chung-Lu model. Yet, in some other cases, you want to generate a graph exactly with some degree sequence. This is quite simple, you just connect pairs of vertices one by one, until you make a desired degree sequence. It shows how many actually there are different graphs with the same degree sequence. Here is an explanation of this.