Graph theory is emerging in business as a way to simplify and interpret complex data. As our data volumes grow, graphs enable visualization of that data and its patterns to help businesses make better-informed decisions.
Graph analysis is based on graph theory. Often called network graphs, since they depict a network of interconnections, graphs are mathematical structures used to model relationships between objects. They provide a powerful way to visualize data and its relationships. Graphs also provide an optimized data structure that computers can use to perform calculations using the best algorithms for the specific problem being solved.
While graphs have become popular in depicting and analyzing social networks, their business value goes so much deeper.
A Simple Graph Theory Example
Most business data today is stored and analyzed in tables of rows and columns; a spreadsheet is an example. Typically, each row represents one thing (a person for example) and each column represents data about that thing (name, birthdate, eye color, etc.) All of the rows represent the same type of thing (people in this example). This is structured data (a table in this case) and homogenous (every row is a person). Graphs allow us to represent and explore the relationships between different types of things (people, locations, businesses, roads, traffic, weather) in ways that are difficult and or slow with structured data.
As a simple example, let’s look at ridesharing or food delivery services.
Food service delivery needs to assign the optimum driver to the pickup and delivery of orders. Let’s look at one simple decision that you need to make: which driver is the best option to pick up and deliver the food, based on minimizing time to delivery and cost of delivery? With those requirements (or constraints) you don’t want to task a driver who is 15 minutes away to pick up an order when there’s an available driver already within 2 miles.
The graph below shows one aspect of this decision–the closest driver to the restaurant for pickup. In a more complex analysis, you would graph other aspects such as customer proximity to the driver and restaurant and the drivers, the time when their food will be ready for pickup, and driver availability during that window.
As you can see in the above graph, the Restaurant is at the center of the graph. The Drivers are described based on their distance from the Restaurant.
- The drivers and the restaurant are called Vertices, or Nodes.
- The lines that connect the vertices are called Edges.
- The number of miles between the Drivers and the Restaurant are known as Weights.
A graph then is the combination of Vertices and Edges that visually depicts the relationships, including the Weights of the various relationships.
In our oversimplified example, Driver 3 is the obvious choice to pick up the food order in the above graph.
Let’s explore more complex scenarios in business.
Applications for Graph Theory in Business
Graph theory has often been overlooked as business intelligence systems are defined, primarily because data analysts don’t tend to think of their data as being networked, nor as being like a social network.
The reality is that any data that has relationships can be used to create a graph or networked graph model. Here are some business examples:
- All the flights to and from airports can be organized and then optimized as a graph. In this case, the airports are the nodes and the flights the edges between the nodes. These graphs can be used to optimize the efficiency of planes, minimize fuel costs, and minimize flight operations time. You could extend the graph to include optimizing pilots and flight crews, scheduling optimum maintenance crew availability, and optimizing gate use.
- All of the products carried by a retailer can be graphed based on which products are purchased together and by which buyer profiles, for both local and country-wide analysis. The graphs help perform retail customer analysis to determine trends including what products are frequently purchased together and by what type of customer. The results provide key intelligence. When constrained optimization is applied, the results offer the best possible options for maximizing product sales at the set margin to the customers most likely to purchase.
- All of the patients with a specific physical condition can be analyzed via graph theory to understand which other physical conditions are co-existent for medical analysis. Graph theory is part of the community detection computations that are being applied for drug discovery as well as for Covid transmission analysis.
Such graphs become extremely complex. Which is why the graph data must be submitted to powerful computers to perform the analytics calculations required to identify the meaningful relationships and impacts of those relationships.
Graph Theory and the Pandemic
Let’s explore an example that’s top of mind for many of us: Covid and how it is transmitted.
The graph below represents Covid spread in Hong Kong between January and April 2020. 1,038 Covid cases were analyzed using network graphs and algorithmic computations to define the related clusters, which were then analyzed to discover the most likely sources of transmission. The analysis results include:
- An investigation of 137 different recognized clusters (median cluster size = 2) found that 7 probable super spreader events (SSEs) accounted for 58% of all clustered cases. The largest cluster of 106 cases, as depicted in the graph, was associated with four bars in Hong Kong.
- An estimated 19% (95% CI: 15% – 24%) of cases caused 80% of all local transmission. Transmission in social settings was associated with more secondary cases than transmission in households (p = 0.002).
https://www.nature.com/articles/s41591-020-1092-0
As you can see, even this small variable graph gets complicated. Yet the visualization makes the analysis far more efficient. This graph highlights around 1000 variables. Now imagine using graph theory to analyze hundreds of thousands of data points. That’s where graph theory shines.
The Bottom Line
Graph theory is emerging as a high-potential tool for businesses to enhance their business intelligence with powerful computational analysis.
The challenge to date has been that graph analysis becomes so complex, it’s difficult to submit and solve the models.
QCi just announced QGraph as part of Qatalyst. QGraph automatically transforms graphs, applies popular graph functions and submits the problem to the Qatalyst Core for resolution. No programming, no hassles. To learn more, click here.
