Types of Graphs
While nodes and edges may have any number of interesting properties and labels, some properties are more common than others. In particular there are two properties of edges that stand out so much that they are said to change the type of graph. These two properties are edge weight, and edge directionality.
If the edges in your graph have directionality then your graph is said to be a directed graph (sometimes shortened to digraph). In a directed graph all of the edges represent a one way relationship, they are a relationship from one node to another node — but not backwards. In an undirected graph all edges are bidirectional. It is still possible (even common) to have bidirectional relationships in a directed graph, but that relationship involves two edges instead of one, an edge from A to B and another edge from B to A.
Directed edges have a subtle impact on the use of the term neighbors. If an edge goes from A to B, then B is said to be A’s neighbor; but the reverse is not true. A is not a neighbor of B unless there is an edge from B to A. In other words, a node’s neighbors are the set of nodes that can be reached from that node.
Let’s use two social networks as examples. On Facebook the graph of friends is undirected. If you are someone’s friend on facebook they are your friend too — friendship on Facebook is always bidirectional meaning the graph representation is undirected. On Twitter, however, “following” someone is a one way relationship. If you follow Beyoncé that doesn’t mean she follows you. The graph of Twitter users and their followers is a directed graph.
If edges in your graph have weights then your graph is said to be a weighted graph, if the edges do not have weights, the graph is said to be unweighted. A weight is a numerical value attached to each individual edge. In a weighted graph relationships between nodes have a magnitude and this magnitude is important to the relationship we’re studying. In an unweighted graph the existence of a relationship is the subject of our interest.
As an example of a weighted graph, imagine you run an airline and you’d like a model to help you estimate fuel costs based on the routes you fly. In this example the nodes would be airports, edges would represent flights between airports, and the edge weight would be the estimated cost of flying between those airports. Such a model could be used to determine the cheapest path between two cities, or run simulations of different potential flight offerings.
An unweighted graph may be used because a relationship in terms of magnitude doesn’t exist. For example, a graph representing college courses and their prerequisites has this property — nodes are courses and edges represent a prerequisite relationship between two classes. If a particular course has two prerequisites it is wrong to say that one course is more of a prerequisite than the other, you just have to pass both prerequisite courses before taking the course in question.
Sometimes a graph will be unweighted even when the relationships clearly have an associated magnitude. Perhaps it’s because the magnitude of the relationship is hard to get data about; perhaps it’s because the existence of a relationship alone is interesting enough; perhaps there is some other reason. For example a researcher may first build a simpler (unweighted) model before deciding to add complexity (weights). Consider social networks again. It is generally true that a person is closer to some friends than others. Edge weights could be used to represent this relative closeness — but closeness is subjective and hard to get data about.
Can you imagine if Facebook asked you, “on a scale of 1–10, how close are you with this person?” every time you added a new friend? For most people, that would be be creepy, invasive, and uncomfortable. Besides that, everyone’s 1–10 scale would be different. This data would be hard to get as well as inconsistent; furthermore, the existence of friendship is interesting by itself. Weighting this social graph is probably not worth the effort.
Another reason to use or not use weights depends on the type of question you want to answer. For example consider a graph where the edges are roads and the nodes are intersections. Further consider these two questions:
- “Are intersections A and B connected by roads?” and,
- “What is the shortest route between intersections A and B?”
If I only need to answer the first question I can save myself time and effort by using an unweighted graph. If I need to answer the second question, I’ll need to find a way to weight the edges — perhaps using the length of each road, or the length of the road divided by the speed limit on that road.
When you begin any project that uses graph theory, you must determine what type of graph you’re going to use. Using the two categories we’ve discussed here, we are left with 4 major types of graphs:
- Undirected & Unweighted: relationships do not have magnitude and are bidirectional.
- Undirected & Weighted: relationships have a magnitude and are bidirectional.
- Directed & Unweighted: relationships do not have magnitude and are one way.
- Directed & Weighted: relationships have a magnitude and are one way.
Each type of graph has different strengths and weaknesses. Sometimes these weaknesses make one type of graph a poor choice — for example the existence of one-way roads and divided highways makes an undirected graph a poor choice for studying traffic patterns. Other times the choice will be more ambiguous such as the previously discussed decision to weight social network edges with a “closeness” score or not.
Picking the appropriate kind of graph to model your problem isn’t always a matter of which model is correct or incorrect. A favorite quip among statisticians applies to graph theory as well: all models are wrong, but some are useful. When deciding how to use a graph to model your problems consider experimenting with different types and weighing the tradeoffs involved in both collecting data to build the model and the differences that might appear in analysis of those different models.
