gistfile1.txt

def __one_level(graph, status, weight_key, resolution, randomize,mu = 0.3):
    """Compute one level of communities
    """

    modified = True
    nb_pass_done = 0
    cur_mod = __modularity_lft(status,mu)
    new_mod = cur_mod

    while modified and nb_pass_done != __PASS_MAX:
        cur_mod = new_mod
        modified = False
        nb_pass_done += 1

        for node in __randomly(graph.nodes(), randomize):
            com_node = status.node2com[node]
            neigh_communities = __neighcom(node, graph, status, weight_key) # can I trust it?

            v_degree = status.gdegrees.get(node, 0.)
            v_loops  = float(graph.get_edge_data(node, node, default={weight_key: 0}).get(weight_key, 1))
            v_in_degree = neigh_communities.get(com_node,0)
            com_degree = status.degrees.get(com_node, 0.)
            com_in_degree = status.internals.get(com_node, 0.)
            links = float(status.total_weight)
            in_links = 0
            for community in set(status.node2com.values()):
                in_links += status.internals.get(community, 0.)
            out_links = links - in_links

            __dCv = v_in_degree
            __E = links
            __Eout = out_links
            __Ein = in_links
            __DC = com_degree
            __DinC = com_in_degree
            __dv = v_degree
            __dinv = v_loops

            remove_cost = 0
            remove_cost += 4. * __dCv * log(mu/(1.-mu))
            if __Eout> 0:
                remove_cost += - __Eout * log( 2.* __Eout )
            if __Eout+__dCv>0:
                remove_cost += (__Eout + __dCv) * log(2.*(__Eout + __dCv))
            tmp = comb(__DC - __dv,__DinC - __dinv - 2.*__dCv, exact=True)
            if tmp > 0:
                remove_cost += log( tmp )
            if ( __DinC - __dinv - 2.*__dCv )> 0:
                remove_cost += - ( __DinC - __dinv - 2.*__dCv ) * log( __DinC - __dinv - 2.*__dCv ) / 2.
            remove_cost += log( comb(__dv,__dinv, exact=True) )
            if __dinv>0:
                remove_cost += - __dinv * log( __dinv ) / 2.
            remove_cost += - log( comb(__DC,__DinC, exact=True) )
            if __DinC>0:
                remove_cost +=  __DinC * log( __DinC ) / 2.

            degc_totw = remove_cost
            __remove(node, com_node,
                     neigh_communities.get(com_node, 0.), status)

            best_com = com_node
            best_increase = 0.

            links = float(status.total_weight)
            in_links = 0
            for community in set(status.node2com.values()):
                in_links += status.internals.get(community, 0.)
            out_links = links - in_links

            for com, dnc in __randomly(neigh_communities.items(),
                                       randomize):

                com_degree = status.degrees.get(com, 0.)
                com_in_degree = status.internals.get(com, 0.)
                v_in_degree = dnc

                __dCv = v_in_degree
                __E = links
                __Eout = out_links
                __Ein = in_links
                __DC = com_degree
                __DinC = com_in_degree
                __dv = v_degree
                __dinv = v_loops


                add_cost = 0.
                add_cost += 4. * __dCv * log((1.-mu)/mu)
                add_cost += - __Eout * log( 2.* __Eout )
                add_cost += (__Eout - __dCv) * log(2.*(__Eout - __dCv))
                add_cost += log( comb(__DC + __dv,__DinC + __dinv + 2.*__dCv, exact=True) )
                add_cost += - ( __DinC + __dinv + 2.*__dCv ) * log( __DinC + __dinv + 2.*__dCv ) / 2.
                add_cost += - log( comb(__DC,__DinC, exact=True) )
                if __DinC > 0:
                    add_cost +=  __DinC * log( __DinC ) / 2.
                add_cost += - log( comb(__dv,__dinv, exact=True) )
                if __dinv > 0:
                    add_cost += + __dinv * log( __dinv ) / 2.

                incr = add_cost + remove_cost 
                if incr > best_increase:
                    best_increase = incr
                    best_com = com
            __insert(node, best_com,
                     neigh_communities.get(best_com, 0.), status)
            if best_com != com_node:
                modified = True
        new_mod = __modularity_lft(status,mu)
        if new_mod - cur_mod < __MIN:
            break
    return max(new_mod,cur_mod)


def __modularity_lft(status,mu = 0.3):
    """
    Fast compute the modularity of the partition of the graph using
    status precomputed
    """

    links = float(status.total_weight)
    in_links = 0
    for community in set(status.node2com.values()):
        in_links += status.internals.get(community, 0.)
    out_links = links - in_links

    result = 0.
    result += 4. * out_links * log( mu )
    result += 4. * in_links * log( 1 - mu )
    if out_links>0:
        result -= out_links * log( 2.*out_links )

    for community in set(status.node2com.values()):
        degree = status.degrees.get(community, 0.)
        in_degree = status.internals.get(community, 0.)  # ??смущает, что там в статусе веса где-то на два делятся, надо бы проверить...
        result += log( comb(degree,in_degree, exact=True) )
        if in_degree>0:
            result -= in_degree*log(in_degree)/2.

    return result