What Is A Graph
For those who have never heard of “graph theory,” the word graph probably already means something. In a corporate meeting someone might say, “this graph shows that our profits are in the toilet.” In algebra class you were asked to, “graph this function.” Unfortunately, graph theory has nothing to do with these kinds of charts.
For our purposes, a graph is a collection of things that have relationships. The things are called vertices or nodes; the two words are used interchangeably in academic literature and elsewhere. Throughout this course I will use the term node simply because it is my preference. The relationships between nodes are called edges.
Graph theory is the study of these collections of nodes and edges. Graph theory is a mathematical language used to describe things with relationships. The heart of graph theory is reducing specific collections of things with specific relationships into this generalized format. After that, we can use graph theory to help us understand and analyze those specific things. Graphs have been studied extensively because they are useful tools in modeling so many real world phenomena including social network analysis, robot/AI path planning, traffic analysis, municipal water system design, and much more.
Let’s define our terms more carefully.
A node is the fundamental unit of a graph. Just about anything can be represented by a node — people in a social network, intersections in a system of roads, airports in a graph about airline traffic. Whatever thing we’re studying, instances of that thing are probably nodes in our graph.
As we’ll see, nodes can be given a number of properties depending on the circumstance. If our nodes represent people, we may wish to know their ages, credit scores, or the last book they read — depending on context.
An edge is a connection between exactly 2 nodes. This connection could mean any number of things, depending on the context. If our nodes represent people an edge might represent friendship between the people; alternately it might represent a financial transaction between the two people. Two nodes that are connected with an edge are called neighbors.
Like nodes, edges can be given any number of properties depending on the context. If the edge represents friendship we may wish to know how old that friendship is, or assign a value representing the strength of that friendship. If the edge represents a financial transaction, we may wish to know how much money was exchanged, what goods/services that amount was exchanged for, and the date of the transaction.
Graphs can range in complexity from quite simple to monstrously complex. As we progress through this course we will introduce increasingly complex graphs with more properties and more complex relationships. As we will see, however, even simple graphs with very few nodes and edges can have powerful emergent properties.
Consider this simple graph representing a network of friends. Each node represents a person, edges between nodes represent friendship. Charlie is friends with Eva, Alice, and Dominique. Eva’s only friend is Charlie. Dominique is friends with everyone but Eva.
There is only so much we can learn about this small social network, but social network graphs are quite powerful. For example, they have been used to dissect and understand Russia’s use of Twitter to spread propaganda, and to discover people of interest in the Enron scandal. Modeling these kinds of graphs is popular enough to support a cottage industry of software to help analyze and visualize social network data.
