Six-Degrees Estimate

Problem

Estimate small-world distances: the fraction of ordered node pairs within six hops and the mean finite distance.

Run a BFS from every node. Return [fraction_within_six, average_distance], where the fraction uses all n * (n - 1) ordered pairs and the average uses only connected pairs (0.0 when none exist). edges is a list of [u, v] pairs.

Hint

Six degrees of separation is the empirical claim that this fraction stays near 1.

Test cases

case 1

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

expected: [1,1.6666666666666667]

case 2

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

expected: [0.3333333333333333,1]

case 3

in: [1,[]]

expected: [0,0]

Starter codePython

def six_degrees(n, edges):
    # Your code here
    pass

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