Research On Algorithms Of Cohesive Subgraph Mining In Large-Scale Graphs

Graphs as data structures representing the relationship between entities are widely applied in modeling and analysis in areas such as complex systems,large-scale integrated circuits,and social networks.Large-scale graphs generally exhibit global sparsity but local cohesiveness,and these local cohesive structures represent key features of graphs and have important applications in community search,information propagation,advertising recommendations and other application areas.Therefore,it is necessary to compute and mine the dense component(cohesive subgraphs)in graphs.However,the mining of cohesive subgraphs should not only ensure high cohesiveness but also consider computational efficiency.In this thesis,two cohesive subgraph metrics,k-truss and kss-core,which can be computed in near-linear and linear time and both ensure good cohesiveness,are used for the analysis.Real-world graphs are constantly evolving and changing,with edges and vertices being added or removed.Therefor,the maintenance of dynamic cohesive subgraphs is also an important challenge.In this thesis,mining cohesive subgraphs is systematically investigated by applying theories,techniques and methods from graph analysis.Aiming at the problems of mining cohesive subgraphs in edge dynamic graphs,full dynamic graphs,dynamic hypergraphs,streaming hypergraphs and designing cohesive subgraph models in hypergraphs,the series of important issues are thoroughly investigated in this thesis.The main contributions are summarized as follows.1.In this thesis,we study the problem of truss maintenance in large-scale dynamic graphs.k-Truss is a widely used cohesive subgraph metric in graph analytics.Maintaining the k-truss,i.e.,updating the k-truss after dynamic changes in graphs,but graphs usually have only a small number of regions where the k-truss is changed,so the key to maintaining k-truss is to reduce redundant computations and avoid recomputing the whole graph.Unlike existing work that focuses on single edge insertion or deletion,this thesis proposes a batch processing algorithm for k-truss maintenance with multiple edges insertion or deletion.The difficulty of quantifying k-truss changes in batch processing is addressed by proposing Triangle Disjoint Set of edges whose insertion or deletion can make k-truss to change by at most 1.This paper further proposes two metrics to help measure the likelihood of k-truss changes,which can then greatly reduce the range of potential k-truss changes in search.Extensive experiments demonstrate that the batch processing algorithm in this thesis can significantly improve the processing efficiency compared with the single-edge processing method,and the improvement is more obvious when the number of dynamic edges is larger.2.In this thesis,we study the k-truss maintenance problem in fully dynamic graphs,which are more complex and contain a large number of dynamic edges and dynamic vertices.Specifically,this thesis considers the challenge of batch processing dynamic edges and vertices and proposes efficient algorithms that search only a small range of affected edges for k-truss.at the same time,the proposed algorithms allow parallel implementation to further improve the efficiency of maintenance.Numerous experiments illustrate the efficiency and scalability of the proposed algorithms.3.In this thesis,we study k-core maintenance in large-scale dynamic hypergraphs.The hyperedges of hypergraphs may contain a set of vertices instead of two vertices in conventional graphs and can represent complex interactions in more complex applications.However,the exponential number of hyperedges can make recalculating the k-core incur unaffordable costs when the hypergraph changes dynamically.In this paper,we propose an efficient and accurate k-core maintenance method that aims to significantly reduce the update time compared to recomputation methods.The proposed algorithms can pinpoint the regions that need to be updated.In this paper,we also propose an auxiliary index structure that can speed up the search process of the maintenance algorithm.Numerous experiments demonstrate the superiority of our algorithm in terms of efficiency.4.In this thesis,we study the problem of batch processing for k-core maintenance in streaming hypergraphs.Unlike existing work,this paper presents the first known batch processing algorithm for maintaining k-core.By proposing the structure called Joint Hyperedge Set,this paper solves the challenge of quantifying k-core changes and searching for possible update ranges.In addition,this thesis further accelerates the update process by finding k-Joint Hyperedge Set structures that can be executed in parallel.The efficiency,scalability,and effectiveness of the k-core maintenance algorithm are experimentally demonstrated,and the parallel algorithm in this thesis achieves linear speedup as the number of threads increases.5.In this thesis,we study the problem of computing cohesive subgraphs based on the engagement of hypergraph vertices.Vertex engagement is of extraordinary significance for social resilience and network stability.However,vertex engagement in hypergraphs reflecting polydiac relationships among entities has never been studied.In this paper,we demonstrate that the engagement of vertices in hypergraphs can be captured by two key parameters,namely,group engagement and neighbor engagement.In addition,we propose a cohesive subgraph model(k,h)-core based on vertex engagement to integrate the advantages of these two measures,thus addressing the ineffectiveness and incompleteness of using only a single engagement factor.In this thesis,an algorithm to complete the decomposition of the(k,h)-core in linear time is proposed.A small-scale local update algorithm is further proposed to maintain the(k,h)-core,which greatly avoids the inefficient way of re-decomposition in dynamic hypergraphs.Extensive experiments demonstrate the generality of the model and the effectiveness of the algorithm in this thesis.