Applications of Graph Theory: Questions & Answers

Both graph theory and network science are powerful tools that can be applied not only in many different branches of research but also in day to day contexts. The reason is that network thinking is thinking in terms of connections. How one thing relates to another and what kind of patterns of relationships tend to emerge. Knowing what to expect gives you a twofold advantage: on the one side, you have a better overview and can better predict what's going to happen; on the other side, you also have a better understanding of how you could integrate into or influence the system (and vice versa) if you would like to get engaged on a deeper level.

What is a Network?

A network is a multiplicity that is comprised of interconnected entities. Network science represents a multiplicity or a process as a combination of nodes (vertices) and edges (connections or co-occurrences). Using InfraNodus you can build network graphs from any connected data as long as it's represented as a text.

What are the Networks Made of: Graphs' Nodes, Vertices and Clusters

Networks are made from the nodes (vertices), which represent more or less stable entities, and from the edges, which represent relations / connections between those entities.

Any situation or process can be described with many different network graphs, depending on what you choose to encode as the nodes and the edges. This is important to realize, because it shows that there can be many different network representations for one situation. Each will provide a different point of view and that is the first step in cognitive reconfiguration practice: to be able to observe from different network perspectives at once.

For example, you could describe a social network in a group as a graph where the nodes are the people and the connections (edges) are the relations between them (the edge is drawn between the nodes that are "friends").

The nodes that are connected into a small group form a cluster.

What Can We Learn from a Graph?

Once we represent any notion as a combination of nodes and edges, we start thinking of the reality in terms of relations or transactions between more or less concrete entities. This is, of course, a simplification, but it's the kind of the simplification that is very close to how our perception is made. We do think in terms of entities and we do think in terms of relations. Things are represented in our brain using relations, which form concrete patterns. If the pattern recurs it represents an entity. So we can say that network representation is simply a reflection of how information is encoded within our brain.

Let us demonstrate how this thinking can be used to better understand what the system we study is capable of.

If we look at the example above, the network was quite dispersed. It’s quite clear that such social structure would not be very efficient in spreading information among all members or activating them all for a collective action (synchronization). Most people don’t know each other, there are no links between them, so there’s no informational pathways for communication within the group.

The situation changes drastically when we introduce a hub – the node that is connected to most (or all) other nodes in the network:

Now most of the nodes belong to the same graph, which is called giant component (because it contains most of the nodes in the network) – it’s possible to reach almost any node from any other node. The nodes that don’t belong to the giant component are called orphans (in the example below it’s you and Peter, who didn’t succumb to the Alien Intelligence).

The network above is modular (there are distinct communities or clusters present within), heterogenous (some nodes have many connections, some only have a few or none), and highly organized (even hierarchical in this case).   Obviously, there’s a lot of pressure on the main hub, the Alien Intelligence, to spread information through this network.

If we would like this network to be a bit more decentralised (and, thus, self-organized), we’d rather build links between the existing members, to allow them spread information to one another without consistent external stimulation. Remember, we need to ensure there’s still giant component within the network, so the most efficient way to create it would be to link the two existing clusters together (Diego-Dmitry and Renata-Marcela-Caique), then unify all the “orphans” (e.g. You-Peter and Dan-David-Varya), join these new clusters together and then link them to the other two clusters. The resulting image would look something like this:

We can now see that all the clusters are connected to one another and such network can use its own infrastructure to proliferate information. It does not need any external impulses in order to communicate. Different color designates a different community – the nodes that are more densely connected to each other than to the rest of the network.

The nodes that have more connections are the hubs. They have a higher degree (the number of edges) and are shown bigger on the graph. Each edge in this graph represents interaction. The fact that we show them all within the same graph implies that the underlying principles of this interaction are more or less the same (i.e. the social codes).

At the same time, there may slight differences in how the members of the green cluster relate to one another if you compare it with the members of the red cluster. This alone may be sufficient reason for the nodes to split into groups. Therefore, it’s important to think of the edges as a kind of social glue or the connectivity basis that connects people together and to be aware about the essence of this basis. Each community comes together on the basis of sharing something in a unique way: ideology, beliefs, social codes, nationality, sex, common practice.

This graph is a simplified version of what Bruno Latour refers to as the actor-network theory or what Foucault called dispositif: a network of relations that come into play and define a particular situation. It reveals power structures, relations between individuals and content, as well as potential gaps and links that can be made between them.

To summarize: dynamic network construction of the relations that are in play at a given situation and their constant reconfiguration is the key to expanding awareness and becoming more conscious of the relations that are at stake.