Source localization in random graphs
Event details
| Date | 16.07.2018 |
| Hour | 17:00 › 19:00 |
| Speaker | Gergely Odor |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Matthias Grossglauser
Thesis advisor: Prof. Patrick Thiran
Co-examiner: Prof. Nisheeth Vishnoi
Abstract
Finding the source of a spreading process on a network using limited information has applications ranging from epidemiology (finding patient zero) to online misinformation (finding the source) and online anonymous messaging (hiding the source). In this thesis, we restrict our focus to sensor-based source localization; our limited information comes from a few sensors that report the time the spreading process has reached each of them. As for the other model parameters, we consider several choices of network topologies, spreading models and sensor selection strategies. Our main focus is on understanding how the network topology affects the difficulty of localizing the source. More specifically, we propose to extend the class of random networks for which the difficulty of the problem is known. In addition to practical applications, questions arising in such rigorous analyses can help understand fundamental properties of the structure of random networks as well.
Background papers
Identifying propagation sources in networks: State-of-the-art and comparative studies, by Jiang, Jiaojiao, et al. IEEE Communications Surveys & Tutorials, 19.1 (2017): 465-481
Metric dimension for random graphs, by Bollobás, Béla, Dieter Mitsche, and Pawel Pralat. arXiv preprint arXiv:1208.3801(2012).
Metadata-Conscious Anonymous Messaging, by Fanti, Giulia, et al. IEEE Transactions on Signal and Information Processing over Networks 2.4 (2016): 582-594.
Exam president: Prof. Matthias Grossglauser
Thesis advisor: Prof. Patrick Thiran
Co-examiner: Prof. Nisheeth Vishnoi
Abstract
Finding the source of a spreading process on a network using limited information has applications ranging from epidemiology (finding patient zero) to online misinformation (finding the source) and online anonymous messaging (hiding the source). In this thesis, we restrict our focus to sensor-based source localization; our limited information comes from a few sensors that report the time the spreading process has reached each of them. As for the other model parameters, we consider several choices of network topologies, spreading models and sensor selection strategies. Our main focus is on understanding how the network topology affects the difficulty of localizing the source. More specifically, we propose to extend the class of random networks for which the difficulty of the problem is known. In addition to practical applications, questions arising in such rigorous analyses can help understand fundamental properties of the structure of random networks as well.
Background papers
Identifying propagation sources in networks: State-of-the-art and comparative studies, by Jiang, Jiaojiao, et al. IEEE Communications Surveys & Tutorials, 19.1 (2017): 465-481
Metric dimension for random graphs, by Bollobás, Béla, Dieter Mitsche, and Pawel Pralat. arXiv preprint arXiv:1208.3801(2012).
Metadata-Conscious Anonymous Messaging, by Fanti, Giulia, et al. IEEE Transactions on Signal and Information Processing over Networks 2.4 (2016): 582-594.
Practical information
- General public
- Free
Contact
- EDIC - [email protected]