Network Theory

Water droplets on a spider's web. Networks are a fundamental structure to our universe, and one that is getting increasing interest within the scientific community.

Water droplets on a spider’s web. Networks are a fundamental structure to our universeĀ and one that is getting increasing interest within the scientific community.

Network theory is a way of describing the world in terms of a model called a network that allows us to capture information about the relationship between things. We often describe the world in terms of objects or things and their properties. We talk about countries and their GDP, people, and their age, or the color of a car. This type of component-based analysis works well when the system we are interested in is relatively isolated. But when we turn up the interactions and connectivity between elements within a system, it is increasingly the connections that come to shape the elements and define the system as a whole, and thus we need a model that captures this information about the relationships and allows us to reason about it. This is where network theory comes in.

Graph Theory

Network theory starts with a very abstract view of the world as made up of nodes which are things or objects, like people, cities, computers etc., and the relationships between these things, called edges, such as friendships, trading partners, cables and so on. This abstract representation of the world can be used to model a wide variety of things. Thus, we can have social networks, biological networks consisting of interacting creatures within an ecosystem, or logistic networks composed of interacting suppliers and consumers. Network theory gives us a set of tools for analyzing the individual elements and relations within these networks, the structure of the network and the properties that these different network structures give rise to.

Connectivity

A graph of a small subset within the internet with edges representing links between websites. The coloring of edges reveals patterns of clustering in the network.

A graph of a small subset within the internet with edges representing links between websites. The coloring of edges reveals patterns of clustering in the network.

The first set of question one might like to ask about a particular network relates to its degree of connectivity, that is how connected an individual element or the whole network is. This will tell us many things about it, such as how quickly a new phenomenon could spread or propagate through the system. The average degree of connectivity will give us a quick answer to this. This is calculated by taking the total number of edges and dividing it by the total number of nodes within the network. We also need to take into account how large the network is, that is to say how far is it on average from one point to another. This is called the average path length, and we can calculate it by taking the average of all the path lengths between all the nodes. Because networks are all about connectivity, we often ascribe value to individual nodes based upon their degree of connectivity. There are various methods for calculating this among which a popular one is called Eigenvector centrality. It measures both how many edges a node has and how connected its adjacent nodes are. Popular web search engines use variants of this Eigenvector centrality measure to rank web pages by calculating both the number of links into a web page and the degree of connectivity of the pages that link into them, thus gaining an idea of the relative importance of the website.

Topology

Next, we are interested in talking about the overall structure to the network. This will be largely determined by how the relationship between the nodes was formed. If the relations between elements were generated randomly, one would expect a relatively even distribution of edges across the network. This type of structure or topology is called a distributed network, as the relative importance of any node is rather evenly distributed across the entire network. A second, type of network structure that can be observed is called decentralized or small world. This is generated by having local clusters of connections, but also some random distant connections. An example of this might be a group of friends, with some of the friends having distant relatives in other parts of the world. Research has shown that by using these local connections within the group and few distant connections, it is possible to connect two random people on the planet within an average of just six steps. It is thus termed small world. Lastly, we have more centralized networks called scale-free networks. This is where many nodes have chosen to connect to the same node giving it a degree of connectivity that greatly exceeds the average, whilst leaving the majority of nodes with a very low level of connectivity. Many real-world networks are thought to be scale-free, including social, biological and technological systems such as the World Wide Web, where very few sites like Wikipedia have a very large amount of links into them, whilst the vast majority of websites have very few.

Robustness

Aerial view of Tianjin. Cities are examples of economic hubs, playing a critical role in a nation’s economic activity, but due to their central role they can also add to the network’s fragility

These various types of network structures give rise to different properties. A key question that is interesting to ask here is how robust or fragile is a particular type of network is, as this will not only help us understand networks better, but will also be of great significance in how we design and manage them. For example, think about a country with many small to medium-sized cities supplying the population with various public services. If we were to remove one of the cities, it would have a limited effect on the overall system, because the network has a distributed structure, making it robust to failure of this kind. In contrary, if we take a country with one dominant capital city with the rest of the urban network dependent upon it for core services, this centralized network may be more efficient but it is also in what is called a more critical state, as affecting this single primary node would have a large systemic effect.

Significance

As we transit from industrial to information societies, networks are emerging as a new paradigm in how we structure our systems of both social and technological organization. Network theory is a young and rapidly growing area that provides us with a set of tools for designing and managing these new types of organization and more generally understanding the world around us from a different perspective.

Cite this article as: , "Network Theory Overview," in Complexity Labs, May 6, 2015, http://complexitylabs.io/network-theory-overview/.

 

2017-07-23T16:50:42+00:00