GraphAcademy

Graph Data Science

Union-Find

The algorithm underlying Full definition for weakly connected components (opens in a new tab)Groups of nodes in which every node is reachable from every other, once relationship direction is ignored. The GDS algorithm that finds them takes the same name.. It holds each Full definition for node (opens in a new tab)A vertex in a graph. In a property graph it can carry labels and properties. in a set, and merges two sets whenever a Full definition for relationship (opens in a new tab)A named, directed connection between two nodes. Every relationship has a type, a start node and an end node. joins them.

Example

Four people, and two relationships read one after the other.

Each person starts in a set of their own, four sets in all. Reading the relationship between Ava and Ben merges their two sets into one. Reading the relationship between Cleo and Dan merges theirs. Nothing joins one pair to the other, so two sets are left.

cypher
CALL gds.wcc.stream('people')
YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS person, componentId

Ava and Ben come back with one componentId, Cleo and Dan with another.

Lessons that use this term

The lesson and course links below open in a new tab.

One lesson uses this term.

Graph Data Science in Practice3 mentions

  • Degree Centrality & WCCCommunity Detection for Frauddegree centrality with different orientations and weights Explain the Union-Find algorithm underlying WCC Configure WCC with thresholds, seeding, and performance optimizations Choose between3 mentions

Related terms

weakly connected components
Groups of nodes in which every node is reachable from every other, once relationship direction is ignored. The GDS algorithm that finds them takes the same name.1 shared lesson
modularity
A score for how much more densely connected the nodes within a group are than they would be by chance.1 shared lesson
undirected relationship
A relationship with no direction. Neo4j GDS represents them as parallel relationships in opposite directions.1 shared lesson
Louvain algorithm
A community detection algorithm that repeatedly merges nodes into groups for as long as merging raises modularity.1 shared lesson
bipartite graph
A graph with two kinds of node, where every relationship joins one kind to the other and never two of the same kind.1 shared lesson
centrality
How important a node is within a graph. Each centrality algorithm defines importance differently.1 shared lesson
degree centrality
A score for each node equal to its number of outgoing relationships.1 shared lesson
graph data science
Analysing data through the structure of its connections. Also the name of the Neo4j library that implements it.1 shared lesson

All glossary terms