Note 7: What is the difference between graph theory and network analysis?

What is the difference between graph theory and network analysis?
This figure is under CC:BY with a reference to
Prof. Dr. Katharina A. Zweig or to this blogpost.

Graph theory is often seen as one building block of network analysis. But what exactly are the differences between the two fields? Graph theory is a very abstract science that defines different graph classes and tries to understand their specific properties. Furthermore, it is concerned with so-called graph problems. Let me give you the most classic example of such a graph problem:

Given: A graph G
Wanted: The maximum clique C in G, i.e., the largest subset of nodes in G such that any two nodes in C are connected by an edge (complete subgraph)

Figure 1: A set of intervals (above) and the corresponding interval graph (below). This figure is under CC:BY with a reference to Prof. Dr. Katharina A. Zweig  or to this blogpost.

 A graph problem is always described by an input ("Given: XX") and a definition of the wanted output ("Wanted: YY") with resepct to the input. Finding a maximum clique in a given graph is problem that takes a long time to solve. The problem is that, intuitively, all possible subsets of nodes have to be tested of whether they constitute a clique. Until now, there is no other solution process that is substantially faster for all possible inputs. However, for some graph classes, it can be done much faster. One of those graph classes is a so-called interval graph (see Figure 1). Given a set I of intervals, the interval graph represents the intervals as node and connects any two nodes with each other, if the corresponding intervals overlap. In such a graph, we just need to find a spot where the maximum number of intervals overlap. It can be shown that we just have to look at all the endpoints of the intervals to find that spot. This can be done very fast, even if the network is extremely large.

Thus, graph theory is concerned with different graph classes and their relationship to graph problems and the runtime necessary to find the solutions to the graph problems.

"Note 7. In general, graph theory is concerned with the relationships between different graph classes and the relationship between certain graph structures, a graph problem, and its algorithmic solution." (Zweig2016)

In contrast, network analysis is interested in the connection between a certain graph structure and the function this graph structure has in the complex system of interest. For this, we use graph theoretic insights. For example, in random graph theory, we know how likely it is that a certain random graph contains a clique of order k (order = number of nodes in it). If a clique of order k is found in a complex network but it would also be very likely to find one of those in a random graph of a corresponding size and order, network analysis would deduce that the clique is not likely to be functional for the complex system of interest.

In summary: network analysis builds on (some of the) insights of graph theory, but is not interested so much in the abstract behavior of graph classes, but rather in the relationship between structure and function of a graph and the complex system it represents.