vesoft-inc / vesoft-inc/nebula-java
Louvain Step 2 appears to drop isolated nodes
Nobody has claimed this yet.
- Dominant language
- Java
- Stars
- 199
- Forks
- 125
- Avg merge
- 5h 6m
- Merged PRs (30d)
- 3
Description
Louvain Step 2 appears to construct the community graph by only considering Edges that connect different communities. See lines 146-155 in source
This means that any isolated nodes (or disconnected communities) in the graph are eliminated from results. Instead they should be their own communities. Isolated nodes should be connected as self-edges in Step 2.
Steps to reproduce the behavior:
Consider Practice Problem at https://www.nebula-graph.io/posts/practice-graphx-nebula-graph-algorithm. Add a couple of "disconnected" vertices to that graph (edge between node 20 and 21) via an edge set like this:
val nebSample = mySess.createDataFrame(Seq(
(0, 2, 1),
(0, 3, 1),
(0, 4, 1),
(0, 5, 1),
(1, 4, 1),
(1, 2, 1),
(1, 7, 1),
(2, 4, 1),
(2, 6, 1),
(2, 5, 1),
(3, 7, 1),
(4, 10, 1),
(5, 7, 1),
(5, 11, 1),
(6, 7, 1),
(6, 11, 1),
(8, 9, 1),
(8, 10, 1),
(8, 11, 1),
(8, 14, 1),
(8, 15, 1),
(9, 14, 1),
(9, 12, 1),
(10, 12 ,1),
(10, 13, 1),
(10, 14, 1),
(11, 13, 1),
(20, 21, 1)
)
).toDF("v1", "v2", "weight")
Expected behavior
Community 20 with a pair of vertices (20, 21) in INNERVERTICES array should appear
Instead, community 20 is excluded from results
Additional context
I have designed an approach to Phase 2 that fixes this problem if you are interested...
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in nebula-algorithm/src/main/scala/com/vesoft/nebula/algorithm/lib/LouvainAlgo.scala, especially lines 146-155, and reproduce the issue with the provided edge set containing vertices 20 and 21. Trace how Step 2 builds the community graph and verify that the resulting INNERVERTICES includes community 20 with both vertices.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- scala
- Domain
- data
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 45/100