Topology Aware Graph Sampling Algorithms for Scalable Social Network Analysis

Abstract

Social networks produce massive volumes of data with many complex relationships, or graphs, with a need for efficient and scalable data analysis. But the traditional graph sampling methods lack the ability to capture some key graph topological information, such as community structure, node centrality, cluster behavior, etc., and thus result in less accurate analysis. In this paper, to tackle the problem, a topology-aware graph sampling (TAGS) framework for scalable social network analysis is proposed. The framework combines topology feature extraction, node importance estimation, and adaptive sampling to create representative subgraphs, which ensures the integrity of topology. The Social Circles data set, comprising Facebook, Twitter, and Google+ social networks, is used for the experiments. The results show that the proposed method can achieve a good structural preservation score (95.5%), sampling accuracy (95.6%), and lower execution time (178 ms) than the execution time of baseline methods (253 ms). Also, it saves 315 MB of memory, which means that it's more scalable. The results validate the fact that topology-aware mechanisms can be extremely useful in both effectiveness and efficiency for graph sampling problems. The suggested framework can be used in the big social network analysis applications that demand high performance and consistency of structure.