Extracting A Representative User Subset From Social Networks

Extracting different user subsets is a critical research in the field of social networks.These existing studies can be divided into two aspects:(1)extracting the representative subset only according to users' characteristics;(2)extracting the representative subset only according to the network topology.However,the subset extracted from a single aspect is not representative enough,because only a few features are preserved.We propose new approaches for this problem and we extract the representative user subset towards both users'characteristics and topological features in order to make the subset as similar as possible to the original set.In conclusion,this paper consists of the following achievements:(1)We firstly introduce the existing work about extracting the user subset and analyze why such work cannot solve our problem,which has laid the foundation for the next work.We focus on formulating the problem of extracting the representative user subset and prove the NP-Hardness of this problem.We propose the approach called K Sampling(KS)to ex-tract the representative user subset.We firstly run clustering algorithm to split users into different clusters according to characteristics.We design the objective function which ag-gregates the indicator of both users' characteristics and topological features.Then we run the heuristic greedy algorithm to sample the representative user subset.Experiments show that KS significantly outperforms existing approaches in terms of extracting representative user subset.(2)Based on KS,we further propose an optimized approach called Affinity Propaga-tion Community Detection Sampling(ACS).We propose an improved version of Affinity Propagation clustering algorithm which takes considerations of users' characteristics and topological features.After clustering,we shift some deviation points which have similar characteristics but different topological features.Also,we run the community detection algorithm to form communities in each cluster.In addition,the community detection algo-rithm would ignore users with fewer relationships.Thus,we run Depth-First-Search(DFS)algorithm to form more communities which is beneficial to the pruning later.Finally,we run the heuristic greedy algorithm with pruning strategy to sample the user subset according to the objective function.Experiments show that ACS outperforms existing methods and we visualize the results to demonstrate that ACS can extract more representative user subset.In conclusion,extracting representative user subset from social networks towards users'characteristics and topological features provides some references for the related researches.