A Social Query Model for Decentralized Search

PSKPM: “Your Common House for Capacity Building”

 ABSTRACT
Decentralized search by routing queries over a network is fast emerging as an important research problem, with potential applications in social search as well as peer-to-peer networks [17, 18]. In this paper, we introduce a novel Social Query Model (SQM) for decentralized search, which factors in realistic elements such as expertise levels and response rates of nodes, and has the Pagerank model and certain Markov Decision Processes as special cases. In the context of the model, we establish the existence of a query routing policy that is simultaneously optimal for all nodes, in that no subset of nodes will jointly have any incentive to use a different local routing policy. For computing the optimal policy, we present an efficient distributed approximation algorithm that is almost linear in the number of edges in the network. Extensive experiments on both simulated random graphs and real small-world networks demonstrate the potential of our model and the effectiveness of the proposed routing algorithm.

1. INTRODUCTION
Decentralized search by routing queries over a network is fast emerging as an important research problem cutting across several different areas, with potential applications in social search as well as peer-to-peer networks [17, 18, 1]. Recent years have seen both theoretical [16, 17, 18] and empirical studies [1, 32] on decentralized search, with particular emphasis on small-world networks. In its most basic form, decentralized search considers a network where any node can initiate a “query” for which one or more nodes in the network have a correct “response”. The central task in decentralized search is to efficiently route the query to one of the nodes with the correct response, without making use of a central index of the entire network. In peer-to-peer file sharing networking, the query may take the form of a re-
quest for a certain audio or video file that may be present in only a set of live nodes. In a social search setting, the querymay be a question that gets routed in the social network until some node in the network gives a correct response.
Existing models in decentralized search typically consider deterministic models for the nodes, while allowing randomized routing policies [17]. In several practical scenarios, including social networks as well as peer-to-peer systems, the nodes are far from deterministic. In a social search setting where queries are routed between actors in the network, several nodes may have the expertise to respond correctly, but may be too busy to respond. Further, the expertise levels of different nodes on the topic of query may vary, at times resulting in an incorrect response being generated.1 Peer-to-peer networks face response rate issues for rather different reasons, e.g., the response rate may vary because of sys- tem/network load or when the node is down. Further, the type/amount of files shared by the nodes vary widely, having the same effect as expertise levels in a social network.
Existing models for decentralized search were not designed to account for such practical factors.

silakan download dan baca disini:

www.google.com/research/pubs/archive/