Decentralized search in expert networks: Generic models and performance bounds

摘要

We investigate the problem of query answering in expert networks, which are composed of inter-connected experts with various specialties. Upon receiving a query, the expert network is tasked to route this query to experts with sufficient expertise in a timely and reliable manner. However, the efficiency of query answering depends on the underlying query routing protocol being used. Among all possible query routing protocols, decentralized search, operating purely on each expert's local information without any network global knowledge, represents the most basic and scalable routing protocol. However, there is still a lack of fundamental understanding on the efficiency of decentralized search in different expert networks. In this regard, we establish a generic model that can abstract diversified social and structural attributes in various expert networks into a common framework, thus applicable to a wide range of network scenarios. On top of such generic network model, we then study decentralized search by quantifying its performance under a variety of network parameters. 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(log2 n) hops, n: total number of experts in the network). To the best of our knowledge, this is the first work studying fundamental behaviors of decentralized search without relying on strict underlying network structures in expert networks. Experiments in both synthetic and real expert networks confirm the efficacy of the developed performance bounds in understanding and reasoning the network performance.