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: comments
  • Loading branch information
@SemyonSinchenko
SemyonSinchenko committed Apr 8, 2026
commit 7845f9739adc59e4ab41600be87c44fe0e494390
2 changes: 0 additions & 2 deletions core/src/main/scala/org/graphframes/lib/NeighborhoodAwareCDLP.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -25,7 +25,6 @@ import org.graphframes.GraphFrame
import org.graphframes.GraphFrame.*
import org.graphframes.GraphFramesSparkVersionException
import org.graphframes.Logging
import org.graphframes.WithAlgorithmChoice
import org.graphframes.WithCheckpointInterval
import org.graphframes.WithDirection
import org.graphframes.WithIntermediateStorageLevel
Expand Down Expand Up @@ -67,7 +66,6 @@ import org.graphframes.WithMaxIter
*/
class NeighborhoodAwareCDLP private[graphframes] (private val graph: GraphFrame)
extends Arguments
with WithAlgorithmChoice
with WithCheckpointInterval
with WithMaxIter
with WithLocalCheckpoints
Expand Down
6 changes: 6 additions & 0 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 @@ -21,6 +21,12 @@ 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 = {
val (gotMajor, gotMinor) = TestUtils.majorMinorVersion(sparkVersion)
(gotMajor >= major) && (gotMinor >= minor)
Comment thread
SemyonSinchenko marked this conversation as resolved.
Outdated
}

/**
* Check whether the given schema contains a column of the required data type.
*
Expand Down
22 changes: 8 additions & 14 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 @@ -10,14 +10,8 @@ import org.graphframes.TestUtils

class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkContext {

private def requireSpark41OrHigher(): Unit = {
val (major, minor) = TestUtils.majorMinorVersion(spark.version)
assume((major, minor) >= ((4, 1)))
()
}

test("basic flow: one iteration propagates strongest incoming label") {
requireSpark41OrHigher()
assume(TestUtils.requireSparkVersionGT(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 @@ -47,7 +41,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC

test(
"different a/c weights change winner between direct-link mass and common-neighbor overlap") {
requireSpark41OrHigher()
assume(TestUtils.requireSparkVersionGT(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 @@ -94,7 +88,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("isolated vertex keeps its own ID label") {
requireSpark41OrHigher()
assume(TestUtils.requireSparkVersionGT(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 @@ -115,7 +109,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("disconnected graph propagates labels independently per component") {
requireSpark41OrHigher()
assume(TestUtils.requireSparkVersionGT(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 @@ -143,7 +137,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("changing only c can flip the winning label") {
requireSpark41OrHigher()
assume(TestUtils.requireSparkVersionGT(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 @@ -184,7 +178,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("changing only a can flip the winning label") {
requireSpark41OrHigher()
assume(TestUtils.requireSparkVersionGT(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 @@ -225,7 +219,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

test("setIsDirected(false) changes propagation by adding reverse links") {
requireSpark41OrHigher()
assume(TestUtils.requireSparkVersionGT(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 @@ -264,7 +258,7 @@ class NeighborhoodAwareCDLPSuite extends SparkFunSuite with GraphFrameTestSparkC
}

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

val vertices = spark.createDataFrame(Seq(1L, 2L, 3L, 4L).map(Tuple1(_))).toDF("id")
val directedEdges =
Expand Down
12 changes: 4 additions & 8 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,8 +150,7 @@ class TriangleCountSuite extends SparkFunSuite with GraphFrameTestSparkContext {
}

test("Approximate triangle count") {
val sparkVersion = spark.version
assume(sparkVersion.substring(0, 3) >= "4.1")
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))

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

test("Approximate triangle count - no triangles") {
val sparkVersion = spark.version
assume(sparkVersion.substring(0, 3) >= "4.1")
assume(TestUtils.requireSparkVersionGT(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 @@ -189,8 +187,7 @@ class TriangleCountSuite extends SparkFunSuite with GraphFrameTestSparkContext {
}

test("Approximate triangle count - bipartite graph") {
val sparkVersion = spark.version
assume(sparkVersion.substring(0, 3) >= "4.1")
assume(TestUtils.requireSparkVersionGT(4, 1, spark.version))

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

test("Approximate triangle count - large lgNomEntries") {
val sparkVersion = spark.version
assume(sparkVersion.substring(0, 3) >= "4.1")
assume(TestUtils.requireSparkVersionGT(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