Exact matches only
Search in title
Search in content
Search in excerpt
Filter by Custom Post Type

Network Degree Distribution

This map of London’s underground transport network shows stations with varying degree distributions from one up to five or more

A key parameter to the make-up of any network is the network’s degree distribution. Degree distribution tries to capture the difference in the degree of connectivity between nodes in a graph.1 It is really asking the question, do all the nodes have roughly the same amount of connections or do some have very many while others have very few connections? By answering this, we will get an idea of how centralized or distributed it is, which is a defining factor to networks telling us how something will flow through it, which nodes have influence, or how quickly can we affect the entire network.

Degree Distribution Spectrum

It is possible to define a spectrum for the network’s degree of distribution starting from systems with very homogeneous degree distribution, that is, all nodes have a relatively similar amount of connections. Here we will be talking about random networks and distributed systems where we have a relatively even topology to the network, but as we turn our degree distribution parameter up we will start to see hubs appearing. These types of networks are described as decentralized, implying that unlike our distributed graph where there was no real center, these have a number of different central hubs to them. These decentralized networks have the small-world property that we mentioned earlier, making them very effective at connecting a large amount of elements within a short average path length. Lastly, if we turn up our degree distribution parameter to make a very large disparity between the node’s different degrees of connectivity, we will start to get centralized networks with one or few dominant nodes and many nodes with a relatively low level of connectivity. This type of network is captured within a model called a scale-free or power law network that we will be talking about in a later section.

Network visualization to the global air transportation network where we can see some nodes with a very high number of connections while others have few.
Degree distribution tries to capture this difference in connectivity between nodes in a network

We might then ask why we get these different networks with fundamentally different degree distributions? If we start out with a random network, we will be able to see that most networks are in fact not random at all. Birds do not just choose at random what other creatures they are going to prey on within a food web. People do not randomly choose their friends and transport authorities do not just randomly lay down highways between any two locations. These connections are of course made under specific rules that govern why and to which other nodes any node will make a connection with. And it is out of the aggregate behavior of these nodes interacting that we get networks that have specific and widely encountered properties, meaning we do not live in a world of random networks but in fact a world of networks that have a specific structure that has emerged out of these local rules.

Importance

Degree distribution parameter may just be a quantitative parameter, but changing it can have a qualitative effect on the network we are dealing with. To illustrate this, we might take an example of a political network. Political social networks span from the highly centralized form of dictatorship, where all sociopolitical connections lead back to one dominant node, to at the other end of the extreme some kind of egalitarianism where responsibility and authority are distributed out in a pluralistic fashion. These different network structures will have a systemic effect and influence on almost all areas of the social and cultural fabric.

Citation

Cite this article as: Joss Colchester, "Network Degree Distribution," in Complexity Labs, January 6, 2016, http://complexitylabs.io/degree-distribution/.
1. View Source
2017-05-24T14:22:24+00:00