Practical Examples of Graphs

Due to the dependence of graph theory algorithms on the size and complexity of the graph, some solutions may only be very close approximations of the true solution. Approximations are the best solution because certain issues haven’t even been solved.

Airline Planning (Flow problems):
One of the most well-known uses of graph theory is in the area of flow issues, which includes practical situations like airline scheduling. Airlines operate flights all over the world, and a crew is needed for each journey. Not every flight gets access to every member of the staff because they can be stationed in a specific city. Graph theory is utilized to schedule the flight crews.

In order to develop a directed graph for this issue, flights are used as the input. All serviced cities are the vertices, and a directed edge will connect the flight’s departure and arrival destinations. A network flow can be viewed in the resulting graph. The weights, or flow capacity, of the edges are equal to the number of crew members needed for the flight. A source and a sink vertex must be added in order to finish the flow network. The base city of the airline that supplies the personnel serves as the source, while all of the destination cities serve as the sink vertices.

The airline can then determine the minimum crew size required to run all flights using graph theory to determine the minimum flow that covers all vertices. Additionally, the airline can plan a timetable for a smaller crew that may not necessarily visit all the locations by assigning weights to the cities based on their value.

There are numerous different situations in which this flow problem can be used. For instance, when only a limited number of trucks may be used to deliver goods from warehouses to stores, or when planning the routes of public transportation while taking into account the anticipated number of passengers.

Map instructions (Shortest path):

These days, we constantly use our smartphones to assist us in our daily activities. It benefits me personally by providing cycling routes from my position to a restaurant or bar. But how are these calculations done? This problem, which belongs to the category of defining the shortest path, has an answer in graph theory.

Making a map into a graph is the first stage. All street crossings are regarded as vertices for this purpose, while the routes that connect intersections are regarded as edges. Weights on the edges can be used to indicate the travel time between vertices or the actual distance between them. This graph can be directed to display the city’s one-way streets as well.

Now, an algorithm just needs to determine the path with the lowest sum of edge weights between the two corresponding vertices in order to provide the direction between two points on the map. This is a simple task for small networks, but it is challenging for graphs built from large cities. Fortunately, there are many different techniques, such the Dijkstra’s algorithm or the A* search algorithm, that, while they may not provide the exact answer, will provide a very excellent estimate.

One of the most common uses of graph theory is to determine the shortest or fastest path between two points on a map. The shortest path problem, however, has additional uses as well. For instance, it can be applied to telecommunication networks to find the shortest network delay time or social networks to examine the “six degrees of separation” between individuals.

Algorithms for search engines (PageRank algorithm):

We can easily traverse the World Wide Web thanks to search engines like Google. The search engine searches for websites that match the query whenever a query is made to look for a certain collection of words. How does the engine rank the millions of matches it has found so that the most popular ones are displayed first?

In order to resolve this problem using graph theory, the search engine first constructs a webgraph, a graph whose vertices are websites and whose directed edges follow hyperlinks on those websites. A directed graph that displays all website relationships is the end result. Additionally, weights can be added to the vertices to give more significant or influential websites precedence.

The most popular websites can be categorized using a variety of techniques. PageRank is one of the first ones Google uses. Here, the engine determines the likelihood that a user will click a link before iteratively adding those odds to create a probability distribution. This distribution depicts the probability of a random visitor finding a specific website. The machine then sorts the list of websites based on this distribution and displays the top ones.

This algorithm had numerous flaws. One can take advantage of it by purchasing links on websites with larger weights, or by creating blog websites with plenty of connections to a specific website to boost the click chance. Although there are more sophisticated algorithms available today that take sponsored advertising into account, the fundamentals of graph theory and website relationships still remain.

Use of social media (Community detection):

Facebook had 2.9 billion active users in January 2022. As a social media platform, advertising generates the majority of the platform’s income. With so many users, it will be exceedingly expensive for advertisers to place their advertising campaigns in places where everyone can see them. Targeting only those who might be interested in your goods is another option. How can you describe a target audience like that?

By giving each person a vertex in accordance with graph theory, you can make a social network graph. If the individuals have a relationship, such as being friends on Facebook, you connect the vertices with the edges. Consequently, an undirected graph results. This enormous graph might initially appear to be incredibly chaotic, however one can always identify patterns in it.

By breaking the graph down into smaller sub-graphs, you can determine the optimum target market. This can be accomplished using a variety of algorithms, including minimal cut techniques like the Karger’s algorithm and hierarchical clustering algorithms. As a result, the graph is divided into groups of individuals that are very connected to one another but less connected to other groups of individuals. Communities are what these organizations are collectively known as, and they have things in common like certain brands, singers, or even political parties. Advertising benefits from identifying these groups since they are more likely to purchase similar goods, support the same musicians, or vote for the same political parties.

In addition to advertising, other uses for community detection are possible. Following the identification of the communities, connections between or even within groupings can be compared. A group or vertex acting differently from its peers may be an indication of incursion. This could serve as a security check. Attacks on a network, for instance, could result in unusual behavior if the vertices are computers or programs. The network’s security can be increased by spotting odd connections.

Some examples follow directed graph and some undirected graph. The advantages of weighted graph are: They can be used to represent intricate social networks, electronic circuits, and a wide range of other intricate real-world applications that cannot be realized with any other data format. The shortest route between any two nodes can be determined using it. Users can identify a path that visits every node in the graph for the least amount of money by using the spanning tree concept.

There are some examples of almost ideal answers to combinatorial optimization problems that seek the shortest path. The most fundamental TSP heuristic is arguably the Nearest Neighbor Method. According to the algorithm’s methodology, the driver should start by traveling to the closest place. The motorist can turn around and return to the starting point once all the cities in the loop have been visited.

The user must pick a city at random, move on to the closest unexplored city, and so on in order to solve TSP using this method. You have to get back to the city you started in after exploring every city on the map.

(Applications, Advantages and Disadvantages of Weighted Graph, 2022; Graph Theory and Its Uses with 5 Examples of Real Life Problems, n.d.; How Are Graphs Used in Our Daily Lives? — Wise-Answer, n.d.; PhD, 2020; Simic, 2021; Travelling Salesman Problem — Challenges & Solution in 2022 — Upper Route Planner, n.d.)

References

Applications, Advantages and Disadvantages of Weighted Graph. (2022, May 19). GeeksforGeeks. https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-weighted-graph/

Graph theory and its uses with 5 examples of real life problems. (n.d.). Www.xomnia.com. https://www.xomnia.com/post/graph-theory-and-its-uses-with-examples-of-real-life-problems/

How are graphs used in our daily lives? — Wise-Answer. (n.d.). Wise-Answer.com. Retrieved October 14, 2022, from https://wise-answer.com/how-are-graphs-used-in-our-daily-lives/
PhD, P. A. (2020, December 19).

How to Solve Traveling Salesman Problem — A Comparative Analysis. Medium. https://towardsdatascience.com/how-to-solve-the-traveling-salesman-problem-a-comparative-analysis-39056a916c9f

Simic, M. (2021, December 7). Weighted vs. Unweighted Graphs | Baeldung on Computer Science. Www.baeldung.com. https://www.baeldung.com/cs/weighted-vs-unweighted-graphs

Travelling Salesman Problem — Challenges & Solution in 2022 — Upper Route Planner. (n.d.). Retrieved October 14, 2022, from https://www.upperinc.com/guides/travelling-salesman-problem