Skip to content

feat: add NeighborhoodAwareCDLP community detection algorithm #825

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
SemyonSinchenko merged 16 commits into from
Jun 9, 2026
Merged

feat: add NeighborhoodAwareCDLP community detection algorithm #825

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
16 commits
Select commit Hold shift + click to select a range
7812cfb
Add NeighborhoodAwareCDLP community detection algorithm
SemyonSinchenko Apr 7, 2026
c132bc7
Apply suggestions from code review
SemyonSinchenko Apr 7, 2026
6a7b577
Update core/src/test/scala/org/graphframes/lib/NeighborhoodAwareCDLPS…
SemyonSinchenko Apr 7, 2026
7845f97
fix: comments
SemyonSinchenko Apr 8, 2026
1378709
fix: new mixin and consolidation
SemyonSinchenko Apr 27, 2026
eb3b3f0
fix: ASF header
SemyonSinchenko Apr 27, 2026
e234cb2
fix: refactoring API
SemyonSinchenko Apr 27, 2026
a80f419
fix: triple brackets
SemyonSinchenko Apr 27, 2026
ee69a70
fix: adjust allowed combinations of args
SemyonSinchenko Apr 27, 2026
2dbd670
fix: fix testing utils
SemyonSinchenko Apr 27, 2026
c2c72c5
fix: update di-graph neighborhoods logic
SemyonSinchenko Apr 27, 2026
14e0750
feat: PySpark bindings
SemyonSinchenko Apr 28, 2026
787fa22
doc: add docs
SemyonSinchenko Apr 28, 2026
5bdc3e1
Merge remote-tracking branch 'graphframes/main' into 791-community-de…
SemyonSinchenko Apr 28, 2026
6469d9a
chore: align internal class name with public API name
SemyonSinchenko Jun 1, 2026
604679a
Merge remote-tracking branch 'graphframes/main' into 791-community-de…
SemyonSinchenko Jun 9, 2026
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
fix: fix testing utils
  • Loading branch information
@SemyonSinchenko
SemyonSinchenko committed Apr 27, 2026
commit 2dbd6705f97144ac25839ec65a73690a7fb2beec
4 changes: 2 additions & 2 deletions core/src/test/scala/org/graphframes/TestUtils.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -22,9 +22,9 @@ object TestUtils {
}

/** Return true if the major and minor versions are greater or eq to constraints */
def requireSparkVersionGT(major: Int, minor: Int, sparkVersion: String): Boolean = {
def requireSparkVersionGE(major: Int, minor: Int, sparkVersion: String): Boolean = {
val (gotMajor, gotMinor) = TestUtils.majorMinorVersion(sparkVersion)
(gotMajor >= major) && (gotMinor >= minor)
(gotMajor > major) || ((gotMajor == major) && (gotMinor >= minor))
}

/**
Expand Down
20 changes: 10 additions & 10 deletions core/src/test/scala/org/graphframes/lib/NeighborhoodAwareCDLPSuite.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -28,7 +28,7 @@ import org.graphframes.TestUtils
class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkContext {

test("basic flow: one iteration propagates strongest incoming label") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark.createDataFrame(Seq(1L, 2L, 3L).map(Tuple1(_))).toDF("id")
val edges = spark.createDataFrame(Seq((1L, 2L), (2L, 3L), (3L, 1L))).toDF("src", "dst")
Expand Down Expand Up @@ -58,7 +58,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC

test(
"different structuralSimilarityMultiplier values can change winner between direct-link mass and common-neighbor overlap") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark
.createDataFrame(Seq((1L, "A"), (2L, "B"), (3L, "B"), (4L, "T"), (7L, "X"), (8L, "Y")))
Expand Down Expand Up @@ -108,7 +108,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("isolated vertex keeps its own ID label") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark.createDataFrame(Seq(1L, 2L, 99L).map(Tuple1(_))).toDF("id")
val edges = spark.createDataFrame(Seq((1L, 2L))).toDF("src", "dst")
Expand All @@ -129,7 +129,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("disconnected graph propagates labels independently per component") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark.createDataFrame(Seq(1L, 2L, 3L, 10L, 11L, 12L).map(Tuple1(_))).toDF("id")
val edges = spark
Expand Down Expand Up @@ -157,7 +157,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("changing only structuralSimilarityMultiplier can flip the winning label") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark
.createDataFrame(Seq((1L, "A"), (2L, "B"), (3L, "B"), (4L, "T"), (7L, "X"), (8L, "Y")))
Expand Down Expand Up @@ -200,7 +200,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("changing ignoreDirectLinks can flip the winning label") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark
.createDataFrame(Seq((1L, "A"), (2L, "B"), (3L, "B"), (4L, "T"), (7L, "X"), (8L, "Y")))
Expand Down Expand Up @@ -246,7 +246,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("setStructuralSimilarityMultiplier allows zero but rejects negative values") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark.createDataFrame(Seq(1L, 2L).map(Tuple1(_))).toDF("id")
val edges = spark.createDataFrame(Seq((1L, 2L))).toDF("src", "dst")
Expand All @@ -260,7 +260,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("zero structuralSimilarityMultiplier is invalid when ignoreDirectLinks is true") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark.createDataFrame(Seq(1L, 2L).map(Tuple1(_))).toDF("id")
val edges = spark.createDataFrame(Seq((1L, 2L))).toDF("src", "dst")
Expand All @@ -276,7 +276,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("setIsDirected(false) changes propagation by adding reverse links") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark.createDataFrame(Seq(1L, 2L).map(Tuple1(_))).toDF("id")
val edges = spark.createDataFrame(Seq((1L, 2L))).toDF("src", "dst")
Expand Down Expand Up @@ -315,7 +315,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("undirected mode matches explicitly symmetrized directed edge set") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val vertices = spark.createDataFrame(Seq(1L, 2L, 3L, 4L).map(Tuple1(_))).toDF("id")
val directedEdges =
Expand Down
8 changes: 4 additions & 4 deletions core/src/test/scala/org/graphframes/lib/TriangleCountSuite.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -150,7 +150,7 @@ class TriangleCountSuite extends SparkFunSuite with GraphFrameTestSparkContext {
}

test("Approximate triangle count") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val edges = spark
.createDataFrame(
Expand All @@ -174,7 +174,7 @@ class TriangleCountSuite extends SparkFunSuite with GraphFrameTestSparkContext {
}

test("Approximate triangle count - no triangles") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val edges = spark.createDataFrame(Seq(0L -> 1L, 1L -> 2L, 3L -> 4L)).toDF("src", "dst")
val g = GraphFrame.fromEdges(edges)
Expand All @@ -187,7 +187,7 @@ class TriangleCountSuite extends SparkFunSuite with GraphFrameTestSparkContext {
}

test("Approximate triangle count - bipartite graph") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val edges =
spark.createDataFrame(Seq(0L -> 2L, 0L -> 3L, 1L -> 2L, 1L -> 3L)).toDF("src", "dst")
Expand All @@ -201,7 +201,7 @@ class TriangleCountSuite extends SparkFunSuite with GraphFrameTestSparkContext {
}

test("Approximate triangle count - large lgNomEntries") {
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))
assume(TestUtils.requireSparkVersionGE(4, 1, spark.version))

val edges = spark.createDataFrame(Seq(0L -> 1L, 1L -> 2L, 2L -> 0L)).toDF("src", "dst")
val g = GraphFrame.fromEdges(edges)
Expand Down
Loading