def test_K5(self):
     """Katz centrality: K5"""
     G = nx.complete_graph(5)
     alpha = 0.1
     b = nx.katz_centrality(G, alpha)
     v = math.sqrt(1 / 5.0)
     b_answer = dict.fromkeys(G, v)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n])
     nstart = dict([(n, 1) for n in G])
     b = nx.katz_centrality(G, alpha, nstart=nstart)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n])

 def most_central(self,F=1,cent_type='betweenness'):
     if cent_type == 'betweenness':
         ranking = nx.betweenness_centrality(self.G).items()
     elif cent_type == 'closeness':
         ranking = nx.closeness_centrality(self.G).items()
     elif cent_type == 'eigenvector':
         ranking = nx.eigenvector_centrality(self.G).items()
     elif cent_type == 'harmonic':
         ranking = nx.harmonic_centrality(self.G).items()
     elif cent_type == 'katz':
         ranking = nx.katz_centrality(self.G).items()
     elif cent_type == 'load':
         ranking = nx.load_centrality(self.G).items()
     elif cent_type == 'degree':
         ranking = nx.degree_centrality(self.G).items()
     ranks = [r for n,r in ranking]
     cent_dict = dict([(self.lab[n],r) for n,r in ranking])
     m_centrality = sum(ranks)
     if len(ranks) > 0:
         m_centrality = m_centrality/len(ranks)
     #Create a graph with the nodes above the cutoff centrality- remove the low centrality nodes
     thresh = F*m_centrality
     lab = {}
     for k in self.lab:
         lab[k] = self.lab[k]
     g = Graph(self.adj.copy(),self.char_list)
     for n,r in ranking:
         if r < thresh:
             g.G.remove_node(n)
             del g.lab[n]
     return (cent_dict,thresh,g)

def relevant_stats(G):
	cloC = nx.closeness_centrality(G, distance = 'distance')
	betC = nx.betweenness_centrality(G, weight = 'distance')
	katC = nx.katz_centrality(G)
	eigC = nx.eigenvector_centrality(G)

	return

def centrality_calculation_by_networkx(G):
    '''
    使用 networkx 计算 Centrality
    '''

    d_c = nx.degree_centrality(G)

    k_z = nx.katz_centrality(
        G=G,
        alpha=0.3,
        beta=0.3,
        max_iter=1000,
        tol=1.0e-6,
        nstart=None,
        normalized=True)

    # 归一化，每个元素除以集合中最大元素
    max_item = max([d_c[item] for item in d_c])
    degree_centrality = [round(d_c[item] / max_item, 4) for item in d_c]

    max_item = max([k_z[item] for item in k_z])
    katz_centrality = [round(k_z[item] / max_item, 4) for item in k_z]

    nx_list = [{'Degree': degree_centrality}, {'Katz': katz_centrality}]

    return nx_list

    def nextBestNode(self, state): #Finds the next best spot for a station
        graph = state.get_graph()
        nodeScores = []
        centrality = nx.katz_centrality(graph)
        for i in centrality:
            nodeScores.append(centrality[i])

        bestNode = 0
        bestScore = nodeScores[0]
        for i in range(len(nodeScores)):
            if (nodeScores[i] > bestScore and (i not in self.stations)):
                bestNode = i
                bestScore = nodeScores[i]
        #print("bestNode=",(bestScore,bestNode))

        #Factor in distance from each station
        for i in range(len(nodeScores)):
            if (i not in self.stations):
                distanceScore = 1.0 / self.closestStation(graph, i)[1]
                #print("distanceScore=",distanceScore)
                nodeScores[i] -= distanceScore * self.distanceWeight

        #Get the node with the best score
        bestNode = 0
        bestScore = nodeScores[0]
        for i in range(len(nodeScores)):
            if (nodeScores[i] > bestScore and (i not in self.stations)):
                bestNode = i
                bestScore = nodeScores[i]
        #print("bestNode=",(bestScore,bestNode))
        return bestNode

 def centralities(self):
     '''
     Get info on centralities of data
     Params:
         None
     Returns:
         dictionary of centrality metrics with keys(centralities supported):
             degree - degree centrality
             betweeness - betweeness centrality
             eigenvector - eigenvector centrality
             hub - hub scores - not implemented
             authority - authority scores - not implemented
             katz - katz centrality with params X Y
             pagerank - pagerank centrality with params X Y
     '''
     output = {}
     output['degree'] = nx.degree_centrality(self.G)
     output['betweeness'] = nx.betweenness_centrality(self.G)
     try:
         output['eigenvector'] = nx.eigenvector_centrality(self.G)
         output['katz'] = nx.katz_centrality(self.G)
     except:
         output['eigenvector'] = 'empty or exception'
         output['katz'] = 'empty or exception'
     # output['hub'] = 'Not implemented'
     # output['authority'] = 'Not implemented'
     # output['pagerank'] = 'Not implemented'
     return output

	def run(self,steps):
		for _ in xrange(steps):
			self.update()

		self.prs =nx.pagerank(self.G)			
		self.close = nx.closeness_centrality(self.G)
		self.bet = nx.betweenness_centrality(self.G)
		self.katz = nx.katz_centrality(self.G)

 def test_P3(self):
     """Katz centrality: P3"""
     alpha = 0.1
     G = nx.path_graph(3)
     b_answer = {0: 0.5598852584152165, 1: 0.6107839182711449,
                 2: 0.5598852584152162}
     b = nx.katz_centrality(G, alpha)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n], places=4)

