Реализация Гирвана-Ньюмана в графическом инструменте - PullRequest
Новая
       35

Реализация Гирвана-Ньюмана в графическом инструменте

0 голосов
/ 04 октября 2018

Я пытаюсь реализовать алгоритм Гирвана-Ньюмана в graph-tool и использую igraph для перекрестной проверки количества кластеров.Проблема в том, что я получаю больше кластеров, около 460, чем версия igraph, 23. Как мне уменьшить количество кластеров?Кроме того, количество кластеров также меняется время от времени.Иногда он может найти около 480 кластеров, а иногда он будет ниже 461. Еще одно замечание: я использовал двудольный граф в качестве меньшего тестового образца (1031 узел, 2295 ребер).

Вот весь сценарий: 

import graph_tool.all as gt


def remove_edge_by_betweenness(G):
    ''' Removes an edge based its highest betweenness value
    :param G: graph-tool Graph object
    :return: graph-tool Edgelist of edges with the highest betweenness value
    '''
    ep_betweenness = gt.betweenness(G)[1]
    b_values = set(ep_betweenness.a)
    edges = gt.find_edge(G, prop=ep_betweenness, match=max(b_values))
    if edges:
        for edge in edges:
            G.remove_edge(edge)

def recalculate_components(G):
    ''' Recalculates connected components in G after removing edges with highest betweenness values
    :param G: graph-tool Graph object
    :return: Vertex PropertyMap of the new connected components
    '''
    init_comp_prop = gt.label_components(G)[0]
    new_comp_prop = init_comp_prop
    init_ncomps = len(set(init_comp_prop.a))
    ncomps = init_ncomps
    while ncomps <= init_ncomps:
        remove_edge_by_betweenness(G)
        new_comp_prop = gt.label_components(G)[0]
        ncomps = len(set(new_comp_prop.a))
    return new_comp_prop

def girvan_newman(G):
    G.set_fast_edge_removal()
    max_q = -1.0
    q = -1.0
    comp_prop = None
    best_comp_prop = None
    while G.num_edges() > 0:
        comp_prop = recalculate_components(G)
        q = gt.modularity(G, comp_prop)
        if q > max_q:
            max_q = q
            best_comp_prop = comp_prop

    if best_comp_prop:
        return set(best_comp_prop.a)
    else:
        return None


co_graph = gt.load_graph('../data/bipartite_graph.gml', fmt='gml')
print("graph loaded")

gn_clusters = girvan_newman(co_graph)
print("Girvan Newman clusters:")
print(gn_clusters)
...