hello, I have a question about the the relationship between the node degree and the shortest paths in the graph. can we say that most of the shortest paths in the graph pass through the nodes with higher degree relative to nodes with low degree?
thanks alot
In general the answer is "No". Node degree play a role for the existence of paths, most certainly, but short paths in terms of total costs may pass many links.
In general the answer is "No". Node degree play a role for the existence of paths, most certainly, but short paths in terms of total costs may pass many links.
Very interesting question!
Indeed, the general answer is certainly no, but if you're asking for relative density, perhaps something can still be said. If by "most" you mean that a randomly selected short path will pass through an arbitrarily selected large degree vertex more often than an arbitrarily selected small degree vertex, then that is true.
For example, let C be a very large cycle and construct a graph G from C by adding a single pendant edge (and corresponding vertex of degree 1) to create a single vertex v of degree 3. If your desired short paths are P_3 (the path on 2 edges), then a randomly selected P_3 in G is unlikely to use v. On the other hand, this randomly selected P_3 is more likely to use v than any other specific vertex in G. Adding more pendant edges incident to v would make the difference more obvious.
Look for betweeness centrality
https://en.wikipedia.org/wiki/Betweenness_centrality
thanks a lot Dr.Colton Magnant . I think I mean the same thing as you said. Can we prove it by mathematics? or just by some example can be described?
To address your last questions, many things can be proven mathematically once the precise statement is in place. Several questions remain: the desired length of the paths, the distribution of degrees in the graph (if you know anything about it), etc.
As Michael noted, this kind of general statement is simply not true, especially from a numerical perspective, which means we must be particularly careful in the statement. From a different perspective, André's answer is appropriate if you want your short paths to go between certain pairs of vertices.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs