Go to main site


Emergence of Navigability in Networks


Event details

Date and time 11.07.2019 14:0016:00  
Place and room
Speaker Akhil Arora
Category Conferences - Seminars
EDIC candidacy exam
Exam president: Prof. Karl Aberer
Thesis advisor: Prof. Robert West
Co-examiner: Prof. Matthias Grossglauser

Navigability, defined as the ability to efficiently maneuver from a source to a target node, is one of the most important functions of any network. Maintaining and improving the navigability of real-world networks is therefore an important task. Having said that, our overarching research goal is to devise methods for improving the navigability of online encyclopedic systems, with Wikipedia being the primary use-case.
In this proposal, we provide a discussion of three existing works in the broad field of network navigability. We begin with a description of a network model devised by Clauset and Moore, which explains the development of properties required for navigability in small-world networks. Next, we discuss the work by Gulyas et al., which employs game-theory to construct navigation skeletons of real-world networks, thereby facilitating identification of edges critical for ensuring navigability. Lastly, we provide a description of an automatic link placement scheme proposed by Paranjape et al., which utilizes human navigation traces from server logs to recommend new links to be added to a website. We conclude with our proposal for operationalization of link insertion, performing cross lingual Wikification, and identification of navigation critical links in Wikipedia.
Background papers
How Do Networks Become Navigable, by Clauset, A. and Moore C.arXiv 2004.
Navigable networks as Nash equilibria of navigation games, by Gulyás, A., et al. Nature Communications 6 (2015):7651.
Improving Website Hyperlink Structure using Server Logs, by A. Paranjpe, R. West, L. Zia, J. Leskovec. In WSDM 2016.

Practical information

  • General public
  • Free


  • edic@epfl.ch


EDIC candidacy exam