Across virtually all scientific domains, there are phenomena that can be described as networks. Things in nature just seem to like to connect.
Let’s consider a couple of examples.
A social network
[GRAPHIC OF SOCIAL NETWORK]
Can we find people that are very well connected? Can we identify cohesive communities in the network? Are there people who link two communities together? All these questions and many more can be addressed in a graph theoretic approach.
The electrical grid
[GRAPHIC OF ELECTRICAL GRID]
How would the malfunctioning of one station affect the overall distribution of electricity? Could an outage at one station lead to outages in another region? Which stations could be considered high-risk targets of sabotage attacks?
Traffic
[GRAPHIC OF TRAFFIC NETWORK]
What happens if an accident blocks an important crossing? Is there an enhanced risk of congestions? Are certain areas at a higher risk to experience congestions? How could building a new road aleviate traffic in an area that has a school?
There are literally countless more examples of what you could describe as a network.
Think of three more things that have a networked structure.
So how would we model and analyze the examples above? That’s a question that we could decide ad hoc whenever we encounter the problem at hand. Luckily, we don’t have to. We can abstract away the essential structure of each of those and use a massive body of tools, metrics, and techniques that have been developed over centuries. That’s where graph theory come into play.
[GRAPHIC OF ABSTRACTION PROCESS]
Graphs are very versatile models for almost any kind relationship. They are “things” and how these “things” are connected to one another.
There are a lot of upsides to modeling relationships with graphs. First of all, graphs are very well formalized discrete mathematical structures. No matter the domain that we are modeling, we can profit from a large toolbox of mathematical analysis techniques and metrics.
There are a lot more specifications of graphs that can be used for more specific problems (for instance, what happens if the relationships, i.e., the edges, are directed, or what if we differentiate between the importance of edges and attach a weight to them?).