Network's shortest paths: Difference between revisions
From Santa Fe Institute Events Wiki
(New page: ==Network's shortest paths== '''Team''': Sergey Melnik, Roberta Sinatra, Bruno Abrahao, Michael Szell, Drew Levin Consider a random network consisting of ''N'' nodes ...) |
|||
| Line 1: | Line 1: | ||
==Network's shortest paths== | ==Network's shortest paths== | ||
'''Team''': [[Sergey Melnik]], [[Roberta Sinatra | '''Team''': [[Sergey Melnik]], [[Roberta Sinatra]], [[Michael Szell]], [[Drew Levin]] | ||
Consider a random network consisting of ''N'' nodes where each pair of nodes is connected with a given probability ''p'' ([http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model see Erdos-Renyi random graph]). The question is about the shortest path through the network from one node to another (also called geodesic path, or intervertex distance): | Consider a random network consisting of ''N'' nodes where each pair of nodes is connected with a given probability ''p'' ([http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model see Erdos-Renyi random graph]). The question is about the shortest path through the network from one node to another (also called geodesic path, or intervertex distance): | ||
Latest revision as of 00:24, 13 June 2010
Network's shortest paths
Team: Sergey Melnik, Roberta Sinatra, Michael Szell, Drew Levin
Consider a random network consisting of N nodes where each pair of nodes is connected with a given probability p (see Erdos-Renyi random graph). The question is about the shortest path through the network from one node to another (also called geodesic path, or intervertex distance):
Can we calculate analytically (and exactly) the probability distribution of shortest paths in such a network? That is, how likely it is that a pair of nodes chosen at random will be distance D apart. For distance D=1 the answer is obviously p. What are such probabilities for distances D=2, D=3, D=4, etc.?
Note that the network has a finite number of nodes (which is not necessarily large) and there are only 2 parameters here, N and p. This is a simple yet fundamental question and there is much more to follow in terms of immediate applications and new theories once we answer it.