def _cliques_heuristic(G, H, k, min_density):
    h_cnumber = nx.core_number(H)
    for i, c_value in enumerate(sorted(set(h_cnumber.values()), reverse=True)):
        cands = set(n for n, c in h_cnumber.items() if c == c_value)
        # Skip checking for overlap for the highest core value
        if i == 0:
            overlap = False
        else:
            overlap = set.intersection(*[
                set(x for x in H[n] if x not in cands)
                for n in cands])
        if overlap and len(overlap) < k:
            SH = H.subgraph(cands | overlap)
        else:
            SH = H.subgraph(cands)
        sh_cnumber = nx.core_number(SH)
        SG = nx.k_core(G.subgraph(SH), k)
        while not (_same(sh_cnumber) and nx.density(SH) >= min_density):
            #!! This subgraph must be writable => .copy()
            SH = H.subgraph(SG).copy()
            if len(SH) <= k:
                break
            sh_cnumber = nx.core_number(SH)
            sh_deg = dict(SH.degree())
            min_deg = min(sh_deg.values())
            SH.remove_nodes_from(n for n, d in sh_deg.items() if d == min_deg)
            SG = nx.k_core(G.subgraph(SH), k)
        else:
            yield SG

def kcore_decomposition(orig_g_M, otherModel_M, name):
  dorig = pd.DataFrame()
  for g in orig_g_M:
      g.remove_edges_from(g.selfloop_edges())
      d = nx.core_number(g)
      df = pd.DataFrame.from_dict(d.items())
      df[[0]] = df[[0]].astype(int)
      gb = df.groupby(by=[1])
      dorig = pd.concat([dorig, gb.count()], axis=1)  # Appends to bottom new DFs
  print "orig"

  if not dorig.empty :
      zz = len(dorig.mean(axis=1).values)
      sa =  int(math.ceil(zz/75))
      if sa == 0: sa=1
      for x in range(0, len(dorig.mean(axis=1).values), sa):
          print "(" + str(dorig.mean(axis=1).index[x]) + ", " + str(dorig.mean(axis=1).values[x]) + ")"

  dorig = pd.DataFrame()
  for g in otherModel_M:
      d = nx.core_number(g)
      df = pd.DataFrame.from_dict(d.items())
      df[[0]] = df[[0]].astype(int)
      gb = df.groupby(by=[1])
      dorig = pd.concat([dorig, gb.count()], axis=1)  # Appends to bottom new DFs
  print "== the other model =="
  if not dorig.empty :
      zz = len(dorig.mean(axis=1).values)
      sa =  int(math.ceil(zz/75))
      if sa == 0: sa=1
      for x in range(0, len(dorig.mean(axis=1).values), sa):
          print "(" + str(dorig.mean(axis=1).index[x]) + ", " + str(dorig.mean(axis=1).values[x]) + ")"
  return

def approximation_k_components_dense(G, max_k=None):
    # Compute only until max k
    if max_k is None:
        max_k = float('infinity')
    # Dictionary with connectivity level (k) as keys and a list of
    # sets of nodes that form a k-component as values
    k_components = {}
    # Dictionary with nodes as keys and maximum k of the deepest 
    # k-component in which they are embedded
    k_number = dict(((n,0) for n in G.nodes()))
    # We deal first with k = 1
    k_components[1] = []
    for cc in networkx.connected_components(G):
        for node in cc:
            k_number[node] = 1
        if len(cc) > 2:
            k_components[1].append(set(cc))
    # Start from k_cores: all k-components are also k-cores
    # but not all k-cores are k-components
    core_number = networkx.core_number(G)
    for k in range(2, min(max(core_number.values())+1, max_k + 1)):
        k_components[k] = []
        # Build k-core subgraph
        C = G.subgraph((n for n, cnum in core_number.items() if cnum >= k))
        for candidates in networkx.connected_components(C):
            # Compute pairwise vertex connectivity for each connected part
            # of this k-core using White and Newman 2001 algorithm.
            K = all_pairs_vertex_connectivity(G.subgraph(candidates), 
                                                    max_paths=k,
                                                    strict=True)
            # Build a graph where two nodes are linked if they have at least k
            # node independent paths between them. Suggested in 
            # White & Newman, 2001 (This is a very dense graph, almost complete 
            # in many cases)
            H = networkx.Graph()
            # Too slow because we add every edge twice
            #H.add_edges_from(((u,v) for u in K \
            #                    for (v,w) in K[u].iteritems() if w >= k))
            seen = set()
            for u, nbrs in K.items():
                for v, ni_paths in nbrs.iteritems():
                    if v not in seen and ni_paths >= k:
                        H.add_edge(u,v)
                seen.add(u)
            # Compute k-core of H and assume that the core of level k is a good
            # approximation for a component of level k
            core_number_2 = networkx.core_number(H)
            C2 = H.subgraph((n for n, cnum in core_number_2.items() if cnum >= k))
            for k_component in networkx.connected_components(C2):
                if len(k_component) >= k:
                    k_components[k].append(set(k_component))
                    for node in k_component:
                        k_number[node] = k
    
    return k_components, k_number

 def test_directed_find_cores(Self):
     '''core number had a bug for directed graphs found in issue #1959'''
     # small example where too timid edge removal can make cn[2] = 3
     G = nx.DiGraph()
     edges = [(1, 2), (2, 1), (2, 3), (2, 4), (3, 4), (4, 3)]
     G.add_edges_from(edges)
     assert_equal(nx.core_number(G), {1: 2, 2: 2, 3: 2, 4: 2})
     # small example where too aggressive edge removal can make cn[2] = 2
     more_edges = [(1, 5), (3, 5), (4, 5), (3, 6), (4, 6), (5, 6)]
     G.add_edges_from(more_edges)
     assert_equal(nx.core_number(G), {1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3})

def bound_branch(G, k ,q_nodes, is_use_cores=False, select_method='rand'):
    '''
    wrapper of branch and bound method
    '''
    ts = time.time()
    global optimal
    optimal = set()
    k_neighbors = k_hop_nbrs_n(G, k, q_nodes)
    sub = set(q_nodes)
    sub.update(k_neighbors)
    g = nx.subgraph(G, sub)

    if is_use_cores:
        cores = nx.core_number(g)
    else:
        cores = None

    # print('subgraph ', g.nodes())
    print('minimum degree of subgraph', minimum_degree(g))
    print('k neighbors', len(k_neighbors))
    BB(g, k, q_nodes, set(), cores, select_method)
    print('the solution is', optimal)

    te = time.time()

    texe = round(te-ts, 2) # the execution time

    return texe

 def OrigCoreN(self):
     ''' returns a 2d array containing the pagerank of the origin node for all edges
     ''' 
     probas = np.dot( 
                   np.array(nx.core_number(self).values(),dtype=float).reshape(-1,1),
                   np.ones((1,self.number_of_nodes())))
     return probas

def SentimentAnalysis_RGO_Belief_Propagation(nxg):
	#Bayesian Pearl Belief Propagation is done by
	#assuming the senti scores as probabilities with positive
	#and negative signs and the Recursive Gloss Overlap
	#definition graph being the graphical model.
	#Sentiment as a belief potential is passed through 
	#the DFS tree of this graph.  
	dfs_positive_belief_propagated=1.0
	core_positive_belief_propagated=1.0
	dfs_negative_belief_propagated=1.0
	core_negative_belief_propagated=1.0
	core_xnegscore=core_xposscore=1.0
	dfs_knegscore=dfs_kposscore=dfs_vposscore=dfs_vnegscore=1.0
	sorted_core_nxg=sorted(nx.core_number(nxg).items(),key=operator.itemgetter(1), reverse=True)
	kcore_nxg=nx.k_core(nxg,6,nx.core_number(nxg))
	for x in sorted_core_nxg:
	      xsset = swn.senti_synsets(x[0])
	      if len(xsset) > 2:
	     		core_xnegscore = float(xsset[0].neg_score())*10.0
	      		core_xposscore = float(xsset[0].pos_score())*10.0
	      if core_xnegscore == 0.0:
			core_xnegscore = 1.0
	      if core_xposscore == 0.0:
			core_xposscore = 1.0
	      core_positive_belief_propagated *= float(core_xposscore)
	      core_negative_belief_propagated *= float(core_xnegscore)
	print "Core Number: RGO_sentiment_analysis_belief_propagation: %f, %f" % (float(core_positive_belief_propagated), float(core_negative_belief_propagated))
	#for k,v in nx.dfs_edges(nxg):
	for k,v in nx.dfs_edges(kcore_nxg):
	      ksynset = swn.senti_synsets(k)
	      vsynset = swn.senti_synsets(v)
	      if len(ksynset) > 2:
	     		dfs_knegscore = float(ksynset[0].neg_score())*10.0
	      		dfs_kposscore = float(ksynset[0].pos_score())*10.0
	      if len(vsynset) > 2:
			dfs_vnegscore = float(vsynset[0].neg_score())*10.0
			dfs_vposscore = float(vsynset[0].pos_score())*10.0
	      dfs_kposscore_vposscore = float(dfs_kposscore*dfs_vposscore)
	      dfs_knegscore_vnegscore = float(dfs_knegscore*dfs_vnegscore)
	      if dfs_kposscore_vposscore == 0.0:
		dfs_kposscore_vposscore = 1.0
	      if dfs_knegscore_vnegscore == 0.0:
		dfs_knegscore_vnegscore = 1.0
	      dfs_positive_belief_propagated *= float(dfs_kposscore_vposscore)
	      dfs_negative_belief_propagated *= float(dfs_knegscore_vnegscore)
	print "K-Core DFS: RGO_sentiment_analysis_belief_propagation: %f, %f" % (float(dfs_positive_belief_propagated),float(dfs_negative_belief_propagated))
	return (dfs_positive_belief_propagated, dfs_negative_belief_propagated, core_positive_belief_propagated, core_negative_belief_propagated)

def anti_kcore(G, k = None, core_number = None):
    if core_number is None:
        core_number = nx.core_number(G)
    if k is None:
        k = max(core_number.values())
    nodes = (n for n in core_number if core_number[n] >= k)
    anti_nodes = (n for n in core_number if core_number[n] < k)
    return (G.subgraph(anti_nodes).copy(), list(nodes))

 def TargCoreN(self):
     ''' returns a 2d array containing the pagerank of the target node for all edges
     ''' 
     probas =  np.dot( 
                   np.ones((self.number_of_nodes(),1)),
                   np.array(nx.core_number(self).values(),dtype=float).reshape(1,-1)
                   )       
     return probas

def test_white_harary_2():
    # Figure 8 white and harary (2001)
    # # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
    G.add_edge(0,4)
    # kappa <= lambda <= delta
    assert_equal(3, min(nx.core_number(G).values()))
    assert_equal(1, nx.node_connectivity(G))
    assert_equal(1, nx.edge_connectivity(G))

