Local View based Connectivity Search in Online Social Networks


One of the challenges in social media research is that, often times, researchers or third parties could not obtain the massive of data collected by a limited number of 'big brothers' (e.g., Facebook and Google). In this paper, we shed light on leveraging social network topological properties and local information to effectively conduct search in Online Social Networks (OSN). The problem we focus on is to discover the reachability of a group of target people in an OSN, particularly from the perspective of a third-party analyst who does not have full access to the OSN. We developed effective and efficient detection techniques which demand only a small number of queries to discover people's connections (e.g. friendship) in the OSN. After conducting experiments on real-world data sets, we found that our proposed techniques perform as well as the centralized detection algorithm, which assumes the availability of the global information in the OSN.

Meeting Name

INFOCOM 2019 - IEEE Conference on Computer Communications Workshops, INFOCOM WKSHPS 2019


Computer Science

Research Center/Lab(s)

Center for High Performance Computing Research


National Science Foundation, Grant CCF-1533918

Keywords and Phrases

local view; minimum steiner tree; online social networks; search; subgraph connectivity

International Standard Book Number (ISBN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2019 , All rights reserved.

Publication Date

01 Apr 2019