What IS Graph Theory?

Graph theory is the branch of mathematics that studies situations or environments that can be modeled as a set of points that are connected by links.  The points could be living, such as human beings, dolphins, or gorillas, or non-living, such as computers in a network, IoT sensors in your house, or web pages on the Internet.  The large collection of connected things is called a network or graph (hence the term "graph theory").

When we use graph theory to model environments comprised of living things, we call that type of study "Social Network Analysis".  Don't be fooled when we use the term "Social" here; we really mean "Professional."  That is so because most SNA research does not track the social activities of people, it tracks their professional activities.  In this case, think of an organization like LinkedIn^®, that connects people through their professional activities.  They cannot track when those members meet socially for drinks after work at a downtown bar, but they can track when two people work for the same organization.

In all of these cases, researchers use well-founded mathematical principles and processes to learn more about the "things" in the environment, the links that connect those things, and even about the network as a whole.  For example, many SNA researchers want to know which node or link in the network is the "most important" and there are several standard ways to perform that calculation.  It also might be useful to know the order of importance of each node or link; for example, a link that uniquely connects to subnetworks is considered important because if it were to fail, the two subnetworks would not be able to communicate.  Considering calculations about the network as a whole, we could calculate how many links are present in the network compared to how many total links would be possible if every point in the network were connected to every other point.  We call this particular ratio (existing links/total possible links) the "network density."