Networkx finding common nodes between different shortest paths in a graph - Is there a alternate solution?

Question

I am writing a tool for recognizing nodes in a network that are causing delays when given a set of two or more sources and destinations experiencing network problems or delay. I am using networkx python library to build the network graph. Consider this graph -

a -- b -- c -- d  
     |    |
     e -- f

Say, these are the sets of source and destination facing network issues. Meaning traffic between a and d is experiencing delay and traffic between e and d is experiencing delay and so on.

| source | destination |
|--------|-------------|
| a      | d           |
| e      | d           |
| f      | a           |

I find the shortest path for these pairs of source and destination. I take an intersection between those two lists and check for errors on those devices. If I have 100 pairs of (source, dest) sets, then I would be finding the common nodes between 100 lists representing the paths between those two pairs.

Shortest path host a to host d: 
     ['a', 'b', 'c', 'd']
Shortest path host e to host d: 
     ['e', 'b', 'c', 'd']
Shortest path host f to host a: 
     ['f', 'c', 'b', 'a']

^^ common nodes are 'c' and 'b' and hence check these for errors.

My question is if there is a better way to do this in networkx, where I can take multiple paths between source and dest and find a common set of nodes? I have very limited knowledge of network/graph theory, but this seems like a common problem that's solved using graphs.

Albert · Accepted Answer · 2022-07-12T17:22:52.680

I think what you're looking for is the nodes of maximal degree, which have the lowest average weight per edge. We can get the info needed for sorting the nodes like this:

def avg_weight(graph, node):
    all_edges = graph.edges(data=True)
    edges = list(filter(lambda e: node in e, all_edges))
    avg = 0
    for e in edges:
        avg += e[2]['weight'] / len(edges)
    return avg

def weight_and_degree(G):
    degrees = dict(G.degree)
    weights = dict(map(lambda n: (n, avg_weight(G, n)), G.nodes))
    return dict(map(lambda p: (p[0], (p[1], weights[p[0]])), degrees.items()))

Now here's a (weighted) graph that has the same properties as you specified above. The weights represent delay times.

import networkx as nx

G = nx.Graph()
G.add_edge('a','b', weight=0.1)
G.add_edge('b','c', weight=0.1)
G.add_edge('d','c', weight=0.1)
G.add_edge('b','e', weight=0.1)
G.add_edge('f','e', weight=0.3)
G.add_edge('f','c', weight=0.2)

If we run the above function on the graph, we can sort by degree and average weight at once like this:

s = dict(sorted(weight_and_degree(G).items(), key=lambda x: (-x[1][0], x[1][1])))
print(' '.join(s.keys())) # b c e f a d

Then you can check the top n results of this list according to the resources you have available, or you can modify the code to only return maximal degree nodes, etc.

References:

Networkx finding common nodes between different shortest paths in a graph - Is there a alternate solution?

1 Answers1