Adamic-Adar Index

Overview

The Adamic-Adar Index (AA Index) is a node similarity metric named after its creators Lada Adamic and Eytan Adar. This index measures the potential connection strength between two nodes based on the shared neighbors they have in the graph.

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

The underlying idea of the AA Index is that common neighbors with low degree provide more valuable information about the similarity between two nodes than common neighbors with high degrees. It is computed 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)|, then sums up these reciprocal values for all common neighbors.

Higher AA Index scores indicate greater similarity between 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 ignores the direction of edges but calculates them as undirected edges.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}])
insert().into(@default).edges([{_from:"A", _to:"B"}, {_from:"B", _to:"E"}, {_from:"C", _to:"B"}, {_from:"C", _to:"D"}, {_from:"C", _to:"F"}, {_from:"D", _to:"B"}, {_from:"D", _to:"E"}, {_from:"F", _to:"D"}, {_from:"F", _to:"G"}])

Creating HDC Graph

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

CALL hdc.graph.create("hdc-server-1", "hdc_tlp", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_tlp", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: topological_link_prediction

File Writeback

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

algo(topological_link_prediction).params({
  projection: "hdc_tlp",
  ids: ["C"],
  ids2: ["A","E","G"],
  return_id_uuid: "id"
}).write({
  file: {
    filename: "aa.txt"
  }
})

Result:

_id1,_id2,result
C,A,1.66096
C,E,3.32193
C,G,2.0959

Full Return

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

exec{
  algo(topological_link_prediction).params({
    ids: ["C"],
    ids2: ["A","C","E","G"],
    type: "Adamic_Adar",
    return_id_uuid: "id"
  }) as aa
  return aa
} on hdc_tlp

Result:

Stream Return

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

exec{
  algo(topological_link_prediction).params({
    ids: ["C"],
    ids2: ["A", "B", "D", "E", "F", "G"],
    type: "Adamic_Adar",
    return_id_uuid: "id"
  }).stream() as aa
  where aa.result >= 2
  return aa
} on hdc_tlp

Result: