next up previous contents
Next: Analogic machine to compute Up: Small world problem estimated Previous: Small world problem estimated   Contents

Stating the problem

Given a random graph $ G$ with $ N$ nodes, $ G(N,E)$. The average number of connections per node6 is M. In other words, each node has $ M$ connections to other nodes. Take randomly two nodes out of the graph: what is the average path length between these two nodes? To compute the average path length, we always choose the shortest distance7.

Tiziano Mengotti 2004-03-27