Pregunta Recuperar nodos conectados en un grafo de NetworkX


Pregunta sencilla: me gustaría recuperar todos los nodos conectados a un nodo determinado dentro de un gráfico de NetworkX para crear un subgrafo. En el ejemplo que se muestra a continuación, solo quiero extraer todos los nodos dentro del círculo, dado el nombre de uno de ellos.

NetworkX graph

Probé la siguiente función recursiva, pero alcancé el límite de recursión de Python, aunque solo hay 91 nodos en esta red.

Independientemente de si el código de abajo tiene errores o no, ¿cuál es la mejor manera de hacer lo que estoy tratando de lograr? Ejecutaré este código en gráficos de varios tamaños, y no sabré de antemano cuál será la profundidad máxima de recursión.

def fetch_connected_nodes(node, neighbors_list):
    for neighbor in assembly.neighbors(node):
        print(neighbor)
        if len(assembly.neighbors(neighbor)) == 1:
            neighbors_list.append(neighbor)
            return neighbors_list
        else:
            neighbors_list.append(neighbor)
            fetch_connected_nodes(neighbor, neighbors_list)

neighbors = []
starting_node = 'NODE_1_length_6578_cov_450.665_ID_16281'
connected_nodes = fetch_connected_nodes(starting_node, neighbors)

5
2017-10-12 18:39


origen


Respuestas:


Suponiendo que el gráfico no está dirigido, hay un comando networkx integrado para esto:

node_connected_component(G, n)

La documentación es aquí. Devuelve todos los nodos en el componente conectado de G conteniendo n.

No es recursivo, pero no creo que realmente necesites o incluso lo desees.


comenta tu código: Tienes un error que a menudo resultará en una recursión infinita. Si u y v Son vecinos con grado al menos 2, entonces comenzará con u, poner v en la lista y al procesar v poner u En la lista y sigue repitiendo. Necesita cambiar para procesar solo los vecinos que no están en neighbors_list. Es caro verificar eso, así que en lugar de eso, usa un juego. También hay un pequeño problema si el nodo de inicio tiene el grado 1. Su prueba para el grado 1 no hace lo que está buscando. Si el nodo inicial tiene grado 1, pero su vecino tiene un grado más alto, no encontrará los vecinos del vecino.

Aquí hay una modificación de su código:

def fetch_connected_nodes(G, node, seen = None):
    if seen == None:
        seen = set([node])
    for neighbor in G.neighbors(node):
        print(neighbor)
        if neighbor not in seen:
            seen.add(neighbor)
            fetch_connected_nodes(G, neighbor, seen)
    return seen

Llamas a esto como fetch_connected_nodes(assembly, starting_node).


8
2017-10-12 20:25



Simplemente puede usar una búsqueda de Breadth-first desde su nodo dado o cualquier nodo.

En Networkx puede tener el diagrama de árbol de su nodo de inicio usando la función:

bfs_tree(G, source, reverse=False)

Aquí hay un enlace al documento: Red bfs_tree.


4
2017-10-12 19:41



Aquí hay un algoritmo recursivo para conectar todos los nodos a un nodo de entrada.

def create_subgraph(G,sub_G,start_node):
sub_G.add_node(start_node)
for n in G.neighbors_iter(start_node):
    if n not in sub_G.neighbors(start_node):
        sub_G.add_path([start_node,n])
        create_subgraph(G,sub_G,n)

Creo que la clave aquí para evitar llamadas recursivas infinitas es la condición para verificar que el nodo que está al lado en el gráfico original no esté ya conectado en el sub_G que se está creando. De lo contrario, siempre irá hacia adelante y hacia atrás y los bordes entre los nodos que ya tienen bordes.

Lo probé de la siguiente manera:

G = nx.erdos_renyi_graph(20,0.08)
nx.draw(G,with_labels = True)
plt.show()
sub_G = nx.Graph()
create_subgraph(G,sub_G,17)
nx.draw(sub_G,with_labels = True)
plt.show()

Encontrará en la imagen adjunta, el gráfico completo y el sub_graph que contiene el nodo 17.enter image description here


3
2017-10-12 19:52