Graph triangle counting method based on bit operation

Abstract

The invention belongs to the field of graph analysis, and relates to a graph triangle counting method based on bit operation. A traditional graph triangle counting method often relates to a large number of matrix multiplication operations and complex control logic. The requirements of quick community discovery and the like in a super-large-scale social network graph cannot be met. According to thegraph triangle counting method based on the bit operation, the graph triangle counting problem is converted into a series of simple bit operations such as Boolean AND operation and bit counting, thecalculation type and the control logic are greatly simplified, and therefore the number of triangles in the graph is efficiently and quickly calculated. Meanwhile, the calculation characteristics of the triangle counting method provided by the invention are suitable for being applied to a novel in-memory calculation architecture.

Description

technical field [0001] The invention belongs to the field of graph analysis, and relates to a fast community discovery method in a super-large-scale social network graph, which includes a graph triangle counting method based on bit operation. Background technique [0002] Triangles are the basic substructure of a graph. The triangle counting problem of the number of triangles in a statistical graph is crucial for analyzing the characteristics of a network. It is usually the first step in calculating indicators such as clustering coefficients and transmissibility. When counting triangles as There are a wide range of applications in basic community discovery, link prediction, and spam filtering. [0003] In the era of big data, the scale of graph data such as social network graphs has shown exponential growth, which puts forward higher requirements for quickly identifying the closeness of user connections in social networks. At present, the triangle counting methods for ident...

AI Technical Summary

Problems solved by technology

However, like most graph processing algorithms, triangle counting has a low computational memory access ratio and a high random data access pattern, so there are frequent data transfers between computing units and memory components, especially the multiplication operation in matrix multiplication Very complex and time-consuming, facing bottlenecks in terms of time and power consumption

The speed of the current triangle counting method to count the triangles in the graph cannot meet the needs of fast community discovery in very large-scale social network graphs.

Images