Adamic-Adar Index

Overview

The Adamic-Adar Index (AA Index) is a node similarity metric named after its creators Lada Adamic and Eytan Adar. It measures the strength of potential connection between two nodes based on their common neighbors.

• L.A. Adamic, E. Adar, Friends and Neighbors on the Web (2003)

The core idea behind the AA Index is that common neighbors with lower degrees contribute more valuable information about the similarity between two nodes than those with higher degrees. The index is calculated using the following formula:

where N(u) is the set of nodes adjacent to u. For each common neighbor u of the two nodes, the AA Index first calculates the reciprocal of the logarithm of its degree |N(u)|, and then sums these values across all common neighbors.

A higher AA Index score indicates greater similarity between the nodes, while a score of 0 indicates no similarity between two nodes.

In this example, N(D) ∩ N(E) = {B, F}, where $\frac{1}{\mathrm{log|N(B)|}}$ = $\frac{1}{\mathrm{log4}}$ = 1.6610, $\frac{1}{\mathrm{log|N(F)|}}$ = $\frac{1}{\mathrm{log3}}$ = 2.0959, thus AA(D,E) = 1.6610 + 2.0959 = 3.7569.

Considerations

• The AA Index algorithm treats all edges as undirected, ignoring their original direction.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
INSERT (A:default {_id: "A"}),
       (B:default {_id: "B"}),
       (C:default {_id: "C"}),
       (D:default {_id: "D"}),
       (E:default {_id: "E"}),
       (F:default {_id: "F"}),
       (G:default {_id: "G"}),
       (A)-[:default]->(B),
       (B)-[:default]->(E),
       (C)-[:default]->(B),
       (C)-[:default]->(D),
       (C)-[:default]->(F),
       (D)-[:default]->(B),
       (D)-[:default]->(E),
       (F)-[:default]->(D),
       (F)-[:default]->(G);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: topological_link_prediction

File Writeback

GQLUQL
CALL algo.topological_link_prediction.write("my_hdc_graph", {
  ids: ["C"],
  ids2: ["A","E","G"],
  return_id_uuid: "id"
}, {
  file: {
    filename: "aa"
  }
})

Result:

File: aa
_id1,_id2,result
C,A,1.66096
C,E,3.32193
C,G,2.0959

Full Return

GQLUQL
CALL algo.topological_link_prediction.run("my_hdc_graph", {
  ids: ["C"],
  ids2: ["A","C","E","G"],
  type: "Adamic_Adar",
  return_id_uuid: "id"
}) YIELD aa
RETURN aa

Result:

Stream Return

GQLUQL
CALL algo.topological_link_prediction.stream("my_hdc_graph", {
  ids: ["C"],
  ids2: ["A", "B", "D", "E", "F", "G"],
  type: "Adamic_Adar",
  return_id_uuid: "id"
}) YIELD aa
FILTER aa.result >= 2
RETURN aa

Result: