Research On Frequent Pattern Mining Algorithms Based On Location Information In Social Networks

With the popularity of mobile internet and the growing size of social networks,mining information about users in the network has become a key concern for researchers.Frequent Pattern Mining(FPM)aims to discover specific patterns of user activity in the network,which in turn can be used to provide more accurate and personalised services to users.However,existing work tends to focus on social networks as a whole,ignoring the differences between certain geographical areas of the network,such as cities,towns and communities.In this paper,we therefore focus on the Geosocial Network(GSN),a social network containing geographical information,and the patterns generated by specific regions within the network.In addition to the challenge of quickly locating regions in GSNs,FPM based on geosocial networks also faces the challenge of efficient subgraph retrieval.To address these problems,we propose three algorithms: a spatial index-based mining algorithm,an edge mapping-based mining algorithm,and an approximate mining algorithm.First,this paper presents the geosocial network graph-based FPM problem(Gs FPM).In order to quickly locate the target mining region,this paper proposes a neighbourhood-aware R-tree,a spatial index structure to speed up the retrieval of subgraphs from large graphs.The Na R-tree is a variant of the R-tree in which each non-leaf tree node further maintains information about the region associated with it.In this paper,we propose a local search algorithm,Gs FPM-Na R,based on the Na R-tree,which does not need to traverse the entire graph to complete subgraph retrieval,thus improving mining efficiency.In addition,the algorithm makes full use of the node and edge information stored in the Na R-tree index structure in order to avoid generating candidate patterns that do not exist in the graph.Secondly,the concept of Minimum Image of Edge-Based Support(MNIE)is proposed as a way to evaluate the support,which can make full use of the region information maintained by the index structure and further speed up the support calculation.Based on the Na R-tree index structure and MNIE,this paper proposes an efficient mining algorithm,Gs FPM-MNIE,which adopts an inert retrieval strategy to reduce the frequency of subgraph retrieval.A detailed analysis of the time complexity of the algorithm Gs FPM-MNIE is also presented in this paper.To further accelerate the mining process,based on the algorithm Gs FPM-MNIE,this paper proposes an efficient approximation algorithm,Gs FPM-A,which uses a sampling-and-hold method between uniform random edge sampling and non-uniform random edge sampling to reduce the network size and significantly improve the performance of the algorithm by sacrificing a certain accuracy rate.Finally,we conduct extensive experiments on real social network datasets to demonstrate the efficiency and effectiveness of our solution.