dice-group / dice-group/Lemming

Bug: NumberOfTrianglesMetric computes wrong results in some cases

Open
#3 2 comments 1 reaction 1 assignee Claimed by @MichaelRoeder View on GitHub
bug
Dominant language
Java
Stars
5
Forks
6
PR merge metrics
No merged PRs in 30d

Description

The current NumberOfTriangleMetric (https://github.com/dice-group/Lemming/blob/master/src/main/java/org/aksw/simba/lemming/metrics/single/NumberOfTrianglesMetric.java#L41-L75) (edge iterator approach) does not compute the correct amount of triangles on all graphs.

We extended the current unit tests in our fork and apart from more simple examples, we added a test case based on a graph (see https://snap.stanford.edu/data/email-Eu-core.html) from the SNAP dataset. The actual test implementation can be found here:
https://github.com/BlackHawkLex/Lemming/blob/master/src/test/java/org/aksw/simba/lemming/metrics/single/triangle/AbstractNumberOfTrianglesMetricTest.java

For running the tests associated with the NumberOfTriangleMetric in this fork, the following test case has to be run:
https://github.com/BlackHawkLex/Lemming/blob/master/src/test/java/org/aksw/simba/lemming/metrics/single/triangle/EdgeIteratorNumberOfTrianglesMetricTest.java

The algorithm outputs a triangle count of 1439598, although the graph actually contains 105461 triangles according to the SNAP graph detail page: https://snap.stanford.edu/data/email-Eu-core.html.

Furthermore, from what we have tested so far it seems that it also outputs wrong counts for most on the graphs on the SemanticWebDogFood assuming that our implementation of the "Forward" algorithm is correct (which according to our test cases seems to be the case). In order to compare the results of the edge-iterator approach and our forward approach, one can add the EdgeIteratorNumberOfTrianglesMetric and the ForwardNumberOfTriangleMetric to the metrics list in the EvaluationRunner (https://github.com/BlackHawkLex/Lemming/blob/master/src/main/java/org/aksw/simba/lemming/tools/EvaluationRunner.java) and use the `getSemanticDogFoodGraphs()` method to choose the right graphs for running an evaluation.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.