People's activities in Online Social Networks (OSNs) have generated a massive volume of data to which tremendous attention has been paid in academia and industry. With such data, researchers and third-parties can analyze human beings’ behaviors in social communities and develop more user-friendly services and applications to meet people's needs. However, often times, they face a big challenge of acquiring the data, as the access to such data is restricted by their collectors (e.g., Facebook and Twitter), due to various reasons, such as their user's privacy. In this paper, we intend to shed light on leveraging limited local social network topological properties to effectively and efficiently conduct search in OSNs. The problem we focus on is to discover the connectivity of a group of target users in an OSN, particularly from the perspective of a third-party analyst who does not have full access to the network. For the analyst, even discovering a user's local connections requires issuing a query through OSN APIs (e.g., Facebook Friendlist API or Twitter Followerlist API). We develop searching techniques which demand only a few number of queries for the connectivity discovery.

After conducting an intensive set of experiments on both real-world and synthetic data sets, we found that our proposed techniques perform as well as the centralized detection algorithm, which assumes the availability of the entire data set, in terms of the size of the discovered subgraph connecting all target users as well as the number of queries made in the search. The experiment results demonstrate the effectiveness of incorporating topological properties of social networks into searching in the OSNs.