Graph Database: Graph Algorithms

Graph Database: Graph Algorithms

Part of: Graph Database User Guide

---

HeliosDB provides 10 high-performance graph algorithms for network analysis.

1. PageRank

Purpose: Measure the importance of nodes based on incoming links.

Use Cases: Influence analysis, web page ranking, citation networks

Algorithm: Iterative power method with damping factor

Example 21: Find Influential Users

use heliosdb_graph::algorithms::centrality::pagerank;

// Get all user IDs
let all_users: Vec<NodeId> = storage.get_vertices_by_label("User").await?
    .into_iter()
    .map(|node| node.id)
    .collect();

// Run PageRank
let ranks = pagerank(
    &storage,
    &all_users,
    0.85,    // damping factor (typical: 0.85)
    100,     // max iterations
    0.0001   // convergence tolerance
).await?;

// Sort by rank
let mut sorted: Vec<_> = ranks.iter().collect();
sorted.sort_by(|a, b| b.1.partial_cmp(a.1).unwrap());

println!("Top 10 most influential users:");
for (i, (node_id, rank)) in sorted.iter().take(10).enumerate() {
    if let Some(node) = storage.get_vertex(**node_id).await? {
        println!("  {}. {} - PageRank: {:.4}",
                 i + 1,
                 node.properties.get("username").unwrap(),
                 rank);
    }
}

Performance:

• 10K nodes: ~45ms (P50), ~82ms (P99)
• 100K nodes: ~520ms (P50), ~890ms (P99)

Parameters:

• damping: Probability of following a link (typical: 0.85)
• iterations: Maximum iterations (typical: 20-100)
• tolerance: Convergence threshold (typical: 0.0001)

2. Louvain (Community Detection)

Purpose: Detect communities/clusters in the graph.

Use Cases: Social groups, customer segments, network modules

Algorithm: Modularity optimization with hierarchical clustering

Example 22: Detect Social Communities

use heliosdb_graph::algorithms::community::louvain;

let all_nodes: Vec<NodeId> = storage.get_vertices_by_label("Person").await?
    .into_iter()
    .map(|node| node.id)
    .collect();

// Run Louvain algorithm
let result = louvain(
    &storage,
    &all_nodes,
    1.0  // resolution (higher = more communities)
).await?;

println!("Community Detection Results:");
println!("  Total communities: {}", result.num_communities);
println!("  Modularity: {:.4}", result.modularity);

// Group nodes by community
let mut communities: HashMap<usize, Vec<NodeId>> = HashMap::new();
for (node_id, community_id) in result.communities {
    communities.entry(community_id).or_insert_with(Vec::new).push(node_id);
}

// Print community sizes
for (community_id, members) in &communities {
    println!("  Community {}: {} members", community_id, members.len());
}

// Get members of largest community
let largest_community = communities.iter()
    .max_by_key(|(_, members)| members.len())
    .unwrap();

println!("\nMembers of largest community:");
for node_id in largest_community.1 {
    if let Some(node) = storage.get_vertex(*node_id).await? {
        println!("  - {}", node.properties.get("name").unwrap());
    }
}

Performance: 10K nodes: ~180ms (P50), ~320ms (P99)

Parameters:

• resolution: Controls community size (1.0 = default, higher = smaller communities)

3. Label Propagation

Purpose: Fast community detection based on label spreading.

Use Cases: Real-time clustering, dynamic graphs, large networks

Algorithm: Iterative label propagation with majority voting

Example 23: Quick Community Detection

use heliosdb_graph::algorithms::community::label_propagation;

let all_nodes: Vec<NodeId> = storage.get_vertices_by_label("User").await?
    .into_iter()
    .map(|node| node.id)
    .collect();

let result = label_propagation(
    &storage,
    &all_nodes,
    100  // max iterations
).await?;

println!("Label Propagation Results:");
println!("  Communities found: {}", result.num_communities);
println!("  Converged in {} iterations", result.iterations);

Performance: 10K nodes: ~95ms (P50), ~170ms (P99)

Advantage: 2x faster than Louvain, suitable for real-time use

4. Dijkstra (Shortest Path)

Purpose: Find the shortest path between two nodes.

Use Cases: Route planning, navigation, cost optimization

Algorithm: Priority queue-based shortest path

Example 24: Find Optimal Route

