def detectBetweenness(G, numClusters, sites, bipartite):
	Gnew = copy.deepcopy(G)
	numComponents = nx.number_connected_components(G)

	betweenness = nx.edge_betweenness_centrality(Gnew,  weight='capacity')
	pickle.dump(betweenness, open("betweennessUnipartite.p", "wb"))
	#betweenness = pickle.load("betweenessUnipartite.p", "rb")
	
	while (numComponents < numClusters):
		print "num components is now ",  numComponents ### REMEMBER TO DELETE THIS ###

		# calculate betweenness of each edge
		betweenness = nx.edge_betweenness_centrality(Gnew,  weight='capacity')

		## identify and remove the edge with highest betweenness
		max_ = max(betweenness.values())
		for k, v in betweenness.iteritems():
			if float(v) == max_:
				G.remove_edge(k[0], k[1])
		numComponents = nx.number_connected_components(G)

	clusters = {}
	i=0
	j = 0
	for component in list(nx.connected_components(Gnew)):
		for node in component:
			if node in sites:
				clusters[node] = i
				j +=1
		print j, "Nodes in cluster ", i
		j = 0
		i += 1

	return clusters

	def find_groups_girvan_newman(self, num_groups):
		if (num_groups==1):
			return set([self.G])
		elif (num_groups in self.groupCache):
			#return a copy of the stored set
			return self.groupCache[num_groups].copy()
		elif (num_groups > len(self.G.nodes())):
			return self.find_groups(len(self.G.nodes))
		#returns set of subgraphs
		previous_partition = self.find_groups(num_groups-1)

		#map subgraph to betweenness dict (a dict mapping edges to betweenness)
		betweenness_map = {subgraph:nx.edge_betweenness_centrality(subgraph) for subgraph in previous_partition}
		#Map subgraph to the (edge, betweenness) pair of the max betweenness in that subgraph
		betweenness_max_map = {e[0]:max(e[1].items(), key=lambda(x):x[1]) for e in betweenness_map.items() if len(e[0].nodes()) > 1}

		#Track removed edges to add them again at end of algorithm
		removed_edges = []

		#Loop until a subgraph is split
		while True:
			print "Removing edge"
			#Identify the subgraph and edge with max betweenness
			target_subgraph_edge=max(betweenness_max_map.items(), key=lambda(x):x[1][1])
			target_subgraph = target_subgraph_edge[0]
			target_edge= target_subgraph_edge[1][0]
			max_betweenness = -1
			#Remove the edge (temporarily)
			target_subgraph.remove_edge(target_edge[0], target_edge[1])
			removed_edges.append(target_edge)
			connected_components = nx.connected_components(target_subgraph)
			if len(connected_components) > 1:
				#Removing one edge from a connected component will result in max 2 connected components
				new_subgraph_1 = target_subgraph.subgraph(connected_components[0])
				new_subgraph_2 = target_subgraph.subgraph(connected_components[1])
				#Repair removed edges in target_subgraph
				target_subgraph.add_edges_from(removed_edges)
				#Remove target subgraph
				previous_partition.discard(target_subgraph)
				#Add new subgraphs
				previous_partition.add(new_subgraph_1)
				previous_partition.add(new_subgraph_2)
				#Store result
				self.groupCache[num_groups] = previous_partition
				return previous_partition.copy()
			else:
				#Recalculate betweenness, max betweenness for target subgraph
				target_betweenness = nx.edge_betweenness_centrality(target_subgraph)
				betweenness_map[target_subgraph] = target_betweenness
				betweenness_max_map[target_subgraph] = max(target_betweenness.items(), key=lambda(x):x[1])
			#Repeat loop
			continue

