Efficient Event Stream Dissemination In Online Social Networks Based On Community Detection

Over the past decades,social networking applications have spread rapidly.People communicate with their friends through social networks almost everyday.Popular social networking applications have a large number of active users.Social network occupies an important position in people's lives.In large-scale Online Social Network(OSN)systems,event stream dissemination incurs costly inter-servder communication due to the per-user view data storage.To solve the problem,existing schemes commonly leverage the social graph structures to save redundant inter-server traffics across social links.The state-of-the-art scheme reduces the inter-server traffics by fully exploiting the proposed hub-structure,based on the observation of high cluster coefficient in OSNs.In order to find the best hub-structure,however,such a scheme needs to identify the global densest sub-graph by iteratively removing the node with the minimum weighted degree.Such a process causes a worst computation cost of O(9)~2),making the social piggyback scheme unscalable for real-world large-scale OSN graphs.In this work,in order to solve the problem that the traditional method is unscalable,we propose a novel scheme by exploiting the social community for event stream dissemination.We first detect the social communities in a social graph by using an efficient community detection algorithm based on distance dynamics.For each community,we then design a heuristics algorithm to fully leverage the hub-structure.The heuristics algorithm explores the hub-structure center on the node with maximum degree in each iteration.We collect large-scale datasets and conduct comprehensive experiments to evaluate our design.The results show that our design significantly reduces the communication overhead and computing time compared to existing schemes,respectively.