Research On Sampling Techniques For Large-scale Social Networks

The popularity of social network services and the development of big data have not only offered people new forms of social interactions but also facilitated research on social network analysis.The difficulty brought by the rapid growth of network scale and data volume has led to the emergence of social network sampling techniques which have consequently become a significant research topic of social network analysis.The key objective of sampling technique design is to determine the process of constructing a sample and the number of needed samples so as to efficiently and effectively work over large-scale social networks.In this dissertation,we focus on the social network sampling techniques and their applications,especially on random reverse reachable set(RR-set)sampling and random walks sampling on temporal networks.RR-set sampling technique has been widely used in influence maximization(IM)problem over social networks.Compared with Monte Carlo simulation and other sam-pling techniques,RR-set sampling technique is more efficient and is able to provide a theoretical guarantee for influence estimation.Due to the diversification of social networks,people began to consider IM problems with different constraints.For event-based social network,a new type of social networks,this dissertation proposes a general formulation of influential event organization problem and designs algorithms for this problem based on RR-set sampling,which have provable approximation ratios.Random walk sampling technique has been mainly employed in personalized PageRank(PPR)problem on static networks,which aims to identify each node's impor-tance within a given network.This dissertation proposes a new random walk sampling technique over discrete temporal networks then extends the PPR problem from static networks to temporal networks.Using matrix calculation and the random walk sam-pling technique,we propose several algorithms and provide performance guarantees.To evaluate the performance of proposed methods,we conduct extensive experi-ments over real-world social network datasets.Our experimental results show that the performance of our algorithms corresponds with our theoretical analysis and demon-strate the superiority of our works.The results also confirm that our algorithms can run properly over large-scale social networks.