What people are saying about graph algorithms and the value it brings. In this post, graph algorithms will be discussed.
What are Graph Algorithms?
Graph models deal with a lot of data. Graph data is analyzed to draw useful information to identify human interactions. This enables the discovery of new business insights and opportunities
There are three kinds of algorithms; graph traversal, centrality, clustering. Graph traversal is the process of visiting each vertex in a graph. Centrality identifies the most important vertices within a graph. Graph cluster identifies a group of vertices which are connected in a particular way. For example, let’s look at the followings:
1. Graph Traversal
Finding the shortest path
Find a path between two vertices in a graph whose sum of the weights of its edges is minimized. There are many algorithms to solve this problem: Dikstra, A*, Bellman-Ford, Floyd-Warshall, etc.
▲ Feature 1. Shortest path between vertices A and F (pic from wikipedia.org)
Graph Distance
- Eccentricity E(v) of vertex v is the greatest distance between v and any other vertex.
- Radius r of a graph is the minimum eccentricity of any vertex.
- Diameter d of a graph is the maximum eccentricity of any vertex.
▲ Feature 2. Graph distance
2. Centrality
- Closeness The farness is sum of its distances from all other nodes. The closeness is the reciprocal of the farness.
- Betweenness The number of times a node acts and a bridge along the shortest path between two other nodes.
- Degree The number of direct neighbors
- Eigenvector The relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.
▲ Feature 3. Pagerank is a variant of the eigenvector centrality measure (pic from wikipedia.org)
3. Clustering
- Bron-kerbosch Finding Maximal cliques in an undirected graph. Clique is a subset of vertices of an undirected graph. Every two distinct vertices in the clique are adjacent.
▲ Feature 4. The 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4 (pic from wikipedia.org)
- Connected components Undirected subgraph in which any two vertices are connected each other. Strongly connected components. Connect components in directed graph.
Common questions
What's the difference between closeness and betweenness centrality?
Closeness measures how short the average path is from a node to everyone else. Betweenness measures how often a node sits on the shortest path between other pairs. A node can have high betweenness while being fairly distant from most others, if it is still the only route between two parts of the graph.
Is finding cliques with Bron-Kerbosch the same as community detection?
No. Bron-Kerbosch finds maximal cliques, groups where every member is directly connected to every other member. Community detection algorithms such as Louvain find looser clusters where internal connections are merely denser than external ones, and those clusters are not required to be fully connected internally.
Can these algorithms run inside PostgreSQL?
Plain PostgreSQL can compute connected components and shortest paths using recursive common table expressions, though it is not built for iterative centrality math at scale. Graph-oriented extensions or dedicated graph databases handle betweenness and eigenvector centrality more efficiently on large datasets.
How large a graph can these algorithms handle?
It depends on the algorithm. Degree centrality and connected components scale to graphs with many millions of edges using near-linear methods. Betweenness and eigenvector centrality get expensive as the graph grows, so large deployments typically approximate or sample rather than compute the exact value.
Which library or database should I start with?
For prototyping, NetworkX in Python covers all the algorithms in this guide on graphs that fit in memory. For production use on larger graphs, a graph database with a built-in algorithm library, or a PostgreSQL extension such as Apache AGE, avoids reimplementing the traversal logic yourself.
Sources
About this page
Last reviewed October 30, 2026 by the Nine Bits editors. Read our editorial policy or report an error.