Query Answering via Decentralized Search
  Expert networks are formed by a group of expert-professionals with different
specialties to collaboratively resolve specific queries posted to the network.
In such networks, when a query reaches an expert who does not have sufficient
expertise, this query needs to be routed to other experts for further
processing until it is completely solved; therefore, query answering efficiency
is sensitive to the underlying query routing mechanism being used. Among all
possible query routing mechanisms, decentralized search, operating purely on
each expert's local information without any knowledge of network global
structure, represents the most basic and scalable routing mechanism, which is
applicable to any network scenarios even in dynamic networks. However, there is
still a lack of fundamental understanding of the efficiency of decentralized
search in expert networks. In this regard, we investigate decentralized search
by quantifying its performance under a variety of network settings. Our key
findings reveal the existence of network conditions, under which decentralized
search can achieve significantly short query routing paths (i.e., between
$O(\log n)$ and $O(\log^2 n)$ hops, $n$: total number of experts in the
network). Based on such theoretical foundation, we further study how the unique
properties of decentralized search in expert networks is related to the
anecdotal small-world phenomenon. In addition, we demonstrate that
decentralized search is robust against estimation errors introduced by
misinterpreting the required expertise levels. To the best of our knowledge,
this is the first work studying fundamental behaviors of decentralized search
in expert networks. The developed performance bounds, confirmed by real
datasets, are able to assist in predicting network performance and designing
complex expert networks.
