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.
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
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.
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.
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.
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.
I think we should mention the Kevin Bacon Number and the Erdős Number and similar applications. They are nice and interesting.
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:
Some of these examples show up in the broader applications section for the Graph Theory Wikipedia page as well, along with various others
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.
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.
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.
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.
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.
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.
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
