Key Takeaways
- Betweenness Centrality identifies high-risk bridging nodes that connect otherwise isolated user groups, revealing potential lateral movement paths and shared credential abuse.
- Community Detection (CDLP) groups users and machines by access patterns in near-linear time, exposing coordinated activity and possible insider threat clusters.
- Weakly Connected Components (WCC) surfaces isolated legacy systems and shadow IT assets that lack proper monitoring or integration with your security stack.
On June 18, 2025, Cybernews reported the largest data breach in history: 16 billion login credentials leaked from 30 different databases. The exposed data spanned everything from social media and developer platforms to corporate tools and VPNs, with most of it siphoned off by infostealer malware.
When you analyze breaches like this, relationships matter more than individual data points. Graph databases, paired with the right algorithms, surface hidden patterns and potential attack paths. But storing data as nodes and edges isn’t enough. To uncover real influence or lurking risks, you need algorithms built for community detection and connectedness.
FalkorDB recently introduced several new graph algorithms: Betweenness Centrality, Weakly Connected Components (WCC), and CDLP (Community Detection via Label Propagation). The built-in graph browser helps you quickly visualize and explore results with Cypher queries, so you can get hands-on with your data right away.
“When data breaches spread like contagion, it’s not just who you are that matters, but who you’re connected to.” Roi Lipman, CTO, FalkorDB
Graph Algorithms & Analytics
Path Finding Algorithms
Pathfinding algorithms determine the most efficient route between nodes in a graph, based on metrics like distance, cost, or time. These algorithms are fundamental to navigation, routing, and resource optimization across both physical and digital networks.
Notable examples include Dijkstra’s algorithm, which computes the shortest path from a source node to all other nodes; A*, a heuristic-based method that speeds up pathfinding with informed guesses; and Single Source Shortest Path (SSSP), which finds optimal routes from a specific starting point. In Directed Acyclic Graphs (DAGs), where cycles are absent, the Longest Path algorithm determines the maximum-weighted path, particularly useful in project scheduling, dependency resolution, and build systems.
Centrality Algorithms
Centrality algorithms evaluate the importance of nodes based on their position and role within a graph’s structure. These measures identify key nodes in a network: influential users in social networks, weak points in critical infrastructure, or web pages ranked by relevance and connectivity.
Some of the most widely used centrality algorithms include Betweenness Centrality, which highlights nodes that act as bridges between different parts of the graph; PageRank, originally developed by Google to rank search results; and Degree Centrality, which measures importance based on the number of direct connections a node has.
Community Detection Algorithms
Community detection and connectivity algorithms identify clusters or groups of nodes that are more closely connected to each other than to the rest of the graph. These algorithms uncover hidden structures and patterns in networks, such as customer segments, coordinated fraud rings, or organizational subgroups. They can also determine whether a graph is fully connected or if it contains isolated “islands” of disconnected components.
Popular algorithms in this category include Louvain Modularity, which detects communities by optimizing the density of connections within groups compared to between them, making it an efficient choice for large-scale graphs. Its improved variant, Leiden Modularity, offers greater stability and more clearly defined communities. Label Propagation (LPA) provides a fast, scalable approach by having nodes adopt the majority label from their neighbors, making it ideal for massive networks where performance is critical.
For analyzing connectivity, Strongly Connected Components (SCC) identify tightly-knit groups in directed graphs where every node is reachable from every other node. Meanwhile, Weakly Connected Components (WCC) uncover broader connectivity by grouping nodes based on mutual reachability, regardless of edge direction.
Graph Algorithms in Action
Betweenness Centrality
Betweenness Centrality measures a node’s significance by calculating how often it appears on the shortest paths between other node pairs. Nodes with high scores can be identified as critical connectors or intermediaries within the network. This algorithm finds nodes that play a central role in facilitating communication or information flow, making it especially valuable for analyzing influence and structural importance in complex graphs.
Performance: Betweenness Centrality is computationally more intensive than local algorithms. Its time complexity is typically O(n×m) for unweighted graphs, where n is the number of nodes and m is the number of edges. Because it requires shortest path calculations between all node pairs, it scales less efficiently on very large graphs.
Let’s model a corporate network where users access machines. We’ll represent User, Server, and Workstation nodes connected via ACCESSES and CONNECTS_TO relationships.
Now, we’ll apply Betweenness Centrality on this graph to detect nodes critical to access flow, such as systems that bridge users to sensitive resources. The algo.betweenness procedure lets you specify node labels and relationship types, so you can focus analytics on specific graph segments without needing manual subgraph extraction.
Results show:
Workstation-2 is the most central: it sits on many shortest paths between users and shared resources. This makes it a high-risk lateral movement surface.
Shared-Storage also connects multiple workstations, indicating a sensitive aggregation point.
Users like Bob who access multiple workstations may bridge departments, especially if combined with Label Propagation or Degree Centrality.
Community Detection using Label Propagation (CDLP)
Label Propagation (CDLP) is a community detection algorithm that groups nodes based on their structural proximity in a graph. Starting with each node assigned a unique label, the algorithm iteratively updates each node’s label to match the most frequent label among its neighbors. Over time, densely connected regions naturally converge to a shared label, revealing distinct communities within the network.
Performance: CDLP runs in near-linear time, with each iteration operating at O(n+m) complexity, where n is the number of nodes and m is the number of edges. It typically converges within a few iterations, making it well-suited for large-scale graphs where speed and simplicity are critical.
Imagine a network where users log into systems, and over time, attackers may compromise certain users or machines. By analyzing access patterns, you can uncover clusters of accounts and systems that may be involved in coordinated activity, potentially identifying malicious lateral movement or insider collusion.
Results show:
Communities 0 & 1 represent normal user activity with expected machine access.
Community 3 is a dense cluster of users (Eve, Mallory, Trent) accessing the same high-value machines: a strong signal for investigation, possibly indicating shared credentials, malware propagation, or insider threat behavior.
Weakly Connected Components (WCC)
The Weakly Connected Components algorithm identifies groups of nodes in a graph that are connected by some path, ignoring the direction of edges. In each component, every node is reachable from every other node if the graph is treated as undirected. This algorithm is especially useful for detecting disjoint subgraphs or structural partitions in large, directed networks.
WCC begins by assigning each node a unique component ID. It then iteratively traverses all edges, merging connected nodes into the same component, ignoring edge direction throughout. The process continues until no more merges are possible.
Performance: Time Complexity: O(V+E), where V is the number of nodes and E is the number of edges. This near-linear performance makes WCC highly scalable and suitable for very large graphs.
The algo.wcc procedure supports real-time component analysis across filtered subgraphs by label or relationship type, helping you quickly isolate disconnected or shadow assets with a single query.
Results show:
Component 0 is a developer environment used by Alice and Bob.
Component 2 is a sensitive financial system accessed by Eve, possibly a separate trust zone.
Component 5 is an isolated legacy server: this could signal an orphaned asset or a misconfigured endpoint lacking proper integration or monitoring.
Quick graph algorithms recap
| Algorithm | Purpose | Reveals | Performance | Best Used For |
|---|---|---|---|---|
| Betweenness Centrality | Measure influence of a node based on shortest paths | Key connectors, chokepoints, potential high-risk hubs | O(n×m)O(n \times m)O(n×m)for unweighted graphs | Identifying shared access nodes, influential users, or lateral movement vectors |
| Weakly Connected Components (WCC) | Detect disconnected or loosely connected graph segments | Isolated systems, legacy assets, disconnected business zones | O(n+m)O(n + m)O(n+m) | Auditing network segmentation, locating shadow IT or misconfigured environments |
| Community Detection (CDLP) | Group nodes into clusters based on structural proximity | Behavioral clusters, coordinated access patterns, implicit user groups | O(n+m)O(n + m)O(n+m)per iteration; fast to converge | Detecting suspicious clusters, shared credentials, insider threat investigation |
Conclusion
Graph algorithms are rapidly becoming required tools for cybersecurity teams, enabling them to look beyond isolated data points and map the true structure of risk, influence, and vulnerability in digital systems. Modern graph databases like FalkorDB empower you to not only store and visualize relationships, but also apply advanced algorithms such as Betweenness Centrality, Weakly Connected Components, and Community Detection, to spot hidden attack paths, risky access patterns, and potential insider threats in real time.
If you haven’t explored graph analytics in your security stack yet, now is the time. With intuitive tools and an ever-expanding library of built-in algorithms, platforms like FalkorDB make it easier than ever to translate complex real-world systems into actionable insight.
FAQ
What are graph algorithms used for in cybersecurity?
Graph algorithms analyze network structure to identify attack paths, insider threats, shared credentials, and vulnerable access points by mapping relationships between users and systems.
How does Betweenness Centrality detect security risks?
It calculates how often nodes appear on shortest paths between others, revealing critical bridge systems that attackers could exploit for lateral movement across networks.
Why use Label Propagation (CDLP) for threat detection?
CDLP runs in near-linear time to group users and machines by access patterns, quickly surfacing suspicious clusters that may indicate coordinated attacks or credential sharing.