def k_crust(G,k=None,core_number=None):
    """Return the k-crust of G.

    The k-crust is the graph G with the k-core removed.

    Parameters
    ----------
    G : NetworkX graph
       A graph or directed graph.
    k : int, optional
      The order of the shell.  If not specified return the main crust.
    core_number : dictionary, optional
      Precomputed core numbers for the graph G.

    Returns
    -------
    G : NetworkX graph
       The k-crust subgraph

    Raises
    ------
    NetworkXError
        The k-crust is not defined for graphs with self loops or parallel edges.

    Notes
    -----
    This definition of k-crust is different than the definition in [1]_.
    The k-crust in [1]_ is equivalent to the k+1 crust of this algorithm.

    Not implemented for graphs with parallel edges or self loops.

    For directed graphs the node degree is defined to be the
    in-degree + out-degree.

    Graph, node, and edge attributes are copied to the subgraph.

    See Also
    --------
    core_number

    References
    ----------
    .. [1] A model of Internet topology using k-shell decomposition
       Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt,
       and Eran Shir, PNAS  July 3, 2007   vol. 104  no. 27  11150-11154
       http://www.pnas.org/content/104/27/11150.full
    """
    func = lambda v, k, core_number: core_number[v] <= k
    # HACK These two checks are done in _core_helper, but this function
    # requires k to be one less than the maximum core value instead of
    # just the maximum. Therefore we duplicate the checks here. A better
    # solution should exist...
    if core_number is None:
        core_number = nx.core_number(G)
    if k is None:
        k = max(core_number.values()) - 1
    return _core_helper(G, func, k, core_number)

def k_shell(G,k=None,core_number=None):
    """Return the k-shell of G.

    The k-shell is the subgraph of nodes in the k-core but not in the (k+1)-core.

    Parameters
    ----------
    G : NetworkX graph
      A graph or directed graph.
    k : int, optional
      The order of the shell.  If not specified return the main shell.
    core_number : dictionary, optional
      Precomputed core numbers for the graph G.


    Returns
    -------
    G : NetworkX graph
       The k-shell subgraph

    Raises
    ------
    NetworkXError
        The k-shell is not defined for graphs with self loops or parallel edges.

    Notes
    -----
    This is similar to k_corona but in that case only neighbors in the
    k-core are considered.

    Not implemented for graphs with parallel edges or self loops.

    For directed graphs the node degree is defined to be the
    in-degree + out-degree.

    Graph, node, and edge attributes are copied to the subgraph.

    See Also
    --------
    core_number
    k_corona


    References
    ----------
    .. [1] A model of Internet topology using k-shell decomposition
       Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt,
       and Eran Shir, PNAS  July 3, 2007   vol. 104  no. 27  11150-11154
       http://www.pnas.org/content/104/27/11150.full
    """
    if core_number is None:
        core_number=nx.core_number(G)
    if k is None:
        k=max(core_number.values()) # max core
    nodes=(n for n in core_number if core_number[n]==k)
    return G.subgraph(nodes).copy()

def real_degeneracy(node):
    friends = get_all_friends(node)
    print "construct graph"
    G = construct_networkx_graph(friends)
    print "calculate core number"
    core_list = nx.core_number(G)
    ret = 0
    for key in core_list.keys():
        ret = max(ret, core_list[key])
    return ret

def k_corona(G, k, core_number=None):
    """Return the k-corona of G.

    The k-corona is the subgraph of nodes in the k-core which have
    exactly k neighbours in the k-core.

    Parameters
    ----------
    G : NetworkX graph
       A graph or directed graph
    k : int
       The order of the corona.
    core_number : dictionary, optional
       Precomputed core numbers for the graph G.

    Returns
    -------
    G : NetworkX graph
       The k-corona subgraph

    Raises
    ------
    NetworkXError
        The k-cornoa is not defined for graphs with self loops or
        parallel edges.

    Notes
    -----
    Not implemented for graphs with parallel edges or self loops.

    For directed graphs the node degree is defined to be the
    in-degree + out-degree.

    Graph, node, and edge attributes are copied to the subgraph.

    See Also
    --------
    core_number

    References
    ----------
    .. [1]  k -core (bootstrap) percolation on complex networks:
       Critical phenomena and nonlocal effects,
       A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes,
       Phys. Rev. E 73, 056101 (2006)
       http://link.aps.org/doi/10.1103/PhysRevE.73.056101
    """

    if core_number is None:
        core_number = nx.core_number(G)
    nodes = (n for n in core_number
             if core_number[n] == k
             and len([v for v in G[n] if core_number[v] >= k]) == k)
    return G.subgraph(nodes).copy()

