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'
两个变量接收返回的key,valuedef dict_key_value(data):
k=str(data.keys()).replace("dict_keys","").replace("(","").replace(")","").replace("[","").replace("]","").replace("'",'')
v=str(data.values()).replace("dict_values","").replace("(","").replace(")","").replace("[","").replace("]","").replace("'",'')
return k,v
if __name__ == '__main__':
data = {
'HJB779158HJB': 'MyTalkingTom-meizujinke-jinkead-rc-b585-v4.8.0.585.apk'}
key,value=dict_key_value(data)
print("key:",key)
print("value:",value)