Random walk on four fully linked hubs

Question

Four network hubs are all directly connected to one another (every hub links to the other three). A data packet hops each step to a uniformly random neighbor of its current hub.

In the long run, what fraction of time does the packet sit at any one chosen hub?

Accepted Answer

For a uniform random walk, the long-run share of a node is proportional to its degree, the number of connections. Here every hub connects to the other three, so every hub has the same degree, 3. When all degrees are equal, the shares are equal too. With four hubs each of degree 3, the total of the degrees is 4 	imes 3 = 12, and \pi = \frac{3}{12} = \frac{1}{4} 	ext{ per hub}. So the packet sits at any given hub one quarter of the time, an even split, as symmetry demands. Takeaway. When every node has the same number of connections (a regular network), the degree rule collapses to a uniform …

Random walk on four fully linked hubs

Your answer

Discussion

Learn the concepts

Related questions