Abrahao: /* Network's shortest paths */

2010-06-13T00:24:49Z

Network's shortest paths

← Older revision		Revision as of 00:24, 13 June 2010
Line 1:		Line 1:
	==Network's shortest paths==		==Network's shortest paths==

	'''Team''': [[Sergey Melnik]], [[Roberta Sinatra~~]], [[Bruno Abrahao~~]], [[Michael Szell]], [[Drew Levin]]		'''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):

Sergey: 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 ...

2010-06-11T05:00:56Z

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 ...

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 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):

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.

Network's shortest paths - Revision history

Abrahao: /* Network's shortest paths */

Sergey: 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 ...