Tag: Graph Algorithms & Analytics

C(v) = 2 × |{(u,w) : u,w ∈ N(v) ∧ (u,w) ∈ E}| / (deg(v) × (deg(v) - 1))

-- Find shortest path between two nodes
MATCH path = shortestPath(
  (start:Location {name: 'New York'})-[:ROUTE*]-(end:Location {name: 'Los Angeles'})
)
RETURN path, length(path) as hops;

-- Weighted shortest path
MATCH path = shortestPath(
  (start:Location {name: 'New York'})-[r:ROUTE*]-(end:Location {name: 'Los Angeles'})
)
RETURN path, reduce(dist = 0, rel in relationships(path) | dist + rel.distance) as total_distance;

-- Find all shortest paths (when multiple exist)
MATCH paths = allShortestPaths(
  (a:Person {id: 123})-[:KNOWS*]-(b:Person {id: 456})
)
RETURN paths, length(paths) as path_length;

-- Find top K shortest paths
MATCH path = (start:City {name: 'Boston'})-[:CONNECTED*1..10]-(end:City {name: 'Seattle'})
WITH path, reduce(cost = 0, r in relationships(path) | cost + r.weight) as total_cost
ORDER BY total_cost
LIMIT 5
RETURN path, total_cost;

-- Calculate in-degree (followers)
MATCH (u:User)
OPTIONAL MATCH (u)<-[:FOLLOWS]-(follower:User)
RETURN u.name, count(follower) as in_degree
ORDER BY in_degree DESC
LIMIT 10;

-- Out-degree (following)
MATCH (u:User)
OPTIONAL MATCH (u)-[:FOLLOWS]->(following:User)
RETURN u.name, count(following) as out_degree
ORDER BY out_degree DESC;

-- Total degree
MATCH (u:User)
OPTIONAL MATCH (u)-[:KNOWS]-(connected:User)
RETURN u.name, count(DISTINCT connected) as degree
ORDER BY degree DESC;

-- Simplified betweenness calculation
MATCH (n:Person)
MATCH path = shortestPath((a:Person)-[:KNOWS*]-(b:Person))
WHERE n IN nodes(path) AND a <> n AND b <> n
WITH n, count(path) as paths_through
RETURN n.name, paths_through
ORDER BY paths_through DESC
LIMIT 10;

-- Measure how close a node is to all others
MATCH (u:User {id: 123})
MATCH path = shortestPath((u)-[:KNOWS*]-(other:User))
WHERE other <> u
WITH u, avg(length(path)) as avg_distance
RETURN u.name, 1.0 / avg_distance as closeness_centrality;

-- Simplified PageRank-style scoring
MATCH (u:User)<-[:FOLLOWS]-(follower:User)
WITH u, count(follower) as direct_followers
MATCH (follower)<-[:FOLLOWS]-(indirect:User)
RETURN
  u.name,
  direct_followers,
  count(DISTINCT indirect) as indirect_reach,
  direct_followers * 1.0 + count(DISTINCT indirect) * 0.15 as influence_score
ORDER BY influence_score DESC;

-- Account for follower quality
MATCH (u:User)<-[f:FOLLOWS]-(follower:User)
OPTIONAL MATCH (follower)<-[:FOLLOWS]-(follower_of_follower:User)
WITH u, follower, count(follower_of_follower) as follower_influence
RETURN
  u.name,
  sum(follower_influence) as weighted_influence
ORDER BY weighted_influence DESC;

-- Find connected components
MATCH (start:User {id: 123})-[:KNOWS*]-(connected:User)
RETURN collect(DISTINCT connected.id) as community_members,
       count(DISTINCT connected) as community_size;

-- Count triangles (A knows B, B knows C, C knows A)
MATCH (a:User)-[:KNOWS]->(b:User)-[:KNOWS]->(c:User)-[:KNOWS]->(a)
RETURN count(*) / 3 as triangle_count;

-- Local clustering coefficient
MATCH (u:User {id: 123})-[:KNOWS]-(neighbor:User)
WITH u, collect(DISTINCT neighbor) as neighbors, count(DISTINCT neighbor) as degree
UNWIND neighbors as n1
UNWIND neighbors as n2
MATCH (n1)-[r:KNOWS]-(n2)
WHERE n1 <> n2
WITH u, degree, count(DISTINCT r) as connected_pairs
RETURN u.name,
       degree,
       connected_pairs * 2.0 / (degree * (degree - 1)) as clustering_coefficient;

-- Simplified label propagation
MATCH (u:User)-[:KNOWS]-(neighbor:User)
WITH u, neighbor.community_id as neighbor_community, count(*) as freq
ORDER BY freq DESC
LIMIT 1
SET u.community_id = neighbor_community
RETURN u.name, u.community_id;

-- Find similar users by shared connections
MATCH (u1:User {id: 123})-[:FOLLOWS]->(common:User)<-[:FOLLOWS]-(u2:User)
WHERE u1 <> u2
WITH u1, u2, count(DISTINCT common) as common_count
MATCH (u1)-[:FOLLOWS]->(u1_following:User)
MATCH (u2)-[:FOLLOWS]->(u2_following:User)
WITH u1, u2, common_count,
     count(DISTINCT u1_following) as u1_total,
     count(DISTINCT u2_following) as u2_total
RETURN u2.name,
       common_count * 1.0 / (u1_total + u2_total - common_count) as jaccard_similarity
ORDER BY jaccard_similarity DESC
LIMIT 10;

-- Recommend products based on similar users' purchases
MATCH (u:User {id: 123})-[:PURCHASED]->(p:Product)<-[:PURCHASED]-(similar:User)
WHERE similar <> u
WITH similar, count(DISTINCT p) as common_purchases
ORDER BY common_purchases DESC
LIMIT 50
MATCH (similar)-[:PURCHASED]->(recommendation:Product)
WHERE NOT EXISTS {(u)-[:PURCHASED]->(recommendation)}
RETURN recommendation.name,
       count(*) as recommendation_score
ORDER BY recommendation_score DESC
LIMIT 10;

-- Compare users by behavior vectors
MATCH (u1:User {id: 123})-[r1:RATED]->(item:Product)<-[r2:RATED]-(u2:User)
WHERE u1 <> u2
WITH u1, u2,
     sum(r1.rating * r2.rating) as dot_product,
     sqrt(sum(r1.rating * r1.rating)) as u1_magnitude,
     sqrt(sum(r2.rating * r2.rating)) as u2_magnitude
RETURN u2.name,
       dot_product / (u1_magnitude * u2_magnitude) as cosine_similarity
ORDER BY cosine_similarity DESC;

-- Explore network level by level
MATCH path = (start:User {id: 123})-[:KNOWS*1..4]-(connected:User)
RETURN connected.name, length(path) as distance
ORDER BY distance, connected.name;

-- Deep exploration of paths
MATCH path = (start:User {id: 123})-[:FOLLOWS*1..5]->(reached:User)
RETURN DISTINCT reached.name, length(path) as depth
ORDER BY depth DESC, reached.name;

-- Find cycles in the graph
MATCH path = (n:Node)-[:CONNECTS*]->(n)
WHERE length(path) > 1
RETURN path, length(path) as cycle_length
ORDER BY cycle_length
LIMIT 10;

-- Simplified max flow calculation
MATCH path = (source:Node {id: 'A'})-[r:PIPE*]->(sink:Node {id: 'B'})
WITH path, reduce(flow = 999999, rel in relationships(path) |
  CASE WHEN rel.capacity < flow THEN rel.capacity ELSE flow END
) as path_capacity
RETURN path, path_capacity
ORDER BY path_capacity DESC;

-- Connect all nodes with minimum total edge weight
MATCH (n:Location)
WITH collect(n) as nodes
MATCH path = (a:Location)-[r:ROAD]-(b:Location)
WHERE a IN nodes AND b IN nodes
RETURN path, r.distance as weight
ORDER BY weight;

-- Find users with anomalous behavior
MATCH (u:User)
OPTIONAL MATCH (u)-[:PURCHASED]->(p:Product)
WITH u, count(p) as purchase_count,
     avg(p.price) as avg_spend
WITH avg(purchase_count) as avg_purchases,
     stddev(purchase_count) as stddev_purchases,
     avg(avg_spend) as global_avg_spend,
     stddev(avg_spend) as stddev_spend
MATCH (u:User)
OPTIONAL MATCH (u)-[:PURCHASED]->(p:Product)
WITH u, count(p) as user_purchases, avg(p.price) as user_avg_spend,
     avg_purchases, stddev_purchases, global_avg_spend, stddev_spend
WHERE abs(user_purchases - avg_purchases) > 3 * stddev_purchases
   OR abs(user_avg_spend - global_avg_spend) > 3 * stddev_spend
RETURN u.name, user_purchases, user_avg_spend;

-- Identify tightly connected suspicious accounts
MATCH (suspect:Account {flagged: true})-[:TRANSACTED_WITH*1..2]-(connected:Account)
WITH suspect, collect(DISTINCT connected) as ring_members
WHERE size(ring_members) > 5
MATCH (m1:Account)-[:TRANSACTED_WITH]-(m2:Account)
WHERE m1 IN ring_members AND m2 IN ring_members
RETURN suspect.id, ring_members, count(*) as internal_transactions
ORDER BY internal_transactions DESC;

-- Calculate graph diameter
MATCH path = shortestPath((a:Node)-[*]-(b:Node))
WHERE a < b
RETURN max(length(path)) as diameter;

-- Calculate graph density
MATCH (n:Node)
WITH count(n) as node_count
MATCH ()-[r:EDGE]-()
RETURN count(r) * 1.0 / (node_count * (node_count - 1)) as density;

-- Analyze degree distribution
MATCH (n:Node)
OPTIONAL MATCH (n)-[r]-(m:Node)
WITH n, count(r) as degree
RETURN degree, count(n) as node_count
ORDER BY degree;

-- Always bound variable-length patterns
MATCH path = (a)-[*1..6]-(b)  -- Good: bounded
-- MATCH path = (a)-[*]-(b)   -- Bad: unbounded
RETURN path;

-- Filter before expensive traversals
MATCH (start:User)
WHERE start.active = true  -- Filter first
  AND start.country = 'US'
MATCH path = (start)-[:KNOWS*1..3]-(connected:User)
RETURN path;

-- Start with indexed lookups
CREATE INDEX user_id ON :User(id);

MATCH (u:User {id: 123})  -- Uses index
MATCH path = (u)-[:FOLLOWS*1..4]->(reached:User)
RETURN path;

-- Break large computations into batches
MATCH (u:User)
WHERE u.id >= 0 AND u.id < 1000  -- Batch 1
WITH u
MATCH (u)-[:KNOWS]-(friend:User)
RETURN u.id, count(friend) as degree;

-- Initialize distance matrix
MATCH (source:Node), (target:Node)
WHERE source <> target
MERGE (source)-[d:DISTANCE]->(target)
SET d.distance = CASE
    WHEN EXISTS((source)-[:CONNECTED]-(target)) THEN 1
    ELSE 999999
END;

-- Floyd-Warshall iterations
MATCH (i:Node), (j:Node), (k:Node)
WHERE i <> j AND j <> k AND i <> k
MATCH (i)-[ij:DISTANCE]->(j)
MATCH (i)-[ik:DISTANCE]->(k)
MATCH (k)-[kj:DISTANCE]->(j)
WITH i, j, ij, ik.distance + kj.distance AS new_distance
WHERE new_distance < ij.distance
SET ij.distance = new_distance;

-- Query all-pairs distances
MATCH (a:Node {id: $node_a})-[d:DISTANCE]->(b:Node {id: $node_b})
RETURN a.id, b.id, d.distance AS shortest_distance;

-- Initialize distances
MATCH (n:Node)
SET n.distance = CASE
    WHEN n.id = $source_id THEN 0
    ELSE 999999
END;

-- Relax edges V-1 times
MATCH (u:Node)-[r:EDGE]->(v:Node)
WHERE u.distance + r.weight < v.distance
SET v.distance = u.distance + r.weight,
    v.predecessor = u.id;

-- Detect negative cycles
MATCH (u:Node)-[r:EDGE]->(v:Node)
WHERE u.distance + r.weight < v.distance
RETURN 'Negative cycle detected' AS warning, u.id, v.id;

-- Extract shortest path
MATCH (target:Node {id: $target_id})
WITH target.id AS current_id, [] AS path
CALL {
    WITH current_id, path
    MATCH (n:Node {id: current_id})
    WHERE n.predecessor IS NOT NULL
    WITH n.predecessor AS pred, path + [current_id] AS new_path
    RETURN pred AS next_id, new_path AS result_path
}
RETURN result_path AS shortest_path;