def gnewman(club,splitTo = 2):
    itteration = 0
    # ok so why do I check the number of connected components
    # for an undirected graph it is know that a connected component of an
    # an undirected graph is a subgraph in which any two vertices are connected to each other by paths
    # this is useful for this application since we are splitting a graph into two subgraphs
    # ie to mathematically represent the splitting of the club
    while nx.number_connected_components(club) < splitTo:
        # returns to us edges with the weights
        between = nx.edge_betweenness_centrality(club,normalized=False)
        # we want the edges with the highest edge betweenness centrality
        # there might be ties so just get the max betweenness
        m = max(between.values())
        # unpack the tuple returned to us by between.items ((u,v), maxBetweenScore)
        for (hU,hV),val in between.items():
            # check to see if m(max betweenness score) is equal to val
            # removes ties along the way
            if val == m:
                club.remove_edge(hU,hV)
                print("removed edge %s--%s with betweenness score of %f"%(hU,hV,m))
        itteration += 1

        print("-------------------------")
        # this print out can be uncommented it simply shows the same metric as described two different ways
        # print(nx.number_connected_components(club),len(list(nx.connected_component_subgraphs(club))))
    print("total iterations %d for splitting into %d"%(itteration,splitTo))

def edge_betweeness_centrality(X):
    """
    based on networkx function: edge_betweenness_centrality
    """
    XX = np.zeros(X.shape)
    for i, value in enumerate(X):
        adj_mat = value.reshape((np.sqrt(len(value)),-1))
        adj_mat = (adj_mat - np.min(adj_mat)) / (np.max(adj_mat) - np.min(adj_mat))
        adj_mat = 1 - adj_mat

#        th = np.mean(adj_mat) + 0.1
#        adj_mat = np.where(adj_mat < th, adj_mat, 0.)

        percent, th, adj_mat, triu = percentage_removed(adj_mat, 0.43) # 43 #63 #73
        print("percent = {0}, threshold position = {1}, threshold = {2}\n".format(percent, th, triu[th]))

        g = nx.from_numpy_matrix(adj_mat)
        print "Graph Nodes = {0}, Graph Edges = {1} ".format(g.number_of_nodes(), g.number_of_edges())
        print "\nEdge kept ratio, {0}".format(float(g.number_of_edges())/((g.number_of_nodes()*(g.number_of_nodes()-1))/2))

        bet_cent = nx.edge_betweenness_centrality(g, weight = 'weight', normalized = True)
        edge_cent = np.zeros(adj_mat.shape)

        for k in bet_cent:
            edge_cent[k[0],k[1]] = bet_cent[k]
        XX[i] = edge_cent.reshape(-1)
        print "graph {0} => mean {1}, min {2}, max {3}".format(i, np.mean(XX[i]), np.min(XX[i]), np.max(XX[i]))

    return XX

def find_disjoint_graphs(my_graph):
    #Dictionary of edges with the calculated value of betweenness centrality
    edgeList = nx.edge_betweenness_centrality(my_graph)

    maxEdgeBetweenness = 0
    edgeNodes = ()

    # Loop over items and unpack each item, find maxEdgeBetweenness among all items.
    for node_id, edgeBetweennessVal in edgeList.items():
        #print("EdgeBetweenness = %f " % edgeBetweennessVal)
        #print("EdgeNodes = %s" % (node_id,))
        if edgeBetweennessVal > maxEdgeBetweenness:
            maxEdgeBetweenness = edgeBetweennessVal
            edgeNodes = node_id
    print("Highest betweenness is %f - for the edge %s" % (maxEdgeBetweenness, edgeNodes,))

    #Remove the edge with highest betweenness
    my_graph.remove_edge(edgeNodes[0], edgeNodes[1])
    print("Removed edge %s" % (edgeNodes,))
    #Add the removed edge to the edges_removed list
    edges_removed.append(edgeNodes)

    num_of_connected_components = nx.number_connected_components(my_graph)
    print("Number of connected components(sub-graphs/communities) after removing edge %s = %d" % (edgeNodes,num_of_connected_components))
    G = my_graph
    # Draw and show the graph, with labels
    nx.draw_networkx(my_graph, pos=None, with_labels=True)
    plt.show()

 def test_C4(self):
     """Edge betweenness centrality: C4"""
     G=nx.cycle_graph(4)
     b=nx.edge_betweenness_centrality(G, weight=None, normalized=True)
     b_answer={(0, 1):2,(0, 3):2, (1, 2):2, (2, 3): 2}
     for n in sorted(G.edges()):
         assert_almost_equal(b[n],b_answer[n]/6.0)

