Truss Decomposition On Multilayer Graphs

Dense subgraph decomposition is an important problem in the management and analysis of large-scale graph data,and can be applied to various real-world scenarios.In community detection,a community is a subgraph composed of densely connected nodes.In node participation analysis,nodes in dense subgraphs are considered to have higher participation and influence.In the field of graph data visualization,the visualization of dense subgraphs can reveal the reasons behind some phenomena.As a means of analysis,when the scale of graph data reaches a certain level,the time or space cost of analyzing the graph data as a whole becomes unacceptable,and decomposing the graph data can reveal hidden information in the graph data structure.Dense subgraph computation is an important direction in the decomposition of large-scale graph data.Existing research has proposed different definitions of dense subgraph models,among which the representative ones are k-core,n-clique,and ktruss.The k-truss model can decompose the graph into different levels of density from dense to sparse based on the triangle relationships between nodes in the graph data,which has stronger robustness and scalability compared to other dense subgraph models,and the density constraint of k-truss is also more in line with realistic application scenarios.Due to the excellent properties of the k-truss model,it has attracted the attention of many researchers in the field of graph data,and although the k-truss decomposition problem in single-layer graphs has been widely studied,research on k-truss decomposition for multi-layer graphs is still in its infancy.In fact,multilayer graphs,as a graph data structure that can represent multiple relationships between entities,are widely used in different fields,such as social networks,where multiple interactions between different users can be represented in a multi-layer graph;timestamped transaction networks can form hierarchical graph data relationships;and in biological networks,different interactions between genes can also be modeled as multi-layer graphs.Therefore,the k-truss decomposition problem in multi-layer graphs has its potential research value.General multi-layer graph models have the same set of nodes for each layer but different sets of edges,making it impossible to define edge properties for the entire multi-layer graph.General multi-layer graph models have the same set of nodes for each layer but different sets of edges,making it impossible to define edge properties for the entire multi-layer graph.To fill this research gap,this paper proposes an efficient algorithm for dense k-truss subgraph decomposition and storage with density constraint for multi-layer graphs,the algorithm first calculates the k-truss of each single-layer graph,and when the number of layers is greater than or equal to 2,the algorithm converts edge properties into node properties using existing calculation results,initializes the global truss value of the vertex and decomposes the graph layer by layer until the vertex truss value is no longer updated.In addition,this paper proposes an algorithm for computing diverse dense Ktruss subgraphs.The algorithm was run on 5 real-world scenario datasets,and the experimental results show that the algorithm can compute effective results in up to 10-layer graph data with as many as millions of nodes.In the case study of visualization,this paper demonstrates the application value of multi-layer k-truss.