PGX 21.1.1
Documentation

Adamic-Adar index

Category structure evaluation

Algorithm ID pgx_builtin_s2_adamic_adar_counting

Time Complexity O(E) with E = number of edges

Space Requirement O(E) with E = number of edges

Javadoc

The Adamic-Adar index is meant for undirected graphs, since it is computed using the degree of the shared neighbors by two vertices in the graph. This implementation computes the index for every pair of vertices connected by an edge and associates it with that edge.

Signature

Input Argument Type Comment
G graph
Output Argument Type Comment
adamic_adar edgeProp edge property holding the Adamic-Adar index of each edge in the graph.

Code

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.annotations.Out;

import static java.lang.Math.log;

@GraphAlgorithm
public class AdamicAdar {
  public void adamicAdar(PgxGraph g, @Out EdgeProperty<Double> aa) {
    g.getEdges().forEach(e -> {
      PgxVertex src = e.sourceVertex();
      PgxVertex dst = e.destinationVertex();

      double value = src.getNeighbors()
          .filter(n -> n.hasEdgeFrom(dst))
          .sum(n -> 1 / log(n.getDegree()));

      aa.set(e, value);
    });
  }
}

/*
 * Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
 */

procedure adamic_adar(graph G; edgeProp<double> aa) {

  foreach (e: G.edges) {
    node src = e.fromNode();
    node dst = e.toNode();

    // In C++ backend, the compiler optimizes below
    e.aa = sum (n: src.nbrs) (n.hasEdgeFrom(dst)) {1 / log(n.numNbrs())};

    // into
    // e.aa = sum(n: src.commonNbrs(dst)) {1 / log(n.numNbrs())};
  }
}