BetweennessCentrality.py

#encoding=utf-8
import time
from collections import defaultdict
from operator import itemgetter

# Data in BC.txt:
# a	b
# a	h
# b	c
# b	h
# h	i
# h	g
# g	i
# g	f
# c	f
# c	i
# c	d
# d	f
# d	e
# f	e

class Graph:
	def __init__(self):
		self.Graph = defaultdict(set)
		self.NodesNum = 0
	
	def MakeLink(self,filename,separator):
		with open(filename,'r') as graphfile:
			for line in graphfile:
				nodeA,nodeB = line.strip().split(separator)
				self.Graph[nodeA].add(nodeB)
				self.Graph[nodeB].add(nodeA)
		self.NodesNum = len(self.Graph)
		
	def BetweennessCentrality(self):
		betweenness = dict.fromkeys(self.Graph,0.0)
		for s in self.Graph:
			# 1. compute the length and number of shortest paths from node s
			S = []
			P = {}
			for v in self.Graph:
				P[v]=[]
			Sigma = dict.fromkeys(self.Graph,0.0)
			Sigma[s] = 1.0
			D = {}
			D[s] = 0
			Q = [s]
			# use BFS to find single source shortest paths
			while Q:
				v = Q.pop(0)
				S.append(v)
				Dv = D[v]
				for w in self.Graph[v]:
					# w found for the first time?
					if w not in D:
						Q.append(w)
						D[w] = D[v] + 1
					# shortest path to w via v
					if D[w] == D[v] + 1:
						Sigma[w] += Sigma[v]
						P[w].append(v)
			
			# 2. sum all pair-dependencies of node s
			delta = dict.fromkeys(self.Graph,0.0)
			# S returns vertices in order of non-increasing distance from s
			while S:
				w = S.pop()
				coeff = (1.0+delta[w])/Sigma[w]
				for v in P[w]:
					delta[v] += Sigma[v]*coeff
				if w != s:
					betweenness[w] += delta[w]
		
		scale = 1.0/((self.NodesNum-1)*(self.NodesNum-2))
		for v in betweenness:
			betweenness[v] *= scale
			
		betweenness = [(node,bc) for node,bc in betweenness.iteritems()]
		betweenness = sorted(betweenness,key=itemgetter(1),reverse=True)
		return betweenness

if __name__=='__main__':
	separator = '\t'
	file = 'C:\\Users\\Administrator\\Desktop\\BC.txt'
	
	begin = time.time()
	myGraph = Graph()
	myGraph.MakeLink(file,separator)
	print myGraph.BetweennessCentrality()
	
	print 'Time:',time.time()-begin,' seconds'