use heliosdb_graph::traversal::dijkstra;

let route = dijkstra(&storage, start_location, end_location).await?;

if let Some(path) = route {
    println!("Optimal route found:");
    println!("  Distance: {:.2} km", path.cost);
    println!("  Stops: {}", path.path.len());

    for (i, location_id) in path.path.iter().enumerate() {
        if let Some(location) = storage.get_vertex(*location_id).await? {
            println!("  {}. {}", i + 1, location.properties.get("name").unwrap());
        }
    }
} else {
    println!("No route found");
}

Performance: 100K nodes: ~8ms (P50), ~15ms (P99)

5. A* (Heuristic Search)

Purpose: Find shortest path using a heuristic for better performance.

Use Cases: Geographic routing, game AI, navigation with coordinates

Algorithm: A* with admissible heuristic function

Example 25: Geographic Routing with A*

use heliosdb_graph::traversal::astar;

// Define Euclidean distance heuristic
let heuristic = |node_a: NodeId, node_b: NodeId| -> f64 {
    // Get node coordinates
    let a = storage.get_vertex(node_a).await.unwrap().unwrap();
    let b = storage.get_vertex(node_b).await.unwrap().unwrap();

    let lat1 = a.properties.get("latitude").unwrap().as_f64().unwrap();
    let lon1 = a.properties.get("longitude").unwrap().as_f64().unwrap();
    let lat2 = b.properties.get("latitude").unwrap().as_f64().unwrap();
    let lon2 = b.properties.get("longitude").unwrap().as_f64().unwrap();

    // Haversine distance
    let r = 6371.0; // Earth radius in km
    let dlat = (lat2 - lat1).to_radians();
    let dlon = (lon2 - lon1).to_radians();
    let a = (dlat / 2.0).sin().powi(2) +
            lat1.to_radians().cos() *
            lat2.to_radians().cos() *
            (dlon / 2.0).sin().powi(2);
    let c = 2.0 * a.sqrt().atan2((1.0 - a).sqrt());
    r * c
};

let path = astar(&storage, start_id, end_id, heuristic).await?;

if let Some(path) = path {
    println!("Route found using A*:");
    println!("  Distance: {:.2} km", path.cost);
    println!("  Nodes explored: {}", path.nodes_explored);
}

Performance: 100K nodes: ~5ms (P50), ~12ms (P99)

Advantage: 30-50% faster than Dijkstra with good heuristic

6. Betweenness Centrality

Purpose: Measure how often a node appears on shortest paths.

Use Cases: Bridge detection, bottleneck analysis, vulnerability assessment

Algorithm: All-pairs shortest paths with path counting

Example 26: Find Bottlenecks

use heliosdb_graph::algorithms::centrality::betweenness_centrality;

let network_nodes: Vec<NodeId> = storage.get_vertices_by_label("Router").await?
    .into_iter()
    .map(|node| node.id)
    .collect();

let centrality = betweenness_centrality(&storage, &network_nodes).await?;

// Find nodes with highest betweenness (potential bottlenecks)
let mut sorted: Vec<_> = centrality.iter().collect();
sorted.sort_by(|a, b| b.1.partial_cmp(a.1).unwrap());

println!("Top bottleneck nodes:");
for (node_id, score) in sorted.iter().take(5) {
    if let Some(node) = storage.get_vertex(**node_id).await? {
        println!("  {} - Betweenness: {:.4}",
                 node.properties.get("name").unwrap(),
                 score);
    }
}

Use Case: Identify critical infrastructure nodes whose failure would impact connectivity

7. Closeness Centrality

Purpose: Measure average distance to all other nodes.

Use Cases: Accessibility analysis, hub detection, efficiency measurement

Algorithm: Average shortest path length from node to all others

Example 27: Find Central Hubs

use heliosdb_graph::algorithms::centrality::closeness_centrality;

let nodes: Vec<NodeId> = storage.get_vertices_by_label("City").await?
    .into_iter()
    .map(|node| node.id)
    .collect();

let centrality = closeness_centrality(&storage, &nodes).await?;

let mut sorted: Vec<_> = centrality.iter().collect();
sorted.sort_by(|a, b| b.1.partial_cmp(a.1).unwrap());

