Как удалить края из крупнейших подключенного компонента? - PullRequest
Новая
       8

Как удалить края из крупнейших подключенного компонента?

1 голос
/ 04 апреля 2020

я работаю над динамическим c графиком, я хочу удалить ребра из самого большого подключенного компонента, вот пример кода, который я написал 

    graph=dn.read_snapshots('mytxt', nodetype=int, timestamptype=int)

 print(nx.number_connected_components(graph))
S=[len(c) for c in sorted(nx.connected_components(graph), key=len, reverse=True)]
print(S)----[150, 1]

здесь у меня есть два компонента, и мне нужно для работы с самым большим из них, со значением 150 

y=[]
 rand_set = set(random.sample(range(20), 5))
for (u,v,t) in **largest**.interactions():
        #m,n = pair(u, v)
        if r in rand_set:
            s.remove_edge((u,v,t))
            if(nx.is_connected(s)==True):
                y.append(u,v,t)
            else:
                graph.add_interaction((u,v,t))
            r+=1

здесь largest означает необходимость работы с наибольшим связанным компонентом этого графа в этом коде, я случайным образом удаляю ребро из подключенного компонента и добавляю к у, однако этот код не дает мне никакого результата. Любая помощь будет оценена

1 Ответ

1 голос
/ 04 апреля 2020

Давайте воспользуемся примером графика, чтобы более легко увидеть, как это можно сделать: 

l = [('maths', 'physics'), ('astronomy', 'physics'), ('history', 'archaeology'), ('environmental science', 'physics'), ('maths', 'astronomy'), ('history', 'literature'), ('astronomy', 'astrophysics'), ('literature', 'philosophy'), ('biology', 'physics')]
graph = nx.from_edgelist(l)

Итак, мы построили график, который выглядит следующим образом: 

pos = nx.spring_layout(graph, scale=20, k=3/np.sqrt(graph.order()))
nx.draw(graph, pos=pos,
        node_color='lightblue', 
        with_labels=True, 
        node_size=500)

enter image description here

Таким образом, на графике есть 2 связанных компонента, самый большой из которых - тот, который появляется слева на рисунке. Чтобы найти самый большой компонентный подграф, вы можете использовать connected_component_subgraphs и найти максимум, используя len в качестве функции key. 

S = max(nx.connected_component_subgraphs(graph), key=len)

Затем получите случайный выбор существующих ребер в этом подграфе, используя random.choices, установив k в значение интереса: 

edges_to_remove = random.choices(list(S.edges()), k=2)
# [('physics', 'biology'), ('physics', 'environmental science')]

В этом случае, например, мы будем удалять ребра, соединяющие узлы ('physics', 'biology') и ('physics', 'environmental science')

И затем, аналогично тому, что вы делаете, мы можем перебирать случайный выбор ребер edges_to_remove и удалять их из графика используя remove_edge: 

for edge in edges_to_remove:  
    graph.remove_edge(*edge)

В результате на следующем графике:

enter image description here

...