def comparisons(G):
    evec = nx.eigenvector_centrality(G)
    print "EVEC:",evec

    pagerank = nx.pagerank(G)
    print "PAGERANK: ", pagerank

    katz = nx.katz_centrality(G)
    print "KATZ: ", katz

 def test_maxiter(self):
     alpha = 0.1
     G = nx.path_graph(3)
     max_iter = 0
     try:
         b = nx.katz_centrality(G, alpha, max_iter=max_iter)
     except nx.NetworkXError as e:
         assert str(max_iter) in e.args[0], "max_iter value not in error msg"
         raise # So that the decorater sees the exception.

 def test_beta_as_dict(self):
     alpha = 0.1
     beta = {0: 1.0, 1: 1.0, 2: 1.0}
     b_answer = {0: 0.5598852584152165, 1: 0.6107839182711449,
                 2: 0.5598852584152162}
     G = nx.path_graph(3)
     b = nx.katz_centrality(G, alpha, beta)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n], places=4)

def katz(g):
    eigv = eig(nx.adjacency_matrix(g, weight='diff').todense())
    max_eigv = max(eigv[0])
    max_eigv_reciprocal = 1./max_eigv
    alpha = max_eigv_reciprocal
    alpha = 0.9 * alpha
    beta = 1 - alpha
    katz_centrality = nx.katz_centrality(g, alpha=alpha, beta=beta,
                                         weight='diff')
    return katz_centrality

def centralityMeasures(G):
	# Betweenness
	# betw = nx.betweenness_centrality(G, normalized=True, weight='weight')
	# print sorted([(k,v) for k,v in betw.iteritems()], key= lambda x:(-x[1],x[0]))

	# clsn = nx.closeness_centrality(G, normalized=True)
	# print sorted([(k,v) for k,v in clsn.iteritems()], key= lambda x:(-x[1],x[0]))

	# evec = nx.eigenvector_centrality(G, weight='weight')
	# print sorted([(k,v) for k,v in evec.iteritems()], key= lambda x:(-x[1],x[0]))

	katz = nx.katz_centrality(G, normalized=True, weight='weight', alpha=0.005)
	print sorted([(k,v) for k,v in katz.iteritems()], key= lambda x:(-x[1],x[0]))

 def test_K5_unweighted(self):
     """Katz centrality: K5"""
     G = nx.complete_graph(5)
     alpha = 0.1
     b = nx.katz_centrality(G, alpha, weight=None)
     v = math.sqrt(1 / 5.0)
     b_answer = dict.fromkeys(G, v)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n])
     nstart = dict([(n, 1) for n in G])
     b = nx.eigenvector_centrality_numpy(G)
     for n in sorted(G):
         assert_almost_equal(b[n], b_answer[n], places=3)

 def test_multiple_alpha(self):
     alpha_list = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6]
     for alpha in alpha_list:
         b_answer = {0.1: {0: 0.5598852584152165, 1: 0.6107839182711449,
                           2: 0.5598852584152162},
                     0.2: {0: 0.5454545454545454, 1: 0.6363636363636365,
                           2: 0.5454545454545454},
                     0.3: {0: 0.5333964609104419, 1: 0.6564879518897746,
                           2: 0.5333964609104419},
                     0.4: {0: 0.5232045649263551, 1: 0.6726915834767423,
                           2: 0.5232045649263551},
                     0.5: {0: 0.5144957746691622, 1: 0.6859943117075809,
                           2: 0.5144957746691622},
                     0.6: {0: 0.5069794004195823, 1: 0.6970966755769258,
                           2: 0.5069794004195823}}
         G = nx.path_graph(3)
         b = nx.katz_centrality(G, alpha)
         for n in sorted(G):
             assert_almost_equal(b[n], b_answer[alpha][n], places=4)

def calculate_center(tcgaSubgraph):
    """
    DESCRIPTION: Calculate centrality measures
    INPUT: Graph object
    OUTPUT: Dictionary of dictionaries, each being a different centrality
    measure
    """
    # calculate maximum eigenvalue of graph
    denseMat = nx.adjacency_matrix(tcgaSubgraph).todense()  # make adj mat
    eigs = numpy.linalg.eig(denseMat)[0]  # calculate eigenvalues
    maxEig = max(eigs)
    alpha = 1 / maxEig.real

    # calculate centrality measures
    centers = {}
    centers["eigen"] = nx.eigenvector_centrality(tcgaSubgraph)
    centers["degree"] = nx.degree_centrality(tcgaSubgraph)
    centers["katz"] = nx.katz_centrality(tcgaSubgraph, alpha=alpha - 0.01, beta=1.0)
    centers["pagerank"] = nx.pagerank(tcgaSubgraph)
    return centers

