Adamic-Adar Score

Problem

Compute the Adamic-Adar link prediction score between nodes u and v of an undirected graph.

The score sums 1 / ln(degree(w)) over all common neighbors w with degree greater than 1. Return 0.0 when there are no such common neighbors. edges is a list of [u, v] pairs.

Hint

Rare common neighbors carry more signal, so low-degree nodes get larger weights.

Test cases

case 1

in: [3,[[0,1],[1,2]],0,2]

expected: 1.4426950408889634

case 2

in: [4,[[0,1],[1,2],[2,3],[3,0]],0,2]

expected: 2.8853900817779268

case 3

in: [4,[[0,1],[0,2],[0,3]],1,2]

expected: 0.9102392266268373

case 4

in: [3,[[0,1],[1,2]],0,1]

expected: 0

Starter codePython

import math
def adamic_adar_score(n, edges, u, v):
    # Your code here
    pass

4 test cases · run your code against them in the editor