-- Initialize node state
MATCH (n:Node)
SET n.index = null,
    n.lowlink = null,
    n.on_stack = false;

-- Recursive DFS for SCC detection
MATCH (v:Node)
WHERE v.index IS NULL
CALL {
    WITH v
    SET v.index = $current_index,
        v.lowlink = $current_index,
        v.on_stack = true
    WITH v, $current_index + 1 AS next_index

    MATCH (v)-[:EDGE]->(w:Node)
    CALL {
        WITH w, next_index
        CASE
            WHEN w.index IS NULL THEN
                // Recurse
                SET w.index = next_index
            WHEN w.on_stack = true THEN
                // Update lowlink
                SET v.lowlink = CASE
                    WHEN w.index < v.lowlink THEN w.index
                    ELSE v.lowlink
                END
        END
    }

    // If v is root of SCC
    WITH v
    WHERE v.lowlink = v.index
    MATCH (w:Node)
    WHERE w.on_stack = true AND w.index >= v.index
    SET w.component_id = v.id,
        w.on_stack = false
    RETURN v.id AS scc_root
};

-- Query component membership
MATCH (n:Node)
WHERE n.component_id IS NOT NULL
RETURN n.component_id AS component,
       COUNT(n) AS size,
       COLLECT(n.id) AS members
ORDER BY size DESC;

-- Initialize residual graph
MATCH (u:Node)-[e:EDGE]->(v:Node)
MERGE (u)-[forward:RESIDUAL {capacity: e.capacity, flow: 0}]->(v)
MERGE (v)-[backward:RESIDUAL {capacity: 0, flow: 0}]->(u);

-- Augmenting path search (BFS)
WITH $source_id AS source, $sink_id AS sink
MATCH path = shortestPath((s:Node {id: source})-[:RESIDUAL*]->(t:Node {id: sink}))
WHERE ALL(r IN relationships(path) WHERE r.capacity - r.flow > 0)
WITH path,
     REDUCE(min_cap = 999999, r IN relationships(path) |
         CASE WHEN r.capacity - r.flow < min_cap
              THEN r.capacity - r.flow
              ELSE min_cap
         END
     ) AS bottleneck
WITH path, bottleneck
UNWIND relationships(path) AS edge
SET edge.flow = edge.flow + bottleneck
WITH path, bottleneck
MATCH (u)-[forward:RESIDUAL]->(v)
WHERE forward IN relationships(path)
MATCH (v)-[backward:RESIDUAL]->(u)
SET backward.capacity = backward.capacity + bottleneck;

-- Extract max flow value
MATCH (:Node {id: $source_id})-[r:RESIDUAL]->()
RETURN SUM(r.flow) AS max_flow_value;

-- Parallel PageRank with batch updates
MATCH (n:Node)
WITH COUNT(n) AS total_nodes
SET n.pagerank = 1.0 / total_nodes;

-- Process in parallel batches
MATCH (n:Node)
WITH n, n.id % 10 AS partition_id
CALL {
    WITH n, partition_id
    MATCH (n)-[:EDGE]->(neighbor:Node)
    WITH neighbor,
         SUM(n.pagerank / COUNT { (n)-[:EDGE]->() }) AS incoming_rank
    SET neighbor.pagerank_new = 0.15 + 0.85 * incoming_rank
} IN TRANSACTIONS OF 100000 ROWS
PER PARTITION (partition_id);

-- Parallel strongly-connected component detection
MATCH (n:Node)
CALL {
    WITH n
    MATCH path = (n)-[:EDGE*]->(n)
    WITH n, COLLECT(DISTINCT [node IN nodes(path) | ID(node)]) AS cycles
    SET n.scc_candidates = cycles
} IN TRANSACTIONS OF 10000 ROWS;

-- Approximate betweenness centrality (sample-based)
WITH 100 AS sample_size  // Sample 100 random nodes instead of all pairs
MATCH (sample:Node)
WITH sample
ORDER BY rand()
LIMIT $sample_size

MATCH path = shortestPath((sample)-[:EDGE*]-(target:Node))
WHERE sample <> target
WITH nodes(path) AS path_nodes
UNWIND path_nodes AS node
WHERE node <> path_nodes[0] AND node <> path_nodes[-1]
WITH node, COUNT(*) AS sampled_betweenness
RETURN node.id,
       sampled_betweenness * ($total_nodes / $sample_size) AS estimated_betweenness
