Graph Algorithms
Built-in algorithm support
Graph DBMSs provide efficient implementations of many classical graph algorithms. These are typically exposed as procedures (in Neo4j, via the Graph Data Science library) rather than formulated as Cypher queries. The DBMS can exploit adjacency-list storage and in-memory traversal to run algorithms that would be slow to express in a declarative query language.
Taxonomy of algorithms
| Category | Algorithms |
|---|---|
| Traversal | Breadth-first search, depth-first search |
| Path finding | Dijkstra’s shortest path, A*, all-pairs shortest paths |
| Centrality | PageRank, betweenness centrality, closeness centrality, eigenvector centrality |
| Community detection | Louvain, label propagation, strongly connected components, weakly connected components |
| Similarity | Jaccard similarity, cosine similarity, node similarity |
| Link prediction | Preferential attachment, common neighbours, Adamic-Adar, resource allocation |
| Structure | Spanning trees, articulation points, bridges, cliques, triangle count, max flow, min cut |
Many of these algorithms overlap with content from the Algorithms course (Part IA).
Graph metrics
Community metrics
| Metric | Question asked |
|---|---|
| Edge/node ratio | How dense is the graph? |
| Diameter | What is the longest shortest path between any two nodes? |
| Clustering coefficient | How likely are my friends to be friends with each other? |
| Tree count | How many distinct spanning trees exist? |
| Modularity | How well does a proposed partition reflect community structure? |
Centrality metrics
Centrality measures answer: which nodes are most important to the structure of the graph? Different definitions of “important” give different rankings.
| Measure | Definition of importance |
|---|---|
| Degree centrality | Number of direct connections |
| Betweenness centrality | How often a node lies on the shortest path between two other nodes |
| Closeness centrality | Average shortest-path distance to all other nodes |
| Eigenvector centrality | Importance weighted by the importance of neighbours (PageRank is a variant) |
| PageRank | Random-surfer model: probability that a random walker with teleportation is at the node |
Similarity metrics
Similarity measures quantify how alike two nodes are based on their properties, their neighbourhood, or both. These are used for recommendation and deduplication.
| Measure | Basis |
|---|---|
| Jaccard similarity | Overlap of neighbour sets divided by union |
| Cosine similarity | Angle between property vectors |
| Euclidean distance | Straight-line distance in property space |
Link prediction
Link prediction estimates the likelihood that a new edge will form between two currently unconnected nodes. It is used extensively in social networks to recommend friends.
| Method | Heuristic |
|---|---|
| Preferential attachment | Nodes with many connections gain more |
| Common neighbours | More mutual friends = more likely to connect |
| Adamic-Adar | Like common neighbours but weights rare neighbours more heavily |
| Resource allocation | Models flow of resources through the network |
Applications
Social networks
Graph algorithms recommend new friend links, detect communities of shared interest, and identify influential users (influencers). A social graph with 1 billion nodes and hundreds of billions of edges requires approximate algorithms and distributed computation.
Biological networks
Metabolic networks with millions of nodes and edges represent biochemical reactions. Biologists query such graphs to find important structures for drug development — pathways that are critical for a pathogen but absent in the host. Community detection identifies groups of compounds that participate in the same biological process. Centrality metrics identify enzymes whose removal would cripple the organism.
Road and logistics networks
Shortest-path and minimum-spanning-tree algorithms underpin route planning in GPS navigation. Max-flow algorithms optimise transport and logistics schedules.
Limitations of in-DBMS algorithms
Graph algorithm libraries in DBMSs are convenient but not a substitute for understanding the algorithms themselves. The DBMS implementation may:
- Use an approximation rather than an exact algorithm (common for centrality on large graphs).
- Be limited by available memory.
- Not expose the intermediate results needed for debugging or verification.
For the Tripos, you should understand what the algorithms do, not merely that a DBMS provides them.
Summary
- Graph DBMSs offer built-in implementations of traversal, path-finding, centrality, community detection, similarity, and link-prediction algorithms.
- Community metrics describe the macroscopic structure of the graph.
- Centrality metrics rank nodes by how structurally important they are.
- Link prediction estimates the probability of future edges, with applications in recommendation systems.
- These algorithms have wide application in social networks, biology, logistics, and many other fields.