CODEWITHSUNDEEP
pythonnetworkxgraph-theory
intStdu
intStdu

Reputation: 291

Networkx - find the most appearing paths in weighted network

I have a directed graph with 481 nodes and 6817 edges (weight is the number of times the edge appears, otherwise it would be around 4 million edges). The graph is shown here:

enter image description here

I want to find the paths from the outer most nodes that enter to the center of the graph most of the times (perhaps the paths with the overall highest weight?). I have calculated the eigenvector centrality of the nodes and made a top 20. Those nodes are the ones that appear in the center. What i have tried:

d = g.successors(top20nodes[0])
h = g.subgraph(d)

This is a way to only get the nodes that eventually end at the node with in this case, the highest eigenvector centrality. However, I do not know how to get the n most appearing (most weighted) paths leading to that node.

My end result would ideally be this, the gray nodes are only to make it clear that I am only interested in the n most appearing paths. In this case, those 4 red paths to the center:

enter image description here

I am not necessarily looking for the exact code, I just do not know how to proceed from here. Anybody has a clue how to achieve this?

Upvotes: 1

Views: 1625

Answers (1)

vurmux
vurmux

Reputation: 10020

Note, that my solution is not not fully optimal, in some cases it can return not-the-best paths

I thought up an algorithm for you. It has several assumptions so it is not best-of-the best. But it should return pretty good results.

Firstly, you should define your graph center (I left it beyond my algorithm). Once you defined it, you should replace all your center nodes to only one - The Main Center Node (don't forget about edges). After it, my algorithm begins.

It starts the BFS tree from the center node with the defined depth. Here is the main imperfect part: if you will have two paths between two nodes - long-heavy and short-light, the short-light will be chosen. I am not sure if it will be critical for your graph, but looks like it will not (the picture is not very informative).

After the BFS tree is built, it summarizes all weigths of BFS paths and sorts them. Then you can just choose the first X paths.

I hope it will help you to solve your problem :)

import networkx as nx

# Create graph
G = nx.DiGraph()
G.add_nodes_from([1,6,7,8,9,10,11,12,13,14,15,16,17])
G.add_weighted_edges_from([
    (6,1,2),
    (7,1,5),
    (10,1,7),
    (12,1,1),
    (15,1,4),
    (17,1,6),
    (8,6,5),
    (8,7,8),
    (9,8,2),
    (11,10,1),
    (13,12,5),
    (14,13,6),
    (16,15,3),
    (16,14,4),
    (14,16,1),
])

# Get the BFS tree. 1 is the center, 100 is the BFS length. Note, that
# long lengths MAY waste a lot of computing time
B = nx.bfs_tree(G, 1, 100)
# Get our center
root = list(v for v, d in B.in_degree() if d == 0)[0]
# Get all leaves _in_BFS_tree
leaves = (v for v, d in B.out_degree() if d == 0)
# Get all paths
all_paths = [nx.shortest_path(B, root, l) for l in leaves]
# Get all sorted pairs [path, path_length]
result = sorted(
    [
        (
            path, sum((G.edges[path[i+1], path[i]]['weight'])
            for i in range(len(path) - 1))
        )
        for path in all_paths
    ],
    key=lambda x: x[1],
    reverse=True
)

result
[([1, 12, 13, 14], 12),
 ([1, 6, 8, 9], 9),
 ([1, 10, 11], 8),
 ([1, 15, 16], 7),
 ([1, 17], 6),
 ([1, 7], 5)]

Upvotes: 1

Related Questions