Tata Institute of Fundamental Research
Exploration On Dynamic Networks
Wednesday Colloquia
Speaker:
W.T.F. den Hollander (Mathematisch Instituut
Universiteit Leiden
Postbus 9512
2300 RA Leiden
The Netherlands)
Date:
Wednesday, 24 Jan 2018, 16:00 to 17:00
Venue:
AG-66 (Lecture Theatre)
(Scan to add to calendar)
Abstract:
Search algorithms on networks are important tools for the organisation of large data sets. A key example is Google PageRank, which assigns a numerical weight to each webpage, with the purpose of measuring its relative importance. The weighting is achieved by exploration.
Networks are modelled as graphs, complex networks as random graphs, and search algorithms as random walks. The mixing time of a random walk on a random graph is the time it needs to approach its stationary distribution.
Many real-world networks are dynamic in nature. In this talk we investigate what happens when at each unit of time a certain fraction of the edges is randomly rewired. We investigate three regimes: fast, moderate and slow dynamics. The mixing time in these regimes exhibits surprising behaviour.
| Speaker: | W.T.F. den Hollander (Mathematisch Instituut Universiteit Leiden Postbus 9512 2300 RA Leiden The Netherlands) |
| Date: | Wednesday, 24 Jan 2018, 16:00 to 17:00 |
| Venue: | AG-66 (Lecture Theatre) |
(Scan to add to calendar)
Abstract:
Search algorithms on networks are important tools for the organisation of large data sets. A key example is Google PageRank, which assigns a numerical weight to each webpage, with the purpose of measuring its relative importance. The weighting is achieved by exploration.
Networks are modelled as graphs, complex networks as random graphs, and search algorithms as random walks. The mixing time of a random walk on a random graph is the time it needs to approach its stationary distribution.
Many real-world networks are dynamic in nature. In this talk we investigate what happens when at each unit of time a certain fraction of the edges is randomly rewired. We investigate three regimes: fast, moderate and slow dynamics. The mixing time in these regimes exhibits surprising behaviour.
Networks are modelled as graphs, complex networks as random graphs, and search algorithms as random walks. The mixing time of a random walk on a random graph is the time it needs to approach its stationary distribution.
Many real-world networks are dynamic in nature. In this talk we investigate what happens when at each unit of time a certain fraction of the edges is randomly rewired. We investigate three regimes: fast, moderate and slow dynamics. The mixing time in these regimes exhibits surprising behaviour.