HN Explorer

What are some real world applications of graph algorithms?

31 points by ablmf ↗ HN
Can you guys 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?

11 comments

[ 3.3 ms ] story [ 39.0 ms ] thread
Phil-bitplex
Most everything I work on is related to graphs if I squint enough.

But to take an example from my visual planning - Gameplan.global - i use graph algorithms to model task dependencies, as well as the grouping structure.

When the tasks and dependencies are modelled as a graph, and the user wants to change a dependency, I can check the graph for a cycle. If a cycle will be introduced after the change, the change is disallowed.

It's not as grandiose as one could imagine for a very large social network graph, its practical and solved the problem I.

dclusin
Graphs are used to model dependencies of software libraries. If your build system can detect circular dependencies it's using a cycle detection algorithm of some kind.
qppo
Here's a real world graph problem that is probably worth some money.

Design a data structure that represents "business logic" as a graph and transformations between graphs.

Now given two distinct "business logic" data structures, A and B, write an algorithm that can:

- check if all flows/paths through A are present in B

- if not, enumerate which paths are no longer present

- for each path not present in B that is in A, enumerate possible substitutions

- for any given path in A and B define a distance metric that estimates the cost of any flow in A versus in B

Now I haven't don't this so I don't know if there's an elegant way to do it without some serious category theory/abstract algebra chops, but this is essentially a problem that costs millions of dollars in businesses. Evaluating changes to processes and their potential cost/benefit as well as deltas to other processes when structures are changed is extremely expensive, and it's why migrating ERPs or CRMs is so time consuming.

Of course for it to be real world, you need the business logic to be fuzzy because you don't have all the information to define such graphs A and B perfectly.

ironSkillet
I've wondered about this myself. I've tried imagining nodes as types and edges as functional transformations between them. Then there are essentially topological "moves" that you can make on your graph that shift the type data around and change the structure of your graph. Two programs are equivalent if the type graph of program 1 can be transformed into the other by these moves. This is all fuzzy thinking and not fully baked at all, but compilers do this all the time to construct optimized "equivalent" programs which gives me hope. I don't have the background in CS to pursue this rigorously though.
qppo
I'm sure this question has been studied in a thesis or ten in the field of computational sociology (which I didn't know existed until I googled the term).

I think there are a number of ways to state this problem in terms of graphs and their transformations, that's usually the case when it comes to abstractions. I think the question more worth answering is the methods by which real world organizational and business problems/processes can be expressed as graphs and their transformations, and how to perform analysis of those graphs for given queries about their nature.

I know a few people who do this but not as a rigorous CS discipline, it's often called Industrial Organizational Psychology, Process Optimization, etc etc. Its a complex interdisciplinary field.

nostrademons
In search/social/IR: reputation graphs, PageRank, reachability, link canonicalization & dupe detection, identifying "objects" that are referred to by different names (eg. people, company names, knowledge graph, synonyms, etc.), propagating properties known to one entity onto related entities.

In geo/rideshare/logistics: shortest-path routing, traffic flow, minimizing the distance driven by someone who needs to make multiple pickups, optimizing delivery routes.

In health: contact tracing, recommending closures of social activities

In industrial/EE applications: circuit theory, flow networks, load stresses

In basic CS infrastructure: register allocation, dependency management, dead code removal, data-flow propagation, figuring out bandwidth requirements in a network

Webster
Substructure and exact match molecule searches are example of graph matching algorithms
dalke
While true (I make a living working with them), I don't think the OP is that interested in graphs which are that small. What makes molecular graphs a bit more challenging is that there are 1 billion or so "small" graphs to search in a very large database. There are also important issues in how to represent a molecule as a molecular graph. Concepts like stereochemistry are tricky to handle.

"Search" here means subgraph isomorphism search.

No one that I know of uses a graph isomorphism test to compare two structures. Instead, they convert the molecular graph into a string, where the atoms and bonds are in a canonical order - perhaps a SMILES string or InChI string - and use a string search. Graph canonicalization is therefore important for molecular search, but not for the "complicated graphs, say social networks" the OP mentioned.

One specialized topic I worked on was the maximum common substructure problem. Given two molecules, what is the largest subgraph. Now extend that to N molecules. Now, find the largest subgraph which is in at least P% of those molecules.

newpycai
That sounds interesting. Have you published anything?
dalke
On 2D molecular similarity search, yes. https://jcheminf.biomedcentral.com/articles/10.1186/s13321-0... . The general approach reduces a 2D molecular graph into a 1D bitstring "fingerprint" which is representative of the graph, and such that bit-wise similarity (Jaccard-Tanimoto) of the fingerprint gives a useful proxy estimation of molecular similarity.

For the rest? No. I'm primarily a software developer, not paper author.

There's my co-authored paper at https://pubs.acs.org/doi/10.1021/acs.jcim.8b00173 , which depends a lot on (sub)graph canonicalization.

The maximum common substructure algorithm I developed, for a set of compounds, is part of the RDKit, "fmcs". The original pure-Python implementation is at https://bitbucket.org/dalke/fmcs/src . It's been rewritten since then in C++ for the RDKit.

The Python code is easier to understand.