By Aileen Agricola | August 13, 2012
Graph theory and network science are two related academic fields that have found application in numerous commercial industries. The terms ‘graph’ and ‘network’ are synonymous and one or the other is favored depending on the domain of application. A Rosetta Stone of terminology is provided below to help ground the academic terms to familiar, real-world structures.
Graph theory is a branch of discrete mathematics concerned with proving theorems and developing algorithms for arbitrary graphs (e.g. random graphs, lattices, hierarchies). For example, can a graph with four vertices, seven edges, and structured according to the landmasses and bridges of Königsberg have its edges traversed once and only once? From such problems, the field of graph theory has developed numerous algorithms that can be applied to any graphical structure irrespective of the domain it represents (i.e. irrespective of what the graph models in the real-world). Examples of such developments are provided below:
- Planar graphs: Can a graph be laid onto a 2D surface such that no edges cross. This problem has application, for example, in circuit board design where no two wires can overlap.
- Shortest paths: What is the minimum number of hops required to get from vertex A to vertex B in a graph? Moreover, what is the path that was taken? This problem has applications in routing,automated reasoning, and planning.
- Energy flows: If a continuous “energy field” is diffused out from a particular vertex (or set of vertices), how much energy do the other vertices in the graph receive? This problem is found inrecommendation engines, knowledge discovery, artificial cognition/intelligence, ranking, and natural language processing.
- Degree distribution: If a node is randomly selected from the network, what is the probability that it has X number of edges emanating from it? This statistic has implications for understanding how disease spreads through a social network and how communication networks can be sabotaged by directed attacks.
- Assortative mixing: Do nodes with characteristic A tend to connect to nodes with characteristic B? Such information is useful as a descriptive statistic as well as for inferring future connectivity patterns in the network.
- Growth models: Do all real-world networks grow according to a similar rule? Network growth models have implications for designing learning systems and understanding the future statistics of a fledgling network.