Index for Counting the Shortest Cycle Based on Strongly Connected Components

The shortest cycle counting is a basic pattern of graph analysis.The shortest cycle counting through a certain vertex refers to the number of shortest cycles passing through the vertex.In real life,the shortest cycle counting has a wide range of applications,such as fraudulent transaction detection,criminal pre-screening,and file sharing optimization.In response to the problems of large indexing space and low query efficiency of existing methods,this paper studies the construction of shortest cycle counting indexing on the original graph,and proposes a trough shortest cycle counting index(STC index) that does not require graph transformation operations.The index classifies the shortest cycles according to their characteristics,constructs different indexing information for different types of shortest cycles,and can directly construct indexes based on the original graph,and further improve query efficiency while ensuring that the indexing size does not expand and the indexing construction time does not increase.In addition,based on the special relationship between cycles and strongly connected components,this paper proposes an indexing strategy based on strongly connected components.By constructing shortest cycle counting indexing within strongly connected components,it can further improve the efficiency of indexing construction,effectively reduce the index size,and improve query efficiency.Experiments on 10 real datasetsverify the efficiency of the proposed STC index and the strategy based on strongly connected components,which can effectively reduce the indexing space and improve the efficiency of indexing construction and querying.