def KShell_Centrality(G):
    #网络的kshell中心性
    #The k-core is found by recursively pruning nodes with degrees less than k.
    #The k-shell is the subgraph of nodes in the k-core but not in the (k+1)-core.
    nodes = {}
    core_number = nx.core_number(G) #The core number of a node is the largest value k of a k-core containing that node.
    for k in list(set(core_number.values())):
        nodes[k] = list(n for n in core_number if core_number[n]==k)
    #print core_number #{'1': 2, '0': 2, '3': 2, '2': 2, '4': 1}字典（节点：KShell值）
    #print nodes.keys(),nodes
    KShell_Centrality = core_number
    return KShell_Centrality

def k_crust(G,k=None,core_number=None):
    """Return the k-crust of G.

    The k-crust is the graph G with the k-core removed.

    Parameters
    ----------
    G : NetworkX graph
       A graph or directed graph.
    k : int, optional
      The order of the shell.  If not specified return the main crust.
    core_number : dictionary, optional
      Precomputed core numbers for the graph G.

    Returns
    -------
    G : NetworkX graph
       The k-crust subgraph

    Raises
    ------
    NetworkXError
        The k-crust is not defined for graphs with self loops or parallel edges.

    Notes
    -----
    This definition of k-crust is different than the definition in [1]_.
    The k-crust in [1]_ is equivalent to the k+1 crust of this algorithm.

    Not implemented for graphs with parallel edges or self loops.

    For directed graphs the node degree is defined to be the
    in-degree + out-degree.

    Graph, node, and edge attributes are copied to the subgraph.

    See Also
    --------
    core_number

    References
    ----------
    .. [1] A model of Internet topology using k-shell decomposition
       Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt,
       and Eran Shir, PNAS  July 3, 2007   vol. 104  no. 27  11150-11154
       http://www.pnas.org/content/104/27/11150.full
    """
    if core_number is None:
        core_number=nx.core_number(G)
    if k is None:
        k=max(core_number.values())-1
    nodes=(n for n in core_number if core_number[n]<=k)
    return G.subgraph(nodes).copy()

def k_core(G,k=None,core_number=None):
    """Return the k-core of G.

    A k-core is a maximal subgraph that contains nodes of degree k or more.

    Parameters
    ----------
    G : NetworkX graph
      A graph or directed graph
    k : int, optional
      The order of the core.  If not specified return the main core.
    core_number : dictionary, optional
      Precomputed core numbers for the graph G.

    Returns
    -------
    G : NetworkX graph
      The k-core subgraph

    Raises
    ------
    NetworkXError
      The k-core is not defined for graphs with self loops or parallel edges.

    Notes
    -----
    The main core is the core with the largest degree.

    Not implemented for graphs with parallel edges or self loops.

    For directed graphs the node degree is defined to be the
    in-degree + out-degree.

    Graph, node, and edge attributes are copied to the subgraph.

    See Also
    --------
    core_number

    References
    ----------
    .. [1] An O(m) Algorithm for Cores Decomposition of Networks
       Vladimir Batagelj and Matjaz Zaversnik,  2003.
       http://arxiv.org/abs/cs.DS/0310049
    """
    if core_number is None:
        core_number=nx.core_number(G)
    if k is None:
        k=max(core_number.values()) # max core
    nodes=(n for n in core_number if core_number[n]>=k)
    return G.subgraph(nodes).copy()

def calculate(net):
    if net.number_of_selfloops() > 0: 
        try:
            net.remove_edges_from(net.selfloop_edges())
        except: 
            return 0
    try:
        c = nx.core_number(net).values()
    except:
        return 0

    if len(c) == 0:
        return 0
    else:
        return round(sum(c)/len(c),7)

