patternMajor
What are some real world applications of graphs?
Viewed 0 times
realwhataregraphsapplicationsworldsome
Problem
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.
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.
Solution
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
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
Context
StackExchange Computer Science Q#126198, answer score: 44
Revisions (0)
No revisions yet.