Graph Theory for Social Networks
Graph Theory Basics
What is a Graph?
Think of a city map. You have locations, like your home, the library, and the grocery store. You also have the roads that connect them. Graph theory is just a formal way of thinking about this kind of structure. It’s a mathematical way to represent networks of connected things.
In a graph, the locations are called nodes or vertices, and the roads connecting them are called edges or links. That's really it. A graph is just a collection of nodes and the edges that link them together. This simple idea can be used to model all sorts of things, from your friendships on social media to the flights between airports.
Types of Graphs
Not all connections are the same. Sometimes relationships are two-way, and sometimes they're one-way. This distinction gives us our first major classification of graphs.
An undirected graph has edges that go both ways. If node A is connected to node B, then B is also connected to A. Think of a friendship on Facebook. It's mutual.
A directed graph has edges with a direction, shown as an arrow. If A points to B, it doesn't mean B points back to A. Think of following someone on Twitter. You might follow them, but they might not follow you back.
We can also add more information to the edges. Some connections are stronger, more costly, or shorter than others. This leads to another classification.
An unweighted graph has edges that are all equal. The connection simply exists or it doesn't.
A weighted graph assigns a value, or "weight," to each edge. This weight could represent anything: distance between cities, cost of a flight, or the strength of a friendship.
Representing Graphs
Drawing graphs is great for visualization, but a computer needs a more structured way to store and work with them. The two most common methods are the adjacency matrix and the adjacency list.
An adjacency matrix is a grid, or a table, where the rows and columns are both labeled with the nodes of the graph. A cell at the intersection of a row (say, node A) and a column (node B) contains a 1 if there is an edge between A and B, and a 0 if there isn't. For a weighted graph, it would contain the weight of the edge instead of a 1.
Here is the adjacency matrix for the graph above.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
An adjacency list is a bit different. For each node, you simply list all the other nodes it's connected to. It's often more efficient for storing graphs that don't have a lot of edges.
Using the same graph, the adjacency list would look like this:
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]
Both methods represent the exact same graph, just in different formats. Choosing which one to use depends on the specific problem you're trying to solve and the structure of the graph itself.
In graph theory, what are the two fundamental components that make up a graph?
If you were to model the network of international airports and the flights between them as a graph, what would the airports themselves most likely represent?
These are the fundamental building blocks of graph theory. Understanding nodes, edges, and their different types allows us to start modeling and analyzing the complex networks all around us.