def approximation_k_components(G, max_k=None):
    # Compute only until max k
    if max_k is None:
        max_k = float('infinity')
    # Dictionary with connectivity level (k) as keys and a list of
    # sets of nodes that form a k-component as values
    k_components = {}
    # Dictionary with nodes as keys and maximum k of the deepest 
    # k-component in which they are embedded
    k_number = dict(((n,0) for n in G.nodes()))
    # We deal first with k = 1
    k_components[1] = []
    for cc in networkx.connected_components(G):
        for node in cc:
            k_number[node] = 1
        if len(cc) > 2:
            k_components[1].append(set(cc))
    # Start from k_cores: all k-components are also k-cores
    # but not all k-cores are k-components
    core_number = networkx.core_number(G)
    for k in range(2, min(max(core_number.values())+1, max_k + 1)):
        k_components[k] = []
        # Build k-core subgraph
        C = G.subgraph((n for n, cnum in core_number.items() if cnum >= k))
        for candidates in networkx.connected_components(C):
            # Compute pairwise vertex connectivity for each connected part
            # of this k-core using White and Newman (2001) algorithm and build 
            # the complement graph of a graph where two nodes are linked if 
            # they have at least k node independent paths between them.
            SG = G.subgraph(candidates)
            H = networkx.Graph()
            for u,v in itertools.combinations(SG, 2):
                K = pairwise_vertex_connectivity(SG, u, v, max_paths=k, 
                                                    strict=True)
                if K < k or math.isnan(K):
                    H.add_edge(u,v)
            # Compute complement k-core (anticore) of H and assume that the 
            # core of level k is a good approximation for a component of level k
            acore_number = anticore_number(H)
            A = H.subgraph((n for n, cnum in acore_number.items() if cnum >= k))
            for k_component in networkx.connected_components(A):
                if len(k_component) >= k:
                    k_components[k].append(set(k_component))
                    for node in k_component:
                        k_number[node] = k
    
    return k_components, k_number

def compute_node_measures(ntwk, calculate_cliques=False):
    """
    These return node-based measures
    """
    iflogger.info('Computing node measures:')
    measures = {}
    iflogger.info('...Computing degree...')
    measures['degree'] = np.array(list(ntwk.degree().values()))
    iflogger.info('...Computing load centrality...')
    measures['load_centrality'] = np.array(
        list(nx.load_centrality(ntwk).values()))
    iflogger.info('...Computing betweenness centrality...')
    measures['betweenness_centrality'] = np.array(
        list(nx.betweenness_centrality(ntwk).values()))
    iflogger.info('...Computing degree centrality...')
    measures['degree_centrality'] = np.array(
        list(nx.degree_centrality(ntwk).values()))
    iflogger.info('...Computing closeness centrality...')
    measures['closeness_centrality'] = np.array(
        list(nx.closeness_centrality(ntwk).values()))
    #    iflogger.info('...Computing eigenvector centrality...')
    #    measures['eigenvector_centrality'] = np.array(nx.eigenvector_centrality(ntwk, max_iter=100000).values())
    iflogger.info('...Computing triangles...')
    measures['triangles'] = np.array(list(nx.triangles(ntwk).values()))
    iflogger.info('...Computing clustering...')
    measures['clustering'] = np.array(list(nx.clustering(ntwk).values()))
    iflogger.info('...Computing k-core number')
    measures['core_number'] = np.array(list(nx.core_number(ntwk).values()))
    iflogger.info('...Identifying network isolates...')
    isolate_list = nx.isolates(ntwk)
    binarized = np.zeros((ntwk.number_of_nodes(), 1))
    for value in isolate_list:
        value = value - 1  # Zero indexing
        binarized[value] = 1
    measures['isolates'] = binarized
    if calculate_cliques:
        iflogger.info('...Calculating node clique number')
        measures['node_clique_number'] = np.array(
            list(nx.node_clique_number(ntwk).values()))
        iflogger.info('...Computing number of cliques for each node...')
        measures['number_of_cliques'] = np.array(
            list(nx.number_of_cliques(ntwk).values()))
    return measures