The Research Of Frequent Community Search Algorithms In Temporal Graphs

Community mining is a fundamental graph mining task.In many existing graph data,the edges in the graph are typically associated with temporal information;notable examples in-cluding scientific collaboration networks,telecommunication network,WeChat social net-work and so on.Most existing community discovery algorithms focus mainly on traditional graph data which cannot be directly used for mining temporal graphs.In this thesis,we study the frequent community mining problem on temporal graphs.Our goal is to identify all the frequent community structures from a temporal graph.Traditional community models,such as k-core,clique,k-truss,k-edge connected component,are all based on general graph data which cannot be used for finding frequent communities on tem-poral graphs.To overcome this issue,we propose a novel frequent community model,called k-star,tailored for temporal graphs.Real-life temporal graphs are typically very large,and thus directly finding communities on such massive temporal graphs are very costly.To efficiently finding the frequent commu-nities on massive temporal graphs,we propose a temporal graph reduction algorithm.Our algorithm can prune the temporal graph based on a concept called weak-core subgraph.There are two technical challenges to implement such a graph reduction method:(1)how to com-pute the frequent degrees of the nodes and(2)how to maintain the frequent degrees of the neighbor nodes.To overcome these challenges,we develop an interval decomposition algo-rithm to compute the frequent degree and maintain the neighbors' frequent degrees efficiently.To further reduce the community search cost,we also propose a strong-neighbor pruning al-gorithms and a dummy-degree pruning algorithm to prune the search space.Finally,we conduct extensive experiments on several real-life massive temporal graph datasets.The experimental results show that our graph reduction and pruning technique are very effective.We also compare our k-star model with other baseline models using case stud-ies,and the results demonstrate the effectiveness of our model.Additional,we also perform scalability testing for our algorithms,and the results show that our algorithm scales very well on large graphs.