Graph Theory and Network Analysis

In a previous post, I commented on the possibilities of using Data Envelopment Analysis - DEA for carrying out comparisons of combined yields. Today I'm going to talk a little about another branch of mathematics that may have applicability in optimizing a business – graph theory.

Graph theory studies the relationship between individuals within a network, through structures called graphs. A graph is nothing more than a set of points (which can be individuals, installations, countries...) that contain relationships between them. For example, in a network of people, I, Fernando, can be friends with Jean and Paulo, who are also friends with each other, and Jean can be Bruna's only friend. This is an example of a graph, which can be represented graphically as shown in Figure 1.

Figure 1 – Representation of an example graph of a network of individuals

Source: ILOS

The graph can also be represented by a square matrix, called a correspondence matrix, where the number 0 represents the absence of a relationship, and the number 1 in this case (they can be others, in case there are weights for the relationships) represents the presence of a link .

Figure 2 – Representation of the same graph through the Correspondence Matrix

Source: ILOS

One of the first cases in which the use of graph theory is recorded is in the problem of bridges in Königsberg, a city that had four islands connected by seven bridges (as shown in Figure 3). Mathematician Leonhard Euller proved through graph theory that it was impossible to pass through all seven bridges once and return to the same island of origin without repeating at least one of the paths.

Figure 3 – The Königsberg Bridges

Source: ILOS

Checking a simple network of friends or islands connected by bridges may not seem so interesting, but think that the same type of representation can be applied to networks of distribution centers, airports or ports, supply networks, customers or even people within a company.

The most interesting part of graph theory is being able to understand which individuals are most influential within a network, through various measures of centrality. These can assess which vertices (the technical name given to each individual) of the graph are more influential, in various ways. For example, it is possible to determine the most influential individual based on the total number of relationships (which are called edges) that he has with other vertices of the network, which would be the so-called degree centrality. It is also possible to analyze which is the most present vertex in the shortest paths between any two vertices, through the betweenness centrality measure. These are just a few examples of measurements that can be performed to understand the influence of individuals within a network. In the references below, you can see each of them in more detail.

There are some free software programs that can generate reports that calculate these measurements and/or graphically represent a network, with multiple filtering and display options. One of them is the UCINET, which comes with Net Draw (which displays the graphic representation of the graph) and is very simple to use. Just create a correspondence matrix in the program itself or import one from Excel, and generate the desired analyses.

With the correct analyses, graph theory can be very useful for routing and network optimization problems in general, being a very aggregating knowledge for the logistics professional.

References

<http://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf>

<http://mathworld.wolfram.com/KoenigsbergBridgeProblem.html>

<http://objdig.ufrj.br/60/teses/coppe_m/LeandroQuintanilhaDeFreitas.pdf>