Decentralized search in networks using homophily and degree disparity

Özgür Şimşek, David D. Jensen

Research output: Chapter in Book/Report/Conference proceedingChapter

30 Citations (Scopus)

Abstract

We propose a new algorithm for finding a target node in a network whose topology is known only locally. We formulate this task as a problem of decision making under uncertainty and use the statistical properties of the graph to guide this decision. This formulation uses the homophily and degree structure of the network simultaneously, differentiating our algorithm from those previously proposed in the literature. Because homophily and degree disparity are characteristics frequently observed in real-world networks, the algorithm we propose is applicable to a wide variety of networks, including two families that have received much recent attention: small-world and scale-free networks.
Original languageEnglish
Title of host publicationProceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05): Edinburgh, Scotland, UK, July 30 - August 5, 2005
EditorsLeslie Pack Kaelbling, Alessandro Saffiotti
PublisherProfessional Book Center
Pages304-310
Number of pages7
Publication statusPublished - 2005
Event19th International Joint Conference on Artificial Intelligence - Edinburgh, UK United Kingdom
Duration: 30 May 20055 Aug 2005
http://ijcai.org/past/ijcai-05/

Conference

Conference19th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI-05
CountryUK United Kingdom
CityEdinburgh
Period30/05/055/08/05
Internet address

Fingerprint Dive into the research topics of 'Decentralized search in networks using homophily and degree disparity'. Together they form a unique fingerprint.

Cite this