36
$\begingroup$

Can you give some real world examples of what graphs algorithms people are actually using in applications?

Given a complicated graphs, say social networks, what properties/quantity people want to know about them?

—-

It would be great if you can give some references. Thanks.

$\endgroup$
  • 6
    $\begingroup$ I don't have enough to say to justify posting this as an answer, but in chemistry we often consider molecules as undirected graphs: nodes (atoms) and bonds (edges). Things like subgraph matching (to aid with design of new molecules) and identification of cycles are quite useful. Directed acyclic graphs can also be used as inputs to neural networks, and I've seen at least one paper where undirected molecular graphs have been converted to directed acyclic graphs to use as inputs for a machine learning model. $\endgroup$ – thesketh May 24 at 21:33
  • $\begingroup$ @thesketh Can you give some references? $\endgroup$ – ablmf May 25 at 7:18
  • $\begingroup$ Relevance based searches use them extensively, think about the online sales (recommended products based on their similarity to the product page currently viewed), search engines (that run for expressions, match them with different factors including nofollow [highest relevance], page URL [search stack exchange], header and body texts, metadata, page rank and then synonyms of search expression etc.) and social media where relevance is implied (e.g. recommended friends, recommended groups, recommended pages). $\endgroup$ – user3819867 May 25 at 8:27
  • 1
    $\begingroup$ As a mere plebeian I don't get to use all these fancy algorithms. However much of what I work with can be called and interacted as a graph. For example CSS selectors are just a means to search the HTML tree. $\endgroup$ – user50829 May 25 at 17:09
  • 12
    $\begingroup$ This question is too broad and shows no research effort. See en.wikipedia.org/wiki/Graph_theory#Applications. $\endgroup$ – user76284 May 26 at 1:52

14 Answers 14

42
$\begingroup$

Graphs are definitely one of the most important data structures, and are used very broadly


Optimization problems

Algorithms like Dijkstra's enable your navigation system / GPS to decide which roads you should drive on to reach a destination.

The Hungarian Algorithm can assign each Uber car to people looking for a ride (an assignment problem)

Chess, Checkers, Go and Tic-Tac-Toe are formulated as a game tree (a degenerate graph) and can be "solved" using brute-force depth or breadth first search, or using heuristics with minimax or A*

Flow networks and algorithms like maximum flow can be used in modelling utilities networks (water, gas, electricity), roads, flight scheduling, supply chains.


Network Topology

The minimum spanning tree ensures that your internet traffic gets delivered even when cables break.

Topological sort is used in project planning to decide which tasks should be executed first.

Disjoint sets help you efficiently calculate currency conversions between NxN currencies in linear time

Graph coloring can in theory be used to decide which seats in a cinema should remain free during a infectious disease outbreak.

Detecting strongly connected components helps uncover bot networks spreading misinformation on Facebook and Twitter.

DAGs are used to perform very large computations distributed over thousands of machines in software like Apache Spark and Tensorflow


Specialized types of graphs

Bayesian networks were used by NASA to select an operating system for the space shuttle

Neural networks are used in language translation, image synthesis (such as fake face generation), color recovery of black-and-white images, speech synthesis

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ I think that some of these examples are overly simplified. For instance, can you explain how graph coloring would actually be useful for such a seating arrangement? Maybe you could argue that a distance-d independent set is useful here, but I would be surprised if there was any evidence that any cinema would have actually used such a computational approach ever. More likely, I think, the approach would be "leave two seats free on each row between two customers", and that's it. $\endgroup$ – Juho May 25 at 11:35
  • 4
    $\begingroup$ GPS devices have never used Dijkstra; it's far too slow. The earliest generation (on Symbian, Blackberry, etc) already used A* with extra highway-heuristics. Newer devices have Arc-flags graphs. $\endgroup$ – MSalters May 25 at 12:01
  • $\begingroup$ @MSalters I agree with you that Dijkstra is not optimal for this purpose. I'm not so sure that "GPS devices have never used Dikjstra" is true though. See here, for example $\endgroup$ – goncalopp May 25 at 18:48
  • 1
    $\begingroup$ @goncalopp: I've worked for close to a decade at a leading maker of GPS devices. I'm not sure at which company the person worked whose answer you linked, but we worked with both mapping companies at the time. We just got graphs from them. Even the hinting ("avoid this road, it's a slip road") was done by us. They may have used Dijkstra internally to validate their delivered product, but a GPS device at the time had a 250 Mhz ARM9 at best. $\endgroup$ – MSalters May 26 at 6:59
  • 1
    $\begingroup$ @MSalters The article you reference talks about "speed up of the arc-flag acceleration of Dijkstra’s algorithm". I could be missing something but the authors seem to be talking about a variant of Dijkstra. So it seems strange to say this isn't using Dijkstra. The abstract states "Arc-flags are a modification to the standard Dijkstra algorithm." Even if you want to debate that point, it's clearly graph-based. $\endgroup$ – JimmyJames May 26 at 20:17
