Search

CN-122019874-A - Method and device for constructing and maintaining parallel triangle connected k-truss community index

CN122019874ACN 122019874 ACN122019874 ACN 122019874ACN-122019874-A

Abstract

The invention provides a method and a device for constructing and maintaining a parallel triangle connected k-truss community index, wherein the method comprises the steps of reading an original image of a relation between target entities from a text file, determining truss values of each edge of the original image and all triangles through a truss decomposition algorithm to obtain three graph edge tensors, dividing the triangles in the original image into inner triangles and marginal triangles based on truss values of the three graph edge tensors, constructing EquiTruss indexes, determining the range of affected edges when nodes are edited to obtain an edge set of the edges with affected truss values, updating truss values of the affected superedges based on the truss decomposition algorithm, and updating the EquiTruss indexes. The invention can fully utilize the parallel computing capability of the novel hardware and solve the problem of poor efficiency of index construction and maintenance in the prior related technology.

Inventors

  • ZHU YUANYUAN
  • MA JUNCHAO
  • YAN XIN

Assignees

  • 武汉大学

Dates

Publication Date
20260512
Application Date
20260121

Claims (10)

  1. 1. A method for constructing and maintaining a parallel triangle connected k-truss community index, comprising: reading an original image of the relation between target entities from a text file, and determining truss values of each edge of the original image and all triangles through truss decomposition algorithm to obtain three graph edge tensors; dividing the triangle inside the original image into an inside triangle and a marginal triangle based on truss values of the three drawing edge tensors, and constructing EquiTruss index; determining the range of the affected edge when the node is edited, and obtaining an edge set of the edge with the truss value affected; based on truss decomposition algorithm, the truss value of the affected superside is updated and the EquiTruss index is updated.
  2. 2. The method for constructing and maintaining a parallel triangle connected k-truss community index according to claim 1, wherein reading an original graph of a relationship between target entities from a text file, and determining truss values and all triangles of each side of the original graph by a truss decomposition algorithm to obtain three graph-side tensors, including: Reading original pictures from the text file by adopting a storage format of compressed sparse lines, wherein the storage format of the compressed sparse lines consists of line pointers and adjacent arrays; and calculating truss values of each edge in the original image, and simultaneously calculating all triangles in the original image to obtain three graph edge tensors, wherein three elements at the same position of the three graph edge tensors form one triangle in the original image.
  3. 3. The method of parallel triangle connected k-truss community index construction and maintenance of claim 1, wherein dividing the triangle inside the artwork into an inside triangle and a marginal triangle based on truss values of three of the graph edge tensors, comprises: taking triangles with equal values of three sides truss in the original image as internal triangles; And taking the triangle with the truss values of the three sides not completely equal in the original drawing as a marginal triangle.
  4. 4. The method of parallel triangle connected k-truss community index construction and maintenance of claim 3, wherein constructing EquiTruss index comprises: for the internal triangle, three edges are added to the same supernode; and sequencing the marginal triangles according to truss values of the three edges, and respectively adding superedges of supernodes to which the three edges belong based on sequencing results.
  5. 5. The method for constructing and maintaining the parallel triangle connected k-truss community index according to claim 1, wherein after constructing EquiTruss index, if further constructing EquiTree index is needed, performing chain reconstruction on EquiTruss index to obtain EquiTree index.
  6. 6. The method of parallel triangle connected k-truss community index construction and maintenance of claim 1, wherein determining the scope of the affected edge, obtaining the edge set of the affected edge with truss value, comprises: For any one edge inserted into the original image, setting an upper bound of a truss value after the edge is inserted, and if the truss value of the edge existing in the original image is smaller than the upper bound and is communicated with the k-triangle between the inserted edges, the truss value of the edge can be influenced; For any one deleted edge from the original image, if the truss value of the existing edge in the original image does not exceed the truss value of the deleted edge and is communicated with the deleted edge k-triangle, the changed truss value may be affected; and merging and summarizing edges which are possibly affected to obtain an edge set of the edges with the truss values affected.
  7. 7. The method of parallel triangle connected k-truss community index construction and maintenance of claim 5, wherein updating the truss value of the affected superside comprises: Determining a node set corresponding to an edge set of an edge with an affected value truss, and extracting an induced subgraph of the node set from the original image; and carrying out truss decomposition on the induced subgraph, and updating truss values of the affected supersides.
  8. 8. The method of parallel triangle connected k-truss community index construction and maintenance of claim 7, wherein updating the EquiTruss index comprises: searching and deleting supernodes containing affected supersides in the original EquiTruss index; constructing an index for the induced sub-graph, and creating a superside between the inside and the outside of the induced sub-graph; And merging the supernodes with the truss equal values and the supersides, and finishing the updating of the EquiTruss index.
  9. 9. The method of parallel triangle connected k-truss community index construction and maintenance of claim 7, wherein if the EquiTree index is to be updated: splitting the affected supernode into a plurality of equivalence classes, and determining the affected equivalence classes; searching and deleting supernodes containing affected supersides in the original EquiTree index; constructing an index for the induced sub-graph, and creating a superside between the inside and the outside of the induced sub-graph; merging the super nodes with truss equal values and super edges between the super nodes to finish the updating of EquiTree indexes; And carrying out chain reconstruction on the updated EquiTree indexes, and maintaining the tree structure of the EquiTree.
  10. 10. A device for constructing and maintaining a parallel triangle connected k-truss community index, comprising: The reading module is used for reading the original image from the text file, determining truss values of each edge of the original image and all triangles through truss decomposition algorithm, and obtaining three image edge tensors; A construction module, configured to divide the triangle inside the original image into an inside triangle and a marginal triangle based on truss values of the three graph-side tensors, and construct EquiTruss index; The processing module is used for determining the range of the affected edge when the node is edited, and obtaining an edge set of the edge with the affected truss value; and the updating module is used for updating truss values of affected supersides based on truss decomposition algorithm and updating the EquiTruss index.

