Graph Theory 101

by Sabina J Haque
graphics by Jovana Andrejevic

Networks in everyday life

What is one of the first things people do when they join a social media platform like Facebook? They send friend requests to whomever they know. Each of those people already has their own connections on Facebook, who also have their own connections, and so on. Being an active Facebook user pinpoints an individual’s place within a vast social network and highlights how they might know strangers via “mutual friends”. What may be less transparent is how platforms like Facebook have an underlying mathematical structure with a plethora of applications in the world around us.

When we look for them, we see that networks are versatile structures in many aspects of our lives: from the internet to mobile data networks to neurons in the brain. Simply put, a network is a collection of entities, such as Facebook users, and the connections between them. Mathematically speaking, a network can be visually represented by a graph and interrogated using the field of graph theory. Understanding graph theory unlocks the logic our world was built on, helping us answer questions about the fundamental connections that define our lives.

The nuts and bolts: what is graph theory?

Before we can use graph theory to describe what’s going on with Facebook or the brain, we need to take a step back and talk about the basics of graph theory.

Most generally, a graph is a collection of nodes (or entities) connected by edges. With the Facebook example, we can identify the nodes as individual users and the edges as mutual connections established by sending and accepting friend requests. As a result, the underlying Facebook graph captures the social relationships between entities, or users.

Defining a graph in this way might seem overly abstract. However, this rigorous formalism is necessary to utilize the tools and knowledge provided by graph theory, which is used to model many types of networks in physical, biological, social, and information systems (Figure 1).

Figure 1: Neuronal and social networks translated into graphs. Graphs are comprised of nodes and edges. In the brain (top), neurons (nodes) connected by synapses (edges). By transmitting electrical signals through synapses, neurons communicate with each other to form thoughts and feelings. Facebook (bottom) represents an example of a social network, with users (nodes) connected by accepted friend requests (edges).

The Facebook social graph, viewed simply, represents an example of an undirected graph (Figure 2, left). To break this down, let’s consider a connection between two Facebook users, Alice and Bob. If Alice is friends with Bob on Facebook, then Bob must also be friends with Alice. Each friend request on Facebook has to be accepted by both parties, making those individuals mutually associated by a friendship edge in the underlying graph. But these edges don’t have an orientation.

Alternatively, let’s say Alice and Bob are also on Instagram. While Alice follows Bob, Bob doesn’t follow Alice back. Here, the edges in the underlying graph have an orientation – an edge exists from Alice to Bob, but there isn’t an edge from Bob to Alice. The underlying graph for Instagram represents a directed graph, where the edges do have specific directions (Figure 2, center).

Figure 2: Diagrammatic representations of different types of graphs. In graph theory, we can use specific types of graphs to model a wide variety of systems in the real world. An undirected graph (left) has edges with no directionality. On the contrary, a directed graph (center) has edges with specific orientations. Finally, a weighted graph (right) has numerical assignments to each edge.

Sometimes we might want to model a system where each connection is weighted by some numerical value. Let’s say we want to develop a version of Facebook where the frequency of interaction between any given pair of users influences the weight of their connection. If Alice and Bob are constantly sending messages and tagging each other in posts, then their connection is weighted more heavily. On the contrary, if they don’t interact much at all over Facebook, the underlying algorithm concludes they aren’t that close and will give their connection less weight. From a graphical perspective, we can attach weights, or numerical labels, to the edges of the graph. The resulting graph is called a weighted or labeled graph (Figure 2, right). Facebook might construct such a weighted social graph if the designers want people to use the site more. For example, Alice might get a notification if Bob’s birthday is today. Because Alice clearly enjoys engaging with Bob, these reminders will easily prompt her to access Facebook and increase her screen-time on the site.

No pain, no gain: neural networks and pain processing

Let’s shift gears away from social networks and try to understand biological phenomena using the graph theoretic tools we’ve just defined. The human brain contains a plethora of underlying circuitry which generates all the sensations our bodies experience. These circuits are made of neurons, or brain cells. Neurons are connected to each other via synapses, which are long root-like structures. Through synapses, neurons communicate by transmitting signals in the form of electrical impulses. The synchronized activity of many communicating neurons generates brain activity.

