Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A Python memory and computational optimized version of Harmonic Centrality
#This function compute the harminic distance of graph's nodes
#graph is a dictionary implementation of adjacency list { 1 : [1,2,3], ...}
#return a dictionary where keys are nodes name and values are node harmonic distances
def harmonic2(graph):
#for dynamic programming
harmRes = dict()
for i in graph.keys():
harmRes[i] = 0.0
#for each node compute the distance from reachable nodes
for s in graph.keys():
queue = [s] #visited node
###BFS###
distance = dict()
for i in graph.keys():
distance[i] = -1 #not visited
distance[s] = 0
#BFS
while queue != []:
c = queue.pop(0)
#for each neighbour 'i'
for i in graph[c]:
if i in distance and distance[i] == -1: #not visited
queue.append(i)
dist = distance[c] + 1
distance[i] = dist
# dist is d(s,i)
harmRes[i] += 1.0 / dist #h(i) = sum 1/d(s,i)
return harmRes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.