Social network search as a volatile multi-armed bandit problem

Zahy Bnaya, Rami Puzis, Roni Stern, Ariel Felner

Human 2 (2), 84, 2013

In many cases the best way to find a profile or a set of profiles matching some criteria in a social network is via targeted crawling. An important challenge in targeted crawling is choosing the next profile to explore. Existing heuristics for targeted crawling are usually tailored for specific search criterion and could lead to short-sighted crawling decisions. In this paper we propose and evaluate a generic approach for guiding targeted crawling which is based on recent developments in Artificial Intelligence. Our approach, based on the recently introduced variant of the Multi-Armed Bandit problem with volatile arms (VMAB), aims to provide a proper balance between exploration and exploitation during the crawling process. Unlike other heuristics which are hand tailored for specific type of search queries, our approach is general-purpose. In addition, it provides provable performance guarantees. Experimental results indicate that our approach compares favorably with the best existing heuristics on two different domains.