Определение количества ребер на сильно связанном компоненте - PullRequest
Новая
       102

Определение количества ребер на сильно связанном компоненте

1 голос
/ 27 сентября 2019

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

maxstmed = max(nx.strongly_connected_components(Gmedium), key=len)

Мой вопрос: как вы находите число ребер этой подключенной сети??Если вы попытаетесь найти количество узлов, у меня это будет выглядеть так: 

newGm = nx.Graph()
newGm.add_nodes_from(list(maxstmed))
newGm.number_of_nodes()

Но вы не можете применить это к ребрам, так как он возвращает 0, когда я использовал add_edges_from и number_of_edges.Я попытался посчитать это вручную следующим образом: 

count = 0
for u in list(newGm.nodes):
    for v in list(newGm.nodes):
        if u == v:
            continue
        if nx.has_path(Gmedium,u,v) == True:
            count += 1
print(count)

Но для большой сети (с более чем 10.000 узлов) это занимает вечность.Кто-нибудь знает алгоритм или функцию, чтобы справиться с этим эффективно?Я использую Python Ver.3 в среде Spyder.Спасибо.

1 Ответ

1 голос
/ 27 сентября 2019

Вы можете использовать функцию subgraph для извлечения подграфа с заданными узлами из исходного графа.Вы отправляете коллекцию узлов как атрибут, и она возвращает вам подграф исходного графа с этими узлами и ребрами между ними: 

G = nx.fast_gnp_random_graph(30, 0.04, directed=True, seed=1)
nx.draw(G)

enter image description here

C = max(nx.strongly_connected_components(G), key=len)
print(C)

{0, 3, 4, 6, 8, 10, 11, 15, 21, 22, 24, 25}

S = G.subgraph(C)
nx.draw(S)

enter image description here

print(list(nx.edges(S)))

[(0, 3), (3, 4), (3, 21), (4, 6), (6, 11), (6, 15), (8, 0), (10, 6), (11, 8), (11, 15), (15, 24), (15, 25), (21, 8), (21, 22), (21, 15), (22, 24), (22, 25), (22, 15), (24, 10), (25, 0)]

...