Probabilistic data structure-based community detection and storage scheme in online social networks

摘要

With the wide popularity of various social network sites such as - Facebook, Twitter, and Instagram; processing, storage, and analysis of a large volume of data are becoming challenging issues. In general, social networks are assumed to be graphs having nodes for representation of a group of persons in order to explore the relationship between them for Social Network Analysis (SNA). Analysts claim that interconnections in these networks are the reflection of social structure of individual where personalities with common attributes often occupy similar positions. Such similarities are caused by the prospects, opportunities, sensitivities and perceptions created by these similar network positions. Thus, clustering of these individuals is necessary to analyse their common characteristics. However, most of the existing clustering algorithms considered for community detection in SNA have high memory requirements especially in online social networks. So, to mitigate these issues, this paper proposes a novel clustering scheme for community detection for fast access, storage and retrieval of data using Probabilistic Data Structures (PDS). In the proposed scheme, Bloom filter has been used for clustering and Quotient filter has been used for storage and access of cluster nodes. It has been experimentally proved that the proposed scheme provides significant improvement in computational time which is reduced by 64% and 79% respectively in comparison to the linked list and adjacency matrix. Moreover, Quotient filter based storage schema significantly enhances the effectiveness of the proposed scheme over conventional storage methods. (C) 2018 Elsevier B.V. All rights reserved.