Summary
Markov chains are fundamental processes and have been studied in nearly every scientific discipline in the past 100 years. In computer science, reversible Markov chains, also known as random walks, form the basis of many efficient randomised algorithms which have been successfully applied to a variety of complex sampling, learning and optimisation problems.
Nowadays an increasing number of algorithms and processes on networks are based on multiple (concurrent and possibly dependent) random walks, including algorithms for packet routing, content search, graph clustering, link prediction and website ranking. This trend will be reinforced by the steady growth of large-scale networks and massive data sets. However, the existing theory of single random walks is not well-suited to cope with the complexity inherent to multiple random walks, and even for independent walks many fundamental questions remain open.
The goal of this proposal is to develop a systematic and rigorous study of multiple random walks. First, we will analyse this random process via commonly used metrics such as hitting times, cover times, mixing times as well as new quantities which are unique to multiple random walks. Then we will connect these quantities to structural properties of the underlying graph. Finally, these insights will be applied to the design of new efficient randomised algorithms for large graphs and distributed networks.
Nowadays an increasing number of algorithms and processes on networks are based on multiple (concurrent and possibly dependent) random walks, including algorithms for packet routing, content search, graph clustering, link prediction and website ranking. This trend will be reinforced by the steady growth of large-scale networks and massive data sets. However, the existing theory of single random walks is not well-suited to cope with the complexity inherent to multiple random walks, and even for independent walks many fundamental questions remain open.
The goal of this proposal is to develop a systematic and rigorous study of multiple random walks. First, we will analyse this random process via commonly used metrics such as hitting times, cover times, mixing times as well as new quantities which are unique to multiple random walks. Then we will connect these quantities to structural properties of the underlying graph. Finally, these insights will be applied to the design of new efficient randomised algorithms for large graphs and distributed networks.
Unfold all
/
Fold all
More information & hyperlinks
| Web resources: | https://cordis.europa.eu/project/id/679660 |
| Start date: | 01-05-2016 |
| End date: | 30-04-2021 |
| Total budget - Public funding: | 1 400 789,00 Euro - 1 400 789,00 Euro |
Cordis data
Original description
Markov chains are fundamental processes and have been studied in nearly every scientific discipline in the past 100 years. In computer science, reversible Markov chains, also known as random walks, form the basis of many efficient randomised algorithms which have been successfully applied to a variety of complex sampling, learning and optimisation problems.Nowadays an increasing number of algorithms and processes on networks are based on multiple (concurrent and possibly dependent) random walks, including algorithms for packet routing, content search, graph clustering, link prediction and website ranking. This trend will be reinforced by the steady growth of large-scale networks and massive data sets. However, the existing theory of single random walks is not well-suited to cope with the complexity inherent to multiple random walks, and even for independent walks many fundamental questions remain open.
The goal of this proposal is to develop a systematic and rigorous study of multiple random walks. First, we will analyse this random process via commonly used metrics such as hitting times, cover times, mixing times as well as new quantities which are unique to multiple random walks. Then we will connect these quantities to structural properties of the underlying graph. Finally, these insights will be applied to the design of new efficient randomised algorithms for large graphs and distributed networks.
Status
CLOSEDCall topic
ERC-StG-2015Update Date
27-04-2024
Images
No images available.
Geographical location(s)
