Directed graph compression

Abstract

In one embodiment of the present disclosure, an original graph including nodes is obtained. The nodes of the original graph are reordered to generate a reordered graph. Non-zero elements in an adjacency matrix for the reordered graph are clustered as compared with an adjacency matrix for the original graph. The adjacency matrix for the reordered graph is encoded with integers. The integers correspond to non-empty blocks in the adjacency matrix for the reordered graph.

What is claimed is: 
     
         1 . A method for processing a graph, comprising:
 obtaining, by one or more processing units, an original graph including a plurality of nodes, wherein the original graph is a directed graph, and each element of a plurality of elements in an adjacency matrix indicates whether or not a directed edge exists from a first node to a second node of the plurality of nodes, and wherein a node identification is assigned to each node of the plurality of nodes;   reordering, by one or more processing units, the plurality of nodes of the original graph to generate a reordered graph, wherein a plurality of non-zero elements in a reordered adjacency matrix are clustered, minimizing a number of non-empty blocks, as compared with the adjacency matrix, wherein a plurality of values associated with each of the plurality of non-zero elements represents weights of an edge and the weights are stored to a weight matrix, and wherein the reordering comprises:
 obtaining, by one or more processing units, node degrees for each node of the plurality of nodes in the original graph, wherein the node degrees include an in-degree and an out-degree, wherein the in-degree indicates a degree to which a node is pointed to by the plurality of nodes and the out-degree indicates a degree to which the node points to the plurality of nodes; 
 determining, by one or more processing units, a set of candidate nodes from the plurality of nodes in the original graph based on the node degrees, wherein the determining the set of candidate nodes comprises:
 sorting, by one or more processing units, the plurality of nodes in the original graph in descending order according to the node degrees; and 
 determining, by one or more processing units, k number of nodes as the set of candidate nodes, wherein k is an integer less than or equal to a total number of nodes in the original graph; and 
 
 determining, by one or more processing units, an order of the set of candidate nodes and corresponding neighbor nodes based on common neighbor information, wherein the common neighbor information is a number of neighbor nodes shared in common between two nodes of the set of candidate nodes, and wherein the order of the set of candidate nodes is a descending order according to the number of neighbor nodes shared in common for each candidate node; and 
   encoding, by one or more processing units, the reordered adjacency matrix with a plurality of integers, wherein each integer of the plurality of integers corresponds to a non-empty block within the number of non-empty blocks in the reordered adjacency matrix, wherein the encoding comprises:
 dividing, by one or more processing units, the reordered adjacency matrix into a plurality of blocks, wherein each block includes at least one element of a plurality of elements in the reordered adjacency matrix; 
 representing, by one or more processing units, each non-empty block of the plurality of blocks as at least one integer of the plurality of integers, wherein elements in each non-empty block are treated as a binary form of the at least one integer; and 
 creating, by one or more processing units, a directory to maintain adjacency matrix identifications, wherein the directory includes an associated row identification where the non-empty blocks are located in the adjacency matrix, and wherein the directory includes a set of numbers, wherein a first number in the set of numbers is a left-most column identification of a first row of the non-empty block and a second number in the set of numbers is the representation of the entire non-empty block as at least one integer of the plurality of integers, wherein elements in the entire non-empty block are treated as a binary form of the at least one integer.