Navigating networks by using homophily and degree

Özgür Şimşek, David Jensen

Research output: Contribution to journalArticle

  • 59 Citations

Abstract

Many large distributed systems can be characterized as networks where short paths exist between nearly every pair of nodes. These include social, biological, communication, and distribution networks, which often display power-law or small-world structure. A central challenge of distributed systems is directing messages to specific nodes through a sequence of decisions made by individual nodes without global knowledge of the network. We present a probabilistic analysis of this navigation problem that produces a surprisingly simple and effective method for directing messages. This method requires calculating only the product of the two measures widely used to summarize all local information. It outperforms prior approaches reported in the literature by a large margin, and it provides a formal model that may describe how humans make decisions in sociological studies intended to explore the social network as well as how they make decisions in more naturalistic settings.
Original languageEnglish
Pages (from-to)12758-12762
Number of pages5
JournalProceedings of the National Academy of Sciences
Volume105
Issue number35
DOIs
StatePublished - 2 Sep 2008

Fingerprint

network
decision
social network
method
system
human being
distribution
power
world
structure
individual
information
problem
model
analysis

Cite this

Navigating networks by using homophily and degree. / Şimşek, Özgür; Jensen, David.

In: Proceedings of the National Academy of Sciences, Vol. 105, No. 35, 02.09.2008, p. 12758-12762.

Research output: Contribution to journalArticle

Şimşek, Özgür; Jensen, David / Navigating networks by using homophily and degree.

In: Proceedings of the National Academy of Sciences, Vol. 105, No. 35, 02.09.2008, p. 12758-12762.

Research output: Contribution to journalArticle

@article{1b4896a3151f4707ae2bb7b1df1d82d7,
title = "Navigating networks by using homophily and degree",
abstract = "Many large distributed systems can be characterized as networks where short paths exist between nearly every pair of nodes. These include social, biological, communication, and distribution networks, which often display power-law or small-world structure. A central challenge of distributed systems is directing messages to specific nodes through a sequence of decisions made by individual nodes without global knowledge of the network. We present a probabilistic analysis of this navigation problem that produces a surprisingly simple and effective method for directing messages. This method requires calculating only the product of the two measures widely used to summarize all local information. It outperforms prior approaches reported in the literature by a large margin, and it provides a formal model that may describe how humans make decisions in sociological studies intended to explore the social network as well as how they make decisions in more naturalistic settings.",
author = "Özgür Şimşek and David Jensen",
year = "2008",
month = "9",
doi = "10.1073/pnas.0800497105",
volume = "105",
pages = "12758--12762",
journal = "Proceedings of the National Academy of Sciences of the United States of America",
issn = "0027-8424",
publisher = "Proceedings of the National Academy of Sciences",
number = "35",

}

TY - JOUR

T1 - Navigating networks by using homophily and degree

AU - Şimşek,Özgür

AU - Jensen,David

PY - 2008/9/2

Y1 - 2008/9/2

N2 - Many large distributed systems can be characterized as networks where short paths exist between nearly every pair of nodes. These include social, biological, communication, and distribution networks, which often display power-law or small-world structure. A central challenge of distributed systems is directing messages to specific nodes through a sequence of decisions made by individual nodes without global knowledge of the network. We present a probabilistic analysis of this navigation problem that produces a surprisingly simple and effective method for directing messages. This method requires calculating only the product of the two measures widely used to summarize all local information. It outperforms prior approaches reported in the literature by a large margin, and it provides a formal model that may describe how humans make decisions in sociological studies intended to explore the social network as well as how they make decisions in more naturalistic settings.

AB - Many large distributed systems can be characterized as networks where short paths exist between nearly every pair of nodes. These include social, biological, communication, and distribution networks, which often display power-law or small-world structure. A central challenge of distributed systems is directing messages to specific nodes through a sequence of decisions made by individual nodes without global knowledge of the network. We present a probabilistic analysis of this navigation problem that produces a surprisingly simple and effective method for directing messages. This method requires calculating only the product of the two measures widely used to summarize all local information. It outperforms prior approaches reported in the literature by a large margin, and it provides a formal model that may describe how humans make decisions in sociological studies intended to explore the social network as well as how they make decisions in more naturalistic settings.

UR - https://doi.org/10.1073/pnas.0800497105

U2 - 10.1073/pnas.0800497105

DO - 10.1073/pnas.0800497105

M3 - Article

VL - 105

SP - 12758

EP - 12762

JO - Proceedings of the National Academy of Sciences of the United States of America

T2 - Proceedings of the National Academy of Sciences of the United States of America

JF - Proceedings of the National Academy of Sciences of the United States of America

SN - 0027-8424

IS - 35

ER -