def centrality_calculation_by_networkx(G):
    '''
    使用 networkx 计算 Centrality
    '''

    d_c = nx.degree_centrality(G)

    k_z = nx.katz_centrality(
        G=G,
        alpha=0.3,
        beta=0.3,
        max_iter=1000,
        tol=1.0e-6,
        nstart=None,
        normalized=True)

    # 归一化，每个元素除以集合中最大元素
    d_c = [round(1.0 * item / max(d_c), 4) for item in d_c]
    k_z = [round(1.0 * item / max(k_z), 4) for item in k_z]

    nx_list = [{'Degree': d_c}, {'Katz': k_z}]

    return nx_list

def test(G):

    d_c = nx.degree_centrality(G)

    e_v = nx.eigenvector_centrality(G=G, max_iter=1000, tol=1.0e-6)

    k_z = nx.katz_centrality(
        G=G,
        alpha=0.3,
        beta=0.3,
        max_iter=1000,
        tol=1.0e-6,
        nstart=None,
        normalized=True)

    p_k = nx.pagerank(G=G, alpha=0.3, personalization=None, max_iter=100,
                      tol=1.0e-6, nstart=None, weight='weight', dangling=None)

    b_c = nx.betweenness_centrality(G=G, k=None, normalized=True,
                                    weight=None, endpoints=False, seed=None)

    c_c = nx.closeness_centrality(G=G, u=None, distance=None, normalized=True)

    d_c = [round(1.0 * item / max(d_c), 4) for item in d_c]
    k_z = [round(1.0 * item / max(k_z), 4) for item in k_z]
    e_v = [round(1.0 * item / max(e_v), 4) for item in e_v]
    b_c = [round(1.0 * item / max(b_c), 4) for item in b_c]
    c_c = [round(1.0 * item / max(c_c), 4) for item in c_c]
    p_k = [round(1.0 * item / max(p_k), 4) for item in p_k]

    return [{'Eigenvector': e_v},
            {'Betweenness': b_c},
            {'Closeness': c_c},
            {'PageRank': p_k},
            {'Degree': d_c},
            {'Katz': k_z}]

def make_net(centrality_name, in_path, out_path):
	#sample code
		#import _2_time_based_data_network_feature
		#make_net_in_path = "../3.time_based_data/1.cite_relation_devide/"
		#make_net_out_path = "../3.time_based_data/2.centrality_data/"
		#_2_time_based_data.make_net( "in_degree", make_net_in_path, make_net_out_path)

	#네트워크를 만들고 Centurality를 계산하고 저장할 것이다.
	import networkx as nx
	global Dump
	Dump = {}
	make_net_initialize(in_path)
	start_time = time.time()
	temp_start_time = time.time()

	print "=============		make_net start:" + centrality_name + "		=============="
	print "=============		from 1951 to 2015		=============="

	for year in range(1951, 2016):
		print year
		f_in = open(in_path + str(year) + "_cite.csv","r")
		lines = f_in.readlines()
		f_in.close()
		edge_list = []

		for line in lines:
			data = line.split(",")
			data_tuple = (data[0].strip(), data[1].strip())
			edge_list.append(data_tuple)

		Net = nx.DiGraph(edge_list)
		Cen_in = {}
		if (centrality_name == "in_degree"):
			Cen_in = nx.in_degree_centrality(Net)
		elif (centrality_name == "degree"):
			Cen_in = nx.degree_centrality(Net)
		elif (centrality_name == "eigenvector"):
			Cen_in = nx.eigenvector_centrality_numpy(Net)
		elif (centrality_name == "katz"):
			Cen_in = nx.katz_centrality(Net)
		elif (centrality_name == "pagerank"):
			Cen_in = nx.pagerank(Net)
		elif (centrality_name == "communicability"):
			Net = nx.Graph(edge_list)
			Cen_in = nx.communicability_centrality(Net)
		elif (centrality_name == "load"):
			Cen_in = nx.load_centrality(Net)
		
		for j in Cen_in:
			key = j
			val = Cen_in[j]
			Dump[key][year] = val

	#저장하는 코드 
	f_out = open(out_path + centrality_name +"_centrality.csv", "w")
	for key in Dump:
		line = str(key)
		for year in range(1951, 2016):
			data = Dump[key].get(year, 0)
			line = line + ","+ str(data)
		line = line + "\n"
		f_out.write(line)
	f_out.close()

	print "=============		make_net end			=============="
	print(centrality_name + "takes %s seconds" % (time.time() - temp_start_time))
	temp_start_time = time.time()

 def test_bad_beta_numbe(self):
     G = nx.Graph([(0,1)])
     e = nx.katz_centrality(G, 0.1,beta='foo')