This is an automated email from the ASF dual-hosted git repository. jin pushed a commit to branch olap-algo in repository https://gitbox.apache.org/repos/asf/incubator-hugegraph.git
commit 08c33c2e56a2208bf9775c1f103b3949a53a34a1 Author: Jermy Li <[email protected]> AuthorDate: Tue Oct 13 14:51:51 2020 +0800 fix closeness distance: 1 extra length is calculated (#67) Change-Id: I35bc20698bf93002a530b95688cd0359a9154fdf --- .../job/algorithm/cent/ClosenessCentralityAlgorithm.java | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/ClosenessCentralityAlgorithm.java b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/ClosenessCentralityAlgorithm.java index 3391a191a..6a95794a0 100644 --- a/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/ClosenessCentralityAlgorithm.java +++ b/hugegraph-core/src/main/java/com/baidu/hugegraph/job/algorithm/cent/ClosenessCentralityAlgorithm.java @@ -89,10 +89,17 @@ public class ClosenessCentralityAlgorithm extends AbstractCentAlgorithm { t = t.emit().until(__.loops().is(P.gte(depth))); t = filterNonShortestPath(t, true); + /* + * We use Marchiori's algorithm(sum of reciprocal of distances): + * .math("_-1").sack(Operator.div).sack().sum() + * for Bavelas's algorithm: + * .math("_-1").sum().sack(Operator.div).sack() + * see https://en.wikipedia.org/wiki/Closeness_centrality + */ GraphTraversal<Vertex, ?> tg; tg = t.group().by(__.select(Pop.first, "v").id()) .by(__.select(Pop.all, "v").count(Scope.local) - .sack(Operator.div).sack().sum()); + .math("_-1").sack(Operator.div).sack().sum()); GraphTraversal<Vertex, ?> tLimit = topN(tg, topN); return this.execute(tLimit, () -> tLimit.next());
