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. |
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. |
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.
No comments:
Post a Comment