Existence and emergence of navigability in social networks

Speaker: Emmanuelle Lebhar, CNRS

Affiliation: U. Paris VII, France

Abstract: Social networks, as part of large spontaneous interactions networks, present remarkable properties that are still widely misunderstood. One of them is the navigability property, a.k.a "six degrees of separation", which consists in the existence of very short paths between any pair (e.g. polylogarithmic in the size of the network) that can moreover be discovered locally, using only a very partial information (e.g. the neighborhood). Since the seminal work of Kleinberg on this subject in 2000, the explanation of this phenomenon is investigated among specific probabilistic distributions of additional links over particular classes of graphs. In this talk, we will survey the development of random graph models dedicated to this property and study how a natural dynamic process can converge to such structures, and therefore shed light on the emergence of this natural phenomenon in social networks.