Description

Method and device for constructing and maintaining parallel triangle connected k-truss community index Technical Field The invention relates to the technical field of data analysis, in particular to a method and a device for constructing and maintaining a parallel triangle connected k-truss community index. Background In the real world, graphs are used to model relationships between entities, within which there are typically closely related sub-graphs, i.e., community structures. The existing researches related to community structures are mainly divided into community detection and community search, wherein the community detection aims at searching all communities in the graph and has been widely studied in the past decades, and the community search is oriented to a query point given by a user and can online return to the communities containing the query point, so that the interests of a plurality of researchers are attracted in recent years. To meet the diverse needs of real-world applications, many community models have been proposed, including k-clique, k-trus, k-core, etc., however, most of these community models are either less cohesive (k-core) or make the community search problem NP-hard (k-clique). k-truss is a trade-off between cohesiveness and time complexity, ensures higher cohesiveness and can be solved in polynomial time, so that the method is widely applied to many researches. On this, part of the work has imposed a constraint on the triangular connectivity on the k-truss community model, focusing on finding the k-truss communities from the graph that connect more tightly triangular connectivity. The existing work often firstly constructs an index (such as EquiTruss, equiTree) for storing all the edge truss values and triangle connection relation information in the original image offline, stores the index in a memory, and then efficiently searches the k-truss community containing triangle connection of a specific query node through the index, so that the method can be efficiently executed on a CPU in series. Above this, part of the work utilizes the parallel computing capabilities of the multi-core CPU to implement the parallel build EquiTruss index. However, the above index building method will be directed to from 3 toIteratively checking the triangle connectivity of each edge, directly converting it to a parallel algorithm does not make good use of the computational power of the new hardware, because the fragmented iterative computation requires frequent start-up kernels to check the corresponding triangle connectivity information, which introduces very expensive kernel start-up overhead. At the same time, graphs in the real world are constantly changing, and updating the index accordingly is critical to online community searching. Existing methods can update inserted/deleted edges in batches, but still lack the computational power of parallel algorithms to utilize new hardware. For the problem of poor efficiency of index construction and maintenance in the prior related art, no effective solution has been proposed at present. Disclosure of Invention The invention provides a method and a device for constructing and maintaining a parallel triangle connected k-truss community index, which are used for solving the defect of poor efficiency of constructing and maintaining the index in the prior related technology. In a first aspect, the present invention provides a method for constructing and maintaining a parallel triangle connected k-truss community index, including: reading an original image of the relation between target entities from a text file, and determining truss values of each edge of the original image and all triangles through truss decomposition algorithm to obtain three graph edge tensors; dividing the triangle inside the original image into an inside triangle and a marginal triangle based on truss values of the three drawing edge tensors, and constructing EquiTruss index; determining the range of the affected edge when the node is edited, and obtaining an edge set of the edge with the truss value affected; based on truss decomposition algorithm, the truss value of the affected superside is updated and the EquiTruss index is updated. According to the method for constructing and maintaining the parallel triangle connected k-truss community index, provided by the invention, an original image of the relation between target entities is read from a text file, truss values of each edge of the original image and all triangles are determined through a truss decomposition algorithm, and three graph edge tensors are obtained, wherein the method comprises the following steps: Reading original pictures from the text file by adopting a storage format of compressed sparse lines, wherein the storage format of the compressed sparse lines consists of line pointers and adjacent arrays; and calculating truss values of each edge in the original image, and simultaneously calculating all triangles in t