TY - GEN

T1 - Navigation in real-world complex networks through embedding in latent spaces

AU - Ban, Xiaomeng

AU - Gao, Jie

AU - Van De Rijt, Arnout

PY - 2010

Y1 - 2010

N2 - Small-world experiments in which packages reach addressees unknown to the original sender through a forwarding chain confirm that acquaintance networks have short paths, a property that was later also discovered in many other networks. They further show that people can find these paths by passing the package on to the acquaintance most socially proximate to the target. This has led researchers to conjecture that perhaps also in many other networks some proximity-based algorithm can be used to find short paths, provided that nodes are given appropriate coordinates. Although potential applications are numerous, ranging from decentralized search to recommendation-based trust to disease control, this conjecture has remained largely unverified. In this paper we apply algorithmic methods to embed nodes in some latent space and employ greedy routing to deliverpackages. Using these methods we empirically investigate the navigability of five real-world complex networks from diverse contexts and of varying topology. In each network, we deliver a majority of packages in fewer than six hops.

AB - Small-world experiments in which packages reach addressees unknown to the original sender through a forwarding chain confirm that acquaintance networks have short paths, a property that was later also discovered in many other networks. They further show that people can find these paths by passing the package on to the acquaintance most socially proximate to the target. This has led researchers to conjecture that perhaps also in many other networks some proximity-based algorithm can be used to find short paths, provided that nodes are given appropriate coordinates. Although potential applications are numerous, ranging from decentralized search to recommendation-based trust to disease control, this conjecture has remained largely unverified. In this paper we apply algorithmic methods to embed nodes in some latent space and employ greedy routing to deliverpackages. Using these methods we empirically investigate the navigability of five real-world complex networks from diverse contexts and of varying topology. In each network, we deliver a majority of packages in fewer than six hops.

UR - http://www.scopus.com/inward/record.url?scp=84880388488&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880388488&partnerID=8YFLogxK

U2 - 10.1137/1.9781611972900.13

DO - 10.1137/1.9781611972900.13

M3 - Conference contribution

AN - SCOPUS:84880388488

SN - 9780898719314

T3 - 2010 Proceedings of the 12th Workshop on Algorithm Engineering and Experiments, ALENEX 2010

SP - 138

EP - 148

BT - 2010 Proceedings of the 12th Workshop on Algorithm Engineering and Experiments, ALENEX 2010

PB - Society for Industrial and Applied Mathematics Publications

T2 - 12th Annual Workshop on Algorithm Engineering and Experiments, ALENEX 2010

Y2 - 16 January 2010 through 16 January 2010

ER -