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'
1、Python使用与C、Java类似的运算符，支持整数与浮点数的数学运算。同时还支持复数运算与无穷位数（实际受限于计算机的能力）的整数运算。除了求绝对值函数abs()外，大多数数学函数处于math和cmath模块内。前者用于实数运算，而后者用于复数运算。使用时需要先导入它们，比如：
>>> import math>>> print(math.sin(math.pi/2))
1.0
fractions模块用于支持分数运算；decimal模块用于支持高精度的浮点数运算。
2、Python定义求余运行a % b的值处于开区间[0, b)内，如果b是负数，开区间变为(b, 0]。这是一个很常见的定义方式。不过其实它依赖于整除的定义。为了让方程式：b * (a // b) + a % b = a恒真，整除运行需要向负无穷小方向取值。比如7 // 3的结果是2，而(-7) // 3的结果却是-3。这个算法与其它很多编程语言不一样，需要注意，它们的整除运算会向0的方向取值。
3、Python允许像数学的常用写法那样连着写两个比较运行符。比如a <b <c与a <b and b <c等价。C++的结果与Python不一样，首先它会先计算a <b，根据两者的大小获得0或者1两个值之一，然后再与c进行比较。
Python中的运算符主要分为六大类，其中包含算术运算符、赋值运算符、比较/关系运算符、逻辑运算符、位运算符以及三目运算符。1、Python算术运算符
是对数值类型的变量进行运算的，比如说：加、减、乘、除、取模和乘方运算等
2、Python赋值运算符
是对已存在的变量进行重新设置新值的运算符
3、Python关系运算符(也被称为比较运算符)
关系运算符结果一般包含bool、True、False等，而关系表达式经常用在if结构的条件中或循环结构的条件中
4、Python逻辑运算符
是用于连接多个条件，一般来讲就是关系表达式
5、Python位运算符
主要是用于数值类型的二进制的运算
6、Python三目运算符
在Python中，没有其他语言的三目运算符，可以借助if语言实现类似的三目运算符。