25
$\begingroup$

Pathfinding is arguably one of the most practical subareas of algorithms and graphs. I am sure you can find plenty of use cases from navigation, routing, logistics and computer games, all growing multimillion businesses.

If you want to think about social networks, you might think about recommender systems some of which are graph-based for discovering similar likes.

| cite | improve this answer | |
$\endgroup$
  • 9
    $\begingroup$ Not only multimillion dollars. The internet requires such graph algorithms to route packets. This supports trillions of dollars in commerce. $\endgroup$ – Sandy Chapman May 24 at 23:19
13
$\begingroup$

Chances are high you found your way to the Stack Exchange network via Google or another search engine. Google uses the PageRank algorithm, which models webpages and links in them as a directed graph. The algorithm itself is perhaps more linear algebra than graph theory (it looks for an eigenvector for the graph's adjacency matrix), but given that the majority of the Earth population uses it on a daily/weekly basis, it should definitely count as an important real world application of graphs.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The eigenvector in PageRank is the stationary distribution of a Markov chain which is imo a graph based characterization. $\endgroup$ – Surb May 25 at 21:37
7
$\begingroup$

Cargo routing for e.g. railways, shipping liners, cargo planes are extremely difficult optimization and useful problems that are fundamentally some sort of network flow problem on a large graph. Similarly, rerouting cargo once delays happen is an important multi-item path finding problem that is very important to e.g. Maersk. What about designing routes for the garbage trucks in a city?

There are also network design problems, e.g. for choosing which links to build in the electricity network to make it robust. E.g. are there any edges that would disconnect the graph if removed? What about a pair of edges? What about five? Note that since this is a network flow problem, the graph might still be a single component; there could just be insufficient capacity between two clusters after removing the edge.

What about detecting bottlenecks in graphs? That is important when designing computer communication networks. For example, there's something called the Cheeger constant that can measure the "bottleneckedness" of a graph.

Stack exchange has an entire separate community dedicated to solving optimization problems like these at or.stackexchange.com.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

In compilers, instruction scheduling algorithms are graph algorithms. They operate on the Data Dependence Graph, finding a topological sort which can most efficiently execute the instructions.


Certain computations can be expressed as a graph. Microsoft Excel formulas form a graph, as they refer to other cells and perform a computation which further formulas may depend on. There are also "blueprint" programming languages which are graphs, with nodes representing operations and edges representing the flow of data.

Machine Learning uses graphs. The model is expressed as a graph, piecing together different operations which combine to perform the overall behavior you want.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

I think we should mention the Kevin Bacon Number and the Erdős Number and similar applications. They are nice and interesting.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This was established by earlier work. Milgram, Stanley (May 1967). "The Small World Problem". Psychology Today. Ziff-Davis Publishing Company. Travers, Jeffrey; Milgram, Stanley (1969). "An Experimental Study of the Small World Problem". Sociometry. 32 (4): 425–443. $\endgroup$ – Tom Kelly May 26 at 8:26
6
$\begingroup$

Markov chains are commonly represented by directed graphs, and have tons of applications across probably most, if not all, scientific fields. The Wikipedia page on Markov chains discusses in more detail many of the following places where you might see Markov chains:

  • Thermodynamics and statistical mechanics
  • Chemical reaction networks
  • Phylogenetics
  • Population dynamics
  • Neurobiology (neurons as nodes, synapses as edges)
  • Automatic speech recognition
  • Google's PageRank system
  • Markov Chain Monte Carlo (statistics), which itself has tons of applications across fields
  • Games
  • etc

Some of these examples show up in the broader applications section for the Graph Theory Wikipedia page as well, along with various others

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

One example that you may overlook when thinking of graphs are meshes.

Almost every algorithm that works on 3D meshes is a graph algorithm. In fact you often use algorithms that are usually defined on general graphs like Dijkstra's algorithm in many mesh processing tasks.

The simplest mesh representation is a undirected graphs equipped with a metric on edges. A more sophisticated data structure is a half-edge mesh, that is a directed graph that has two edges with opposite direction between connected points and a metric on the edges that gives the same length for both half-edges that form an edge.

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

It's not been mentioned yet, but one big area where they're used every day by developers is in software version control.

Almost all modern distributed version control tools utilize a directed acyclic graph structure to track changes, with each node representing a set of changes and each edge connecting pairs of changes that are derived from each other. git even explicitly calls this out in their technical documentation.

Because of merging changes, a regular tree structure cannot accurately represent the standard working model used in most DVCS systems, so you actually need a graph here to get an accurate idea of what has happened in terms of changes to a pisece of software.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

Regarding social networks and your second question,

What properties/quantity people want to know about them

You can try it yourself, so anything you might want to know about the social network is a valid answer to your own question.

Ref How to use Facebook's Graph Search (and why you would even want to)

Some examples given in the article are

I searched for photos of my friends who visited Hawaii, because I just returned from a trip to Oahu and wanted to see their photos of the islands.

Friends who listen to Daft Punk and live in San Francisco

Friends of my friends who work at TechHive

You can also find some other real world applications from the websites of Palantir and Neo4j

I remember some years ago seeing a presentation from Palantir where they helped the police use graphs to model criminal networks. So they would add connections between people based on friendship, family relationships, financial transactions, phone calls, etc, as well as businesses used for money laundering, where they kept their bank accounts, etc. I think the police has done similar work on paper for many years, but with graphs and computers it can be made more efficient, scalable, and easily be queried.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

One example not mentioned here is Gaussian elimination to solve linear equation systems. In order to minimize runtime and memory requirements, it is important to do the elimination in the right order so as to avoid too many non-zero entries in the resulting equations.

It turns out you can model this problem as a graph problem.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

They're commonly used in molecular biology and genomics to model and analyse datasets with complex relationships.

For example, graph-based methods are often used to 'cluster' cells together into cell-types in single-cell transcriptome analysis.

Another use is to model genes or proteins in a 'pathway' and study the relationships between them. This is common in analysis of metabolic pathways and gene regulatory networks. See here for examples of how graphs are used in genomics.

Evolutionary trees, ecological networks, and hierarchical clustering are also represented as graph structures.

Applications of graph theory range far beyond social and toy examples. These will only become far more widespread as technology develops to leverage this kind of data. At this point, graph-based methods are so pervasive that researchers in some fields (such as biology) may not even be aware that they're using them.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Graphs appear all over the place in physics, most often as a visual representation of an underlying tensor calculus in a monoidal category (in the sense of string diagrams or Penrose notation). Feynman diagrams or Feynman graphs give the most important and striking example of this. Feynman graphs are a visual way of doing calculations in perturbative quantum field theory, the physical framework underlying the Standard Model of Particle physics, and also used to describe complex, many-body quantum systems.

Each graph encodes a complex number called an amplitude, and by summing over graphs/amplitudes, one can calculate, for example, the probability for a particular collisional process between elementary particles taking place. These graphs are sometimes interpreted as providing a picture of particle collisions in spacetime, although this intuition is often misued. In perturbative string theory, sums over one-dimensional Feynman graphs are replaced by sums over two-dimensional surfaces.

Other, related appearances of graphs are as angular momentum diagrams or in tensor networks, and each of these (including Feynman graphs!) arise from some categorical tensor caculus.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Using GPS/Google Maps/Yahoo Maps, to find a route based on shortest route. Google, to search for webpages, where pages on the internet are linked to each other by hyperlinks; each page is a vertex and the link between two pages is an edge.

On ecommerce websites relationship graphs are used to show recommendations.

And more

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.