This website your browser does not support. Please upgrade your browser Or Use google Crome
';
Latest Announcments
Other Links
Graphs and networks: bridging the theoretical and the technical

By Kaneenika Sinha, IISER Pune

Much of the current discourse in science revolves around the two (seemingly disparate) notions of “pure” and “applicable” sciences. This blog post will focus on a central area of mathematics called graph theory, which seamlessly bridges the gap between these two notions. Graph theory is at the heart of some of the most vital questions that our fast-paced modern civilization confronts. How does a mobile network provider optimise the number and location of cell phone towers so that a maximum number of areas can be serviced at minimum cost? How does the GPS device in your car find you the shortest path to your destination? How does Google almost always direct you to the most relevant websites when you search for something?

There is a similarity among the above questions: they can all be interpreted in terms of a network, that is, a mathematical model consisting of various nodes and edges (or bridges) that connect these nodes.

Graph theory literally starts with a question about bridges.

The modern-day Russian exclave of Kaliningrad was known as Koenigsberg (in Prussia) in the 18th century. This city spread out on both sides of a river. This river also encircled two islands. Both the sides of the river and the two islands were connected to each other by seven bridges as shown in the figure below. In 1736, the famous mathematician Leonhard Euler considered the following problem: could one walk through the city by crossing each bridge exactly once? More precisely, irrespective of where you lived in the city (islands or mainland), could you leave your home, travel through each bridge exactly once and return home?

konigsberg

Euler interpreted his question as follows: let us regard the two sides of the river and the two islands as vertices or points (or nodes) in a plane. One draws an edge between any two vertices if there is a bridge between them. In fact, the number of edges between any two vertices is equal to the number of bridges connecting them. We now have a collection of vertices and edges and wish to know whether you could have a path (that is, a sequence of vertices and edges) that starts at a vertex and returns to it by crossing each edge in the collection exactly once. Such a path is called a circuit. We immediately observe that to have such a circuit, for each edge landing into a vertex, we would require a different edge out of that vertex. In other words, the degree of each vertex, that is, number of edges coming out of each vertex must be even. This condition fails in the Koenigsberg bridge network and Euler concluded that the answer to his question was negative.

Euler’s analysis enables us to place the Koenigsberg Bridges problem in a much wider context. In general, a collection of vertices and edges (both of which we assume to be finite in number for simplicity) is called a graph. An edge is identified with the two vertices that it connects. Euler’s question generalizes to the question whether a given graph has a circuit. A graph with such a circuit is called an Eulerian graph and Euler’s fundamental observation, which initiated the study of graphs as a mathematical subject, was that a graph is Eulerian if and only if it is connected (that is, any two vertices can be connected by a path) and the degrees of all vertices are multiples of 2.

Graph theory is a subject that opens up various possibilities of investigation for the mathematician as well as the biologist (not to mention the computer scientist!) Very often, they approach the same structure, but with different questions in mind, each fundamental and interesting in its own right.

To the biologist, in the last couple of decades, graphs have become an important tool to study interactions between cellular components. Often, such interactions between these components (which can be thought of as nodes) create graph networks with several thousand components and one has to rely on graph analysis to describe the known interactions as well as to use known patterns to predict other interactions, which are then explored further through experiments. What do these graphs look like?

In the late 1990s, some key observations were made about biochemical networks in a cell which made them amenable to modeling and analysis by graphs. One such observation, made by DJ Watts and SH Strogatz in 1998, is that such networks are “small-world.” This means, firstly, that while most nodes may not be joined by edges, they can be connected by a path with a relatively small number of edges. This is akin to a group of faculty members at a research institute in India. While any two of them may not directly know each other, a little bit of conversation will almost certainly reveal a common friend during graduate school or postdoc years! Small-world also refers to the property that these networks have a high level of clustering. There are smaller groups of nodes which have a lot of interaction with each other and relatively weaker links outside of the group. The Watts-Strogatz model generates random graphs with these properties.

Yet another important observation about biochemical networks made by AL Barabasi and R. Albert in 1999 is that they self-organize into a “scale-free” state. This means that any part of the network is likely to have a similar structure to the whole. Technically speaking, the probability that a node in a network interacts with K other nodes decays as a negative power of K. Once the biochemical interactions of the components of a biochemical network are viewed in these terms, graph theory provides further insights to them and this has been among the most fundamental approaches to analyze biochemical regulatory networks in the last two decades. A few examples where this approach has helped are metabolic circuits, cell signalling networks and cytoskeletal structures. Limitations in my knowledge prevent me from explaining this further and I would like to refer the interested reader to a comprehensive survey, “Insights into the Organization of Biochemical Regulatory Networks Using Graph Theory Analyses” by Avi Ma’ayan (Journal of Biological Chemistry Vol. 284, No. 9, pp. 5451-5455). This survey covers most of the key developments in this area and is written in a language accessible to the non-specialist.

To the mathematician, graphs may provide a different kind of information. For example, a special type of graph that is of interest to mathematicians is what is called a regular graph, a graph in which very vertex has the same degree. In other words, the number of edges emanating from each vertex is the same. The behaviour of the number of circuits in such a graph is mysterious: an exciting development in mathematics is that in some cases, the ratio of the number of circuits to the total number of nodes in such a graph exhibit a pattern similar to those exhibited by the values of a certain function introduced by Srinivasa Ramanujan in 1916. Ramanujan’s function led to the birth of the theory of modular forms, which now occupy a venerable position in mathematics. The discovery of fundamental information about what are called “Fourier coefficients” of such functions lies at the heart of deep and beautiful mathematics: in the 1970s, a quantification of the size of these coefficients won Pierre Deligne the Fields Medal (the most prestigious prize in mathematics). In a more recent development, discovery of the distribution patterns among these coefficients won Richard Taylor the 2015 Breakthrough Prize in Mathematics. It is indeed amazing that the number of circuits in certain families of regular graphs follow patterns which are very similar to those of Fourier coefficients of modular forms. This indicates that these graphs model and encode a lot more information than what immediately meets the eye and a mathematician cannot resist taking the study of this aspect of graphs further.

The above examples demonstrate how graph theory engages a mathematician and a biologist in different ways. Both derive important interpretations, which have led to key developments in their respective fields. Graph analysis helps to power our cellphone network, enables us to surf the internet smoothly and helps us to travel to our destination in a timely manner. Yet, at the core of all these developments is an innocent question asked by Leonhard Euler around 300 years ago, possibly during a recreational walk in Koenigsberg!

Images licensed under the Creative Commons:( https://creativecommons.org/licenses/by-sa/3.0/deed.en)
For Attribution Check link:
1.( https://commons.wikimedia.org/wiki/File:7_bridges.png)
2.( https://commons.wikimedia.org/wiki/File:Keningsbergo_pontoj_markitaj.png)
3.( https://commons.wikimedia.org/wiki/File:K%C3%B6nigsberg_graph.svg)