The human brain contains 86 billion neurons, all interconnected to form many overlapping circuits that convey different cognitive processes, such as pain (Figure 3). Neuroscience research has been able to show how pain intensity can be directly related to specific patterns of brain activity. What remains unclear to researchers is how communications at the neuron level affect the manifestation and intensity of pain. This is a complex process involving different brain regions, sets of neurons, and chemical signals. If neurons in one region of the brain send messages to neurons in a different region, what kind of pain intensity does that result in? In particular, researchers do not understand how inhibitory neurons, which are specialized neurons that make other neurons less likely to fire, affect pain processing. Approximately how many inhibitory neurons are involved in the pathways that generate various levels of pain intensity?

We can use the tools of graph theory to disentangle some of these neuronal pathways, where neurons are nodes and synapses are edges (Figure 3). Recently, a group of researchers sought to understand how the brain might convey different levels of pain using graph theory. To capture the nature of the pain process, they built a weighted graph model of the different neural pathways known to generate pain responses. Here, each node represents a distinct pain neuron and the edges stand for their synaptic connections. In addition to weighting the edges, the researchers constructed their model such that the different nodes were weighted based on their degree, or the number of edges attached to each one. That is, a neuron with five connections to other neurons would have a heavier node strength in the graph than one with only two connections. By constructing a weighted graph in this way, the researchers could properly account for the varied strengths of communicated signals.

To properly model the neural pathways associated with pain, the researchers also had to account for inhibitory neurons, which weaken the strength of connections. Adjusting the fraction of inhibitory neurons in the weighted graph model allowed the researchers to determine that inhibitory neurons make up 20% of the circuitry in the brain required for pain processing. This particular configuration boosts information transmission of these neuronal pathways and is consistent with the observed patterns of brain activity that correlate with sensations of pain. The work done by these researchers represents a significant advance in how we understand our bodies’ reaction to pain. However, it also provides an example of how the basic tools of graph theory can be manipulated to accurately model a complex system and derive functional insight into a biological process.

Figure 3: Using graph theory to model pain processing in the brain. The feeling of pain manifests from several neural pathways in the brain. But what accounts for the intensity of pain at a neuronal level? Researchers implemented a weighted graph model of the neural pathways associated with pain to investigate this question. Each node represents a distinct pain neuron, and the edges their synaptic connections. Instead of the traditional weighted graph in Figure 2, the weights are associated with each node based on how many edges are connected to it.

Graph theory and beyond

Identifying a graph-like structure in a real world context may not seem too daunting. However, when we stop to consider how many possibilities exist to apply graph theory in everyday life, we realize how powerful graphs can be. Their abstract structure makes them endlessly versatile in almost any context. Beyond this expansive relevance, graph theory permeates some of the most cutting edge research in modern mathematics. Currently, researchers are using graphs to identify how entropy and disorder manifest in different physical systems, to develop machine learning algorithms, and to create mathematical formulas for the length of time it takes enzymes to transition into different complexes during biochemical reactions. Not only can we apply graph theory in many real world contexts, but graphs provide a framework to answer quantitative questions that can even help us lead better lives. For example, what is the optimal strategy to make friends when you start a new job? Identifying mathematical graphs (or networks) in everyday life unlocks tools and knowledge that enable us to address more complex questions and deepen our technical understanding of how things work than we would be able to without these models. 

Sabina J Haque is a 4th year PhD student in Dr. Jeremy Gunawardena’s research group. She is a mathematician who uses graph theory and statistical physics to model the stochastic nature of cellular information processing. Outside of the lab, she is a mediocre (but improving) runner, rap enthusiast, and politics junkie.

Jovana Andrejevic is a sixth-year Applied Physics Ph.D. student in the School of Engineering and Applied Sciences at Harvard University.

Cover Image: “Facebook Network Visualized with Gephi” by yaph is licensed under CC BY-NC-SA 2.0

For More Information:

This article is part of our special edition on networks. To read more, check out our special edition homepage!

See also: