Research On Frequent Pattern Mining With Big Social Graph

With the increasing popularity of graph data,graph mining has become a basic task of graph analysis.Frequent subgraphs and pattern mining as an important part have been widely used in various fields,such as social network distribution,protein detection,and financial fraud detection,etc.The goal of frequent subgraph/pattern mining is to find frequent subgraphs or patterns in the data graph.In the social field,frequent pattern mining has broad application prospects,such as finding frequent cooperation patterns in cooperation graphs.However,in a social graph with dense relationships,finding frequent patterns is an extremely time-consuming task,which makes it difficult to apply existing methods to large social graphs.Therefore,how to complete frequent pattern mining tasks on social graphs within an acceptable time frame has become a key issue for graph mining.Therefore,the main work of this dissertation is as follows:(1)Aiming at the huge-scale problem of frequent pattern mining on large social graphs,the concept of social pattern and a support measurement method based on minimum independent individual are proposed.The concept of social patterns fundamentally reduces the problem scale of frequent pattern mining tasks,which makes it possible to conduct frequent pattern mining on social graphs.At the same time,the support measurement method based on the minimum independent individual enables the support of social patterns to be calculated faster.(2)Aiming at frequent pattern mining tasks on large graphs,a new algorithm framework SocMi is proposed.It is based on a novel structure called pathgraph.As a storage carrier of frequent patterns,the pathgraph contains the necessary information for pattern expansion and support calculation,and can accelerate the process of frequent pattern mining through the merging of pathgraphs.At the same time,we use cache to further optimize the SocMi algorithm.(3)Aiming at the further requirement of timeliness of frequent pattern mining task,an approximate frequent pattern mining algorithm framework ASocMi is proposed.It is based on a rapid exploration strategy to complete the collection of neighbor information of each node in the early stage.At the same time,a complete expansion strategy is proposed to ensure the completeness of pathgraphs.As an inexact algorithm,ASocMi can return nearly complete result set.