Can you guys give some real world examples of what graphs algorithms people are actually using in applications?<p>Given a complicated graphs, say social networks, what properties/quantity people want to know about them?
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.<p>In geo/rideshare/logistics: shortest-path routing, traffic flow, minimizing the distance driven by someone who needs to make multiple pickups, optimizing delivery routes.<p>In health: contact tracing, recommending closures of social activities<p>In industrial/EE applications: circuit theory, flow networks, load stresses<p>In basic CS infrastructure: register allocation, dependency management, dead code removal, data-flow propagation, figuring out bandwidth requirements in a network
Here's a real world graph problem that is probably worth some money.<p>Design a data structure that represents "business logic" as a graph and transformations between graphs.<p>Now given two distinct "business logic" data structures, A and B, write an algorithm that can:<p>- check if all flows/paths through A are present in B<p>- if not, enumerate which paths are no longer present<p>- for each path not present in B that is in A, enumerate possible substitutions<p>- for any given path in A and B define a distance metric that estimates the cost of any flow in A versus in B<p>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.<p>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.
Most everything I work on is related to graphs if I squint enough.<p>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.<p>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.<p>It's not as grandiose as one could imagine for a very large social network graph, its practical and solved the problem I.
Pixie is the recommendation engine at Pinterest, based on random walks on a graph: <a href="https://link.medium.com/cgxBc05RO6" rel="nofollow">https://link.medium.com/cgxBc05RO6</a>
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.