Optimal flows on random graphs
Seminar Room 1, Newton Institute
AbstractWe investigate minimal-weight problems on the configuration model, in which flow passes through the network minimizing the total weight along edges. In practice, one is both interested in the actual weight of the minimal weight path, which represents its cost, as well as the number of edges used or hopcount, as this is often a good measure of the delay observed in the network.
We assume that the edge weights are independent continuous random variables, leading to first passage percolation on the configuration model. We then investigate the total weight and hopcount of the minimal weight path. We study how the minimal weight and hopcount depend on the structure of the edge weights as well as on the structure of the graph. Our proofs crucially rely on the connection between first passage percolation and continuous-time branching processes, which is due to the tree-like nature of the configuration model.
The above research is inspired by transport in real-world networks, such as the Internet. Measurements have shown fascinating features of the Internet, such as the `small world phenomenon'. The small-world phenomenon states that typical distances in the network under consideration is small. Also, the degrees in the Internet are rather different from the degree structure in classical random graphs. Internet is a key example of a complex network, other examples being the Internet Movie Data Base, social networks, biological networks, the WWW, etc.
[This is joint work with Gerard Hooghiemstra, Shankar Bhamidi, Piet Van Mieghem, Henri van den Esker and Dmitri Znamenski.]
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.