ORDER BY estimated_betweenness DESC;

-- Incremental PageRank after edge addition
MATCH (u:Node {id: $new_source}), (v:Node {id: $new_target})
MERGE (u)-[:EDGE]->(v);

-- Localized update (affected nodes only)
MATCH (affected:Node)
WHERE affected IN [u, v]
   OR EXISTS((affected)-[:EDGE*1..2]-(u))
   OR EXISTS((affected)-[:EDGE*1..2]-(v))
WITH affected
MATCH (affected)-[:EDGE]->(neighbor:Node)
WITH neighbor,
     SUM(affected.pagerank / COUNT { (affected)-[:EDGE]->() }) AS delta
SET neighbor.pagerank = neighbor.pagerank + 0.85 * delta,
    neighbor.needs_full_recompute = false;

-- Incremental community detection after node addition
MATCH (new_node:Node {id: $new_node_id})
MATCH (new_node)-[:EDGE]-(neighbor:Node)
WITH neighbor.community AS candidate_community, COUNT(*) AS connections
ORDER BY connections DESC
LIMIT 1
SET new_node.community = candidate_community;

-- Streaming BFS for large graphs
WITH $start_id AS start_id, 0 AS level
CALL {
    WITH start_id, level
    MATCH (current:Node {id: start_id})
    SET current.level = level
    RETURN current.id AS processed_id
}

WITH level + 1 AS next_level
CALL {
    WITH next_level
    MATCH (current:Node)-[:EDGE]->(next:Node)
    WHERE current.level = next_level - 1
      AND next.level IS NULL
    SET next.level = next_level
    RETURN COUNT(next) AS nodes_at_level
} IN TRANSACTIONS OF 50000 ROWS

RETURN next_level AS level, nodes_at_level;

-- Benchmark PageRank iterations
WITH datetime() AS start_time
MATCH (n:Node)
SET n.pagerank = 1.0 / COUNT { MATCH (m:Node) };

// Run 20 iterations
WITH start_time, range(1, 20) AS iterations
UNWIND iterations AS iter
CALL {
    MATCH (source:Node)-[:EDGE]->(target:Node)
    WITH target, SUM(source.pagerank / COUNT { (source)-[:EDGE]->() }) AS rank
    SET target.pagerank_new = 0.15 + 0.85 * rank
}
MATCH (n:Node)
SET n.pagerank = n.pagerank_new
REMOVE n.pagerank_new

WITH start_time, datetime() AS end_time
RETURN duration.between(start_time, end_time).milliseconds AS runtime_ms,
       runtime_ms / 20.0 AS ms_per_iteration;

-- Memory usage profiling
CALL dbms.memory.usage()
YIELD used, total, peak
RETURN used / 1024 / 1024 AS used_mb,
       total / 1024 / 1024 AS total_mb,
       peak / 1024 / 1024 AS peak_mb;

-- Track PageRank convergence
WITH [] AS convergence_history
MATCH (n:Node)
WITH convergence_history + [n.pagerank] AS history

// After iteration
MATCH (n:Node)
WITH history, n.pagerank_new - n.pagerank AS delta
WITH AVG(ABS(delta)) AS mean_change,
     MAX(ABS(delta)) AS max_change,
     STDDEV(ABS(delta)) AS stddev_change
RETURN mean_change,
       max_change,
       stddev_change,
       CASE WHEN mean_change < 0.0001 THEN 'CONVERGED' ELSE 'CONTINUE' END AS status;

-- Bank exposure network analysis
MATCH (bank:Bank)-[exp:EXPOSURE]->(counterparty:Bank)
WITH bank,
     SUM(exp.amount) AS total_exposure,
     bank.capital AS capital
WITH bank,
     total_exposure / capital AS leverage_ratio
WHERE leverage_ratio > 10.0
MATCH path = (bank)-[:EXPOSURE*1..3]->(systemic:Bank)
WHERE systemic.systemically_important = true
RETURN bank.name,
       leverage_ratio,
       COUNT(DISTINCT path) AS contagion_paths,
       SUM([r IN relationships(path) | r.amount]) AS total_risk
ORDER BY total_risk DESC;