Walktrap: graphs with isolated vertices are not accepted
Bug #1066081 reported by
Christopher Lu
This bug affects 1 person
| Affects | Status | Importance | Assigned to | Milestone | |
|---|---|---|---|---|---|
| igraph |
Fix Released
|
Medium
|
Tamás Nepusz | ||
Bug Description
Walktrap does not operate on graphs with isolated vertices; why is this not allowed? It can handle graphs with multiple connected components, so it makes sense for isolated vertices to be handled the same way.
The algorithm itself appears to be able to handle this, but the conversion from an igraph graph will divide by zero when calculating the average edge weight for the loop edge. For isolated vertices, the weight of the loop edge doesn't matter.
A patch against top of trunk implementing the necessary change is attached.
Revision history for this message
| Christopher Lu (9e9o1ko8b2f5xpiibgscjzlhu-chris-0zxvj9hhx1hzo5xiyhxz186cr) wrote | #1 |
Revision history for this message
| Tamás Nepusz (ntamas) wrote | #2 |
| Changed in igraph: | |
| status: | New → In Progress |
| importance: | Undecided → Medium |
| assignee: | nobody → Tamás Nepusz (ntamas) |
| milestone: | none → 0.6.1 |
Revision history for this message
| Tamás Nepusz (ntamas) wrote | #3 |
| Changed in igraph: | |
| status: | In Progress → Fix Committed |
| Changed in igraph: | |
| status: | Fix Committed → Fix Released |
Revision history for this message
| Gábor Csárdi (gabor.csardi) wrote Continue on github | #4 |
To post a comment you must log in.
The original implementation of the walktrap method from Pascal Pons did not allow isolated vertices either and we just replaced the error message in his code with an appropriate igraph error code. I'll read the paper once again to see that it really doesn't matter and if so, I'll merge your patch. Thanks!