def plot_edge_btwn(G, bins=20):
    """
    Plot the edge-betweenness distributions.

    Args:
        G: networkx graph object
    Returns:
        figure handle & axes array.
    """
    # Get edge-betweenness dictionary
    edge_btwn_dict = nx.edge_betweenness_centrality(G)

    # Sort edge-betweenness dictionary by edge-betweenness values
    edge_btwn_labels_sorted, edge_btwn_vec_sorted = \
        network_compute.get_ranked(edge_btwn_dict)

    # Open figure & axes
    fig, axs = plt.subplots(2, 1)
    # Plot histogram
    axs[0].hist(edge_btwn_vec_sorted, bins)
    axs[0].set_ylabel('Occurrences')
    axs[0].set_xlabel('Edge-betweenness')

    # Plot sorted node between values
    axs[1].scatter(np.arange(len(edge_btwn_vec_sorted)),
                   edge_btwn_vec_sorted, s=20, c='r')
    axs[1].set_xlabel('Area')
    axs[1].set_ylabel('Edge-betweenness')

    return fig, axs

 def test_K5(self):
     """Edge betweenness centrality: K5"""
     G=nx.complete_graph(5)
     b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False)
     b_answer=dict.fromkeys(G.edges(),1)
     for n in sorted(G.edges()):
         assert_almost_equal(b[n],b_answer[n])

 def test_P4(self):
     """Edge betweenness centrality: P4"""
     G=nx.path_graph(4)
     b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False)
     b_answer={(0, 1):3,(1, 2):4, (2, 3):3}
     for n in sorted(G.edges()):
         assert_almost_equal(b[n],b_answer[n])

def CalculateBetweeness(graph):

    BetweenValue = nx.edge_betweenness_centrality(graph, normalized=True, k=None, weight=None, seed=None)

    graph.remove_edges_from([k for k, v in BetweenValue.iteritems() if v == max(BetweenValue.values())])

    return graph

 def test_balanced_tree(self):
     """Edge betweenness centrality: balanced tree"""
     G = nx.balanced_tree(r=2, h=2)
     b = nx.edge_betweenness_centrality(G, weight="weight", normalized=False)
     b_answer = {(0, 1): 12, (0, 2): 12, (1, 3): 6, (1, 4): 6, (2, 5): 6, (2, 6): 6}
     for n in sorted(G.edges()):
         assert_almost_equal(b[n], b_answer[n])

 def f28(self):
     start = 0
     c_vals = nx.edge_betweenness_centrality(self.G).values()
     res = sum(c_vals)
     stop = 0
     # self.feature_time.append(stop - start)
     return res

	def communitySplits(self, graph):
		"""
		Compute the splits for the formation of communities. 

		Arguments:
			graph -  A networkx graph of digraph. 

		Returns:
			The graph with weak edges removed. 	
		"""

		nConnComp = nx.number_connected_components(graph)
		nComm = nConnComp

		while (nComm <= nConnComp):
			betweenness = nx.edge_betweenness_centrality(graph)
			if (len(betweenness.values()) != 0 ):
				max_betweenness = max(betweenness.values())
			else:
				break	
			for u,v in betweenness.iteritems():
				if float(v) == max_betweenness:
					graph.remove_edge(u[0], u[1])
			nComm = nx.number_connected_components(graph)			
		return graph		

def get_communities(graph):
	betweenness = nx.edge_betweenness_centrality(graph)
	sorted_betweeness = [x[0] for x in sorted(betweenness.items(), key = lambda x : x[1], reverse = True)]
	best_partitions = []
	max_modularity = -1.0
	graph_copy = graph.copy()
	while sorted_betweeness:
		communities = [list(x) for x in nx.connected_components(graph_copy)]
		partitions = {}
		for i in range(len(communities)):
			for node in communities[i]:
				partitions[node] = i
		modularity = community.modularity(partitions, graph_copy)
		if modularity > max_modularity:
			best_partitions = communities
			max_modularity = modularity
		elif modularity <= max_modularity:
			break;
		graph_copy.remove_edge(*sorted_betweeness[0])
		del sorted_betweeness[0]
	for partition in best_partitions:
		print sorted(partition)
	val_map = {}
	for partition in best_partitions:
		value = random.random()
		while value in val_map.values():
			value = random.random()
		for node in partition:
			val_map[node] = value
	values = [val_map.get(node) for node in graph.nodes()]
	nx.draw_spring(graph, node_color = values, node_size = 500, with_labels = True)
	plt.savefig(sys.argv[2])

