Optimal flows on random graphs

Add to your list(s) Download to your calendar using vCal

• van der Hofstad, R (TU Eindhoven)
• Thursday 15 August 2013, 10:00-10:45
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Stochastic Processes in Communication Sciences

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

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.