Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Navigating Low-Dimensional and Hierarchical Population Networks
verfasst von : Ravi Kumar, David Liben-Nowell, Andrew Tomkins
Erschienen in: Algorithms – ESA 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Social networks are
navigable small worlds
, in which two arbitrary people are likely connected by a short path of intermediate friends that can be found by a “decentralized” routing algorithm using only local information. We develop a model of social networks based on an arbitrary metric space of points, with population density varying across the points. We consider
rank-based friendships
, where the probability that person
u
befriends person
v
is inversely proportional to the number of people who are closer to
u
than
v
is. Our main result is that greedy routing can find a short path (of expected polylogarithmic length) from an arbitrary source to a randomly chosen target, independent of the population densities, as long as the doubling dimension of the metric space of locations is low. We also show that greedy routing finds short paths with good probability in tree-based metrics with varying population distributions.