println!("Most central cities (easiest to reach):");
for (node_id, score) in sorted.iter().take(10) {
    if let Some(node) = storage.get_vertex(**node_id).await? {
        println!("  {} - Closeness: {:.4}",
                 node.properties.get("name").unwrap(),
                 score);
    }
}

8. Degree Centrality

Purpose: Count incoming, outgoing, or total connections.

Use Cases: Popularity metrics, connectivity analysis, hub detection

Algorithm: Simple degree counting

Example 28: Find Most Connected Nodes

use heliosdb_graph::algorithms::centrality::{degree_centrality, DegreeMode};

let users: Vec<NodeId> = storage.get_vertices_by_label("User").await?
    .into_iter()
    .map(|node| node.id)
    .collect();

// Outgoing connections (following count)
let following = degree_centrality(&storage, &users, DegreeMode::Out).await?;

// Incoming connections (follower count)
let followers = degree_centrality(&storage, &users, DegreeMode::In).await?;

// Total connections
let total = degree_centrality(&storage, &users, DegreeMode::Total).await?;

// Find users with most followers
let mut sorted_followers: Vec<_> = followers.iter().collect();
sorted_followers.sort_by(|a, b| b.1.partial_cmp(a.1).unwrap());

println!("Users with most followers:");
for (node_id, count) in sorted_followers.iter().take(10) {
    if let Some(node) = storage.get_vertex(**node_id).await? {
        println!("  {} - {} followers",
                 node.properties.get("username").unwrap(),
                 count);
    }
}

Performance: 1M nodes: ~15ms (P50), ~28ms (P99)

9. Eigenvector Centrality

Purpose: Measure influence based on the influence of neighbors.

Use Cases: Authority ranking, influence propagation, quality scoring

Algorithm: Power iteration on adjacency matrix

Example 29: Find Authority Nodes

use heliosdb_graph::algorithms::centrality::eigenvector_centrality;

let papers: Vec<NodeId> = storage.get_vertices_by_label("Paper").await?
    .into_iter()
    .map(|node| node.id)
    .collect();

let centrality = eigenvector_centrality(
    &storage,
    &papers,
    100,    // max iterations
    0.0001  // tolerance
).await?;

let mut sorted: Vec<_> = centrality.iter().collect();
sorted.sort_by(|a, b| b.1.partial_cmp(a.1).unwrap());

println!("Most authoritative papers:");
for (node_id, score) in sorted.iter().take(10) {
    if let Some(node) = storage.get_vertex(**node_id).await? {
        println!("  {} - Authority: {:.4}",
                 node.properties.get("title").unwrap(),
                 score);
    }
}

Note: Similar to PageRank but undamped and sensitive to neighbor influence

10. BFS/DFS Traversal

Purpose: Explore graph structure systematically.

Use Cases: Reachability, connectivity, tree building

Algorithm: Breadth-first or depth-first search

Example 30: BFS Traversal

use heliosdb_graph::traversal::{bfs, BfsOptions};

let options = BfsOptions {
    max_depth: 6,
    max_nodes: 1000000,
    enable_early_termination: false,
    target: None,
};

let result = bfs(&storage, start_id, options).await?;

println!("BFS Traversal Results:");
println!("  Nodes visited: {}", result.total_visited);
println!("  Max depth reached: {}", result.max_depth_reached);
println!("  Execution time: {:?}", result.duration);

// Nodes at each depth level
for (depth, count) in result.depth_distribution {
    println!("  Depth {}: {} nodes", depth, count);
}

Example 31: DFS Traversal with Cycle Detection

use heliosdb_graph::traversal::{dfs, DfsOptions};

let options = DfsOptions {
    max_depth: 100,
    detect_cycles: true,
    enable_early_termination: false,
    target: None,
};

let result = dfs(&storage, start_id, options).await?;

println!("DFS Traversal Results:");
println!("  Nodes visited: {}", result.total_visited);

if !result.cycles.is_empty() {
    println!("  Cycles detected: {}", result.cycles.len());
    for (i, cycle) in result.cycles.iter().enumerate() {
        println!("  Cycle {}: {:?}", i + 1, cycle);
    }
}

Performance:

• BFS (6-degree, 1M nodes): ~78ms (P99)
• DFS (1M nodes): ~65ms (P99)

---

Navigation

• Previous: Graph Patterns
• Next: Use Cases
• Index: Graph Database User Guide

---

Version: 6.5 Last Updated: November 17, 2025