search

neo4j-contrib / neo4j-graph-algorithms

Efficient Graph Algorithms for Neo4j
https://github.com/neo4j/graph-data-science/
GNU General Public License v3.0
767 stars 196 forks source link

LPA: add random option to pick the smallest label #901

Closed szarnyasg closed 4 years ago

szarnyasg commented 5 years ago

cc @jexp and @knutwalker

This issue is based on the discussion started in PR #858. My starting post was:

I was recently looking into LPA again, for using it in the LDBC Graphalytics benchmark. LPA docs says that:

At every iteration of propagation, each node updates its label to the one that the maximum numbers of its neighbours belongs to. Ties are broken uniformly and randomly. The Graphalytics benchmark requires deterministic execution, so in case of a tie, the smallest label wins. According to the benchmark specification:

image

Do you think it's possible to support such an approach to achieve determinism?

AliciaFrame commented 4 years ago

This has been addressed in the most recent release (3.5.8.0) - see the release notes here. Its currently available on our download center, but the code has not yet been open sourced on the repo.

szarnyasg commented 4 years ago

@AliciaFrame thanks! I'll run our validation on the new procedure once it's in the Maven Central.