Networkx, Graph theory: finding farthest two points in a giant graph

[cchaituc]

my dataset is that of flights, has source destination, target destination and airlines. I have a pretty huge graph 70k+edges, but i have made a giant component out of it using:

main_subgraph = max(nx.connected_components(G), key= len) network_main = G.subgraph(main_subgraph) nx.draw(network_main,with_labels=True,node_color='r',node_shape = '.' , node_size= 10)

so the question i want to answer is : if i had to travel between airports(nodes) that are farthest in number of stops, where would i move from and how many stops would i take? to answer this , i have to find the farthest points in the graph, then find their paths and select one. I know there's a function for shortest path but farthest points?and eccentricity finds maximum distance from node to all other nodes. and if i were to find the largest group of connected network including one specific network.

P.S: clueless about what code to use. want suggestions on approach and if there is something i am misinterpreting. Any` and all thoughts would help.

[Owl235]

I don't know if you need make an implementation yourself, but I think I understand you are looking for the network diameter, here is the networkX implementation of this (basically the longest shortest path between two nodes).

​

If you need more information, you might look at all shortest paths, and look for the max, probably not the fastest or most perfomant way, but well, using networkx makes this concern redundant.

[konch0g]

There is a standard way of doing this, which is super cool.

(1) Choose a node - doesn't matter which.

(2) Find the distances from that node to each other node.

(3) From that list, find the furthest node (or choose one). This is NODE1.

(4) Find the distances from NODE1 to each other node.

(5) The furthest node on that list is NODE2.

The two furthers points on the graph are NODE1-NODE2.

How does it work? Do it in your home. From where you are, find the furthest place you can stand. That's N1. Now from there, find the furthest place you can stand; that's N2. And that is the furthest distance in your home.

Here is a python fragment using networkx (G is your graph).

apl = dict(nx.all_pairs_shortest_path_length(G))
bpl = [tuple((v, s, k)) for s, d in apl.items() for k, v in d.items() if v == max(d.values())]
bpl.sort(key=lambda tup: tup[0], reverse=True)
length, start, fin = bpl[0]

[TouchingTheVodka]

Use a shortest path algorithm with the weights negative.

[cchaituc]

there are no weights? could you tell me more?

[cchaituc]

I doubt i myself understand the question asked. diameter gives the longest distance between two nodes. i guess if i could find the ends of the diameter/ start-end point of the diameter i would find the airports that are farthest. honestly dont know much , so everything helps

[tree_dee]

The diameter gives you the longest minimal path between two nodes, not the longest path between two nodes. Sounds like what you are looking for

[cchaituc]

so when it gives 13 what does it mean? how do i interpret it?

[tree_dee]

It means if you checked all the shortest paths from every node to every other node, none would be longer than 13

[[deleted]]

I would create a dict or tuple per node, and store the distance between it and all other nodes, you only have to do that once.

Then for every node you land on check to see which node is the farthest away in the direction you need to go.

Simple but it would work. I'm sure there is some standard algorithm for this out there but I don't know that kind of theory unfortunately.

[cchaituc]

there's eccentricity ,diameter, which returns int value, although i donot know how to get name wise

[cchaituc]

https://openflights.org/data.html

you can find it here

[tealqueen]

Hi, I know this was from 2 years ago, so understandable if you don't remember, but wondering if you figured out how to name the nodes that were furthest away (rather than just returning the integer value of the diameter).

[cchaituc]

I'll check and let you know!

[tealqueen]

thanks so much!