def whole_graph_metrics(graph, weighted=False):
    graph_metrics = {}

    # Shortest average path length
    graph_metrics['avg_shortest_path'] = \
        nx.average_shortest_path_length(graph, weight=weighted)

    # Average eccentricity
    ecc_dict = nx.eccentricity(graph)
    graph_metrics['avg_eccentricity'] = np.mean(np.array(ecc_dict.values()))

    # Average clustering coefficient
    # NOTE: Option to include or exclude zeros
    graph_metrics['avg_ccoeff'] = \
        nx.average_clustering(graph, weight=weighted, count_zeros=True)

    # Average node betweeness
    avg_node_btwn_dict = nx.betweenness_centrality(graph, normalized=True)
    graph_metrics['avg_node_btwn'] = \
        np.mean(np.array(avg_node_btwn_dict.values()))

    # Average edge betweeness
    avg_edge_btwn_dict = nx.edge_betweenness_centrality(graph, normalized=True)
    graph_metrics['avg_edge_btwn'] = \
        np.mean(np.array(avg_edge_btwn_dict.values()))

    # Number of isolates
    graph_metrics['isolates'] = len(nx.isolates(graph))

    return graph_metrics

def gRa(g, w):
    '''w为图中的边数，表示经过减边p扰动后仍然留在数据中的边数'''
    tg = g.copy()
    Rq = nx.to_scipy_sparse_matrix(g)
    Rq = Rq.toarray()

    bw = nx.edge_betweenness_centrality(g, normalized=False)
    norm = sum(bw.values())
    e_num = len(g.edges())

    n = len(g)
    N = (n * (n - 1)) / 2
    for k, v in bw.items():
        g.add_edge(*k, weight=v)
#    print g.edges(data=True)
    R = nx.to_scipy_sparse_matrix(g, weight='weight')
    Rp = R.toarray()

    Rp = w * Rp * 2.0 / Rp.sum()

    q = float(e_num - w) / (N - e_num)

    for i, each in enumerate(Rq):
        for j, e in enumerate(each):
            if e == 0:
                Rp[i, j] = q  # 超级绕采用特别方式在Rp中加入Rq
    for i in range(n):
        Rp[i,i]=0 #去除对角线上的q
    return Rp

def edge_betweenness(edge_list=path+'connected-component-analysis/network-profiling-data/cid6_analysis/cid6-edge-list',
                     out_file=path+'connected-component-analysis/network-profiling-data/cid6_analysis/cid6-edge-betweenness-10000.json'):
    G = nx.read_edgelist(edge_list, delimiter='\t')
    M = nx.edge_betweenness_centrality(G, k=10000)
    M_new = dict()
    for k, v in M.items():
        M_new[k[0]+'\t'+k[1]] = v
    json.dump(M_new, open(out_file, 'w'))

def setCapacity(G, factor):
	if(G.number_of_edges() > 0):
		bb=nx.edge_betweenness_centrality(G, normalized=True, weight='weight')

		for edge in G.edges(data=True):
			edge[2]['capacity'] = (bb[(edge[0],edge[1])]*factor)

	return G

def Betweenness_Edge_centrality(G, fn):
	'''
	G: Graph
	fn: funtion of n used to delimit the number of hotspots
	'''
	edgeBetDict = nx.edge_betweenness_centrality(G)
	edgeBetCentr = SortDictionary(edgeBetDict)[:int(fn)]
	return edgeBetCentr

        def most_valuable_edge(G):
            """Returns the edge with the highest betweenness centrality
            in the graph `G`.

            """
            # We have guaranteed that the graph is non-empty, so this
            # dictionary will never be empty.
            betweenness = nx.edge_betweenness_centrality(G)
            return max(betweenness, key=betweenness.get)