Community Detection

Overview

Community detection algorithms identify groups of densely connected nodes. These clusters often represent real-world communities, topics, or organizational units.

Louvain Algorithm

The Louvain algorithm detects communities by optimizing modularity. It's highly scalable and produces hierarchical community structures.

Detect communities in social network:

GQL
CALL algo.louvain('Person', 'KNOWS')
YIELD nodeId, communityId
MATCH (p:Person) WHERE id(p) = nodeId
RETURN communityId, COLLECT_LIST(p.name) AS members, COUNT(*) AS size
ORDER BY size DESC

Hierarchical communities:

GQL
CALL algo.louvain('Person', 'KNOWS', {
  includeIntermediateCommunities: true
})
YIELD nodeId, communityId, intermediateCommunityIds
MATCH (p:Person) WHERE id(p) = nodeId
RETURN p.name, communityId AS finalCommunity,
       intermediateCommunityIds AS hierarchy

Adjust community granularity:

GQL
CALL algo.louvain('Person', 'KNOWS', {
  resolution: 2.0  // More, smaller communities
})
YIELD nodeId, communityId
MATCH (p:Person) WHERE id(p) = nodeId
RETURN communityId, COUNT(*) AS size
ORDER BY size DESC

Store community assignments:

GQL
CALL algo.louvain('Person', 'KNOWS', {
  writeProperty: 'community'
})
YIELD communityCount, modularity

// Query by community
MATCH (p:Person)
WHERE p.community = 1
RETURN p.name

Weighted community detection:

GQL
CALL algo.louvain('Person', 'INTERACTS', {
  relationshipWeightProperty: 'strength'
})
YIELD nodeId, communityId
MATCH (p:Person) WHERE id(p) = nodeId
RETURN communityId, COLLECT_LIST(p.name) AS members

Label Propagation

Label Propagation is a fast, near-linear time algorithm. Nodes adopt the most frequent label among their neighbors until convergence.

Fast community detection:

GQL
CALL algo.labelPropagation('Person', 'KNOWS')
YIELD nodeId, communityId
MATCH (p:Person) WHERE id(p) = nodeId
RETURN communityId, COLLECT_LIST(p.name) AS members
ORDER BY SIZE(members) DESC

Seed with initial labels:

GQL
MATCH (p:Person)
WHERE p.department IS NOT NULL
SET p.seedLabel = p.department

CALL algo.labelPropagation('Person', 'KNOWS', {
  seedProperty: 'seedLabel'
})
YIELD nodeId, communityId
MATCH (p:Person) WHERE id(p) = nodeId
RETURN communityId, COLLECT_LIST(p.name) AS members

Limit iterations:

GQL
CALL algo.labelPropagation('Person', 'KNOWS', {
  maxIterations: 10
})
YIELD nodeId, communityId, didConverge
RETURN communityId, COUNT(*) AS size, didConverge

Connected Components

Connected components identify isolated subgraphs where all nodes can reach each other. Weakly connected ignores edge direction; strongly connected requires paths in both directions.

Find weakly connected components:

GQL
CALL algo.wcc('Person', 'KNOWS')
YIELD nodeId, componentId
MATCH (p:Person) WHERE id(p) = nodeId
RETURN componentId, COLLECT_LIST(p.name) AS members, COUNT(*) AS size
ORDER BY size DESC

Find strongly connected components (directed):

GQL
CALL algo.scc('Person', 'FOLLOWS')
YIELD nodeId, componentId
MATCH (p:Person) WHERE id(p) = nodeId
RETURN componentId, COLLECT_LIST(p.name) AS members
ORDER BY SIZE(members) DESC

Find isolated nodes:

GQL
CALL algo.wcc('Person', 'KNOWS')
YIELD nodeId, componentId
WITH componentId, COLLECT_LIST(nodeId) AS nodeIds
WHERE SIZE(nodeIds) = 1
MATCH (p:Person) WHERE id(p) IN nodeIds
RETURN p.name AS isolatedNode

Component statistics:

GQL
CALL algo.wcc.stats('Person', 'KNOWS')
YIELD componentCount, nodeCount, minComponentSize, maxComponentSize
RETURN componentCount, nodeCount,
       minComponentSize, maxComponentSize

Triangle Count & Clustering

Triangle counting measures local clustering. Nodes with high triangle counts are well-embedded in tight-knit groups. The clustering coefficient indicates network density.

Count triangles per node:

GQL
CALL algo.triangleCount('Person', 'KNOWS')
YIELD nodeId, triangleCount, coefficient
MATCH (p:Person) WHERE id(p) = nodeId
RETURN p.name, triangleCount, coefficient
ORDER BY triangleCount DESC
LIMIT 10

Global clustering coefficient:

GQL
CALL algo.triangleCount.stats('Person', 'KNOWS')
YIELD globalTriangleCount, averageClusteringCoefficient
RETURN globalTriangleCount, averageClusteringCoefficient

Find tightly-knit groups:

GQL
CALL algo.triangleCount('Person', 'KNOWS')
YIELD nodeId, coefficient
MATCH (p:Person) WHERE id(p) = nodeId
WHERE coefficient > 0.7
RETURN p.name, p.department, coefficient AS clustering
ORDER BY clustering DESC

Native GQL triangle pattern matching:

GQL
MATCH (a:Person)-[:KNOWS]-(b:Person)-[:KNOWS]-(c:Person)-[:KNOWS]-(a)
WHERE id(a) < id(b) AND id(b) < id(c)  // Avoid counting same triangle 3x
RETURN a.name, b.name, c.name