Directed graph compression
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.
1. A method comprising:
reordering, by one or more processing units, a plurality of nodes of a graph to generate a reordered graph, wherein a plurality of non-zero elements in a reordered adjacency matrix are clustered, reducing a number of non-empty blocks, as compared with an adjacency matrix; and
encoding, by the one or more processing units, the reordered adjacency matrix with a plurality of integers, wherein the encoding comprises:
creating, by the one or more processing units, (i) a directory to maintain adjacency matrix identifications, (ii) a first set of integers, and (iii) a second set of integers, wherein:
a first non-empty block includes at least two rows;
the directory includes an associated row identification that identifies row location of the first non-empty block in the adjacency matrix;
the first set of numbers comprises: (i) a first integer that is a left-most column identification of the first non-empty block and (ii) a second integer that is a representation of a first binary number present in the first row of the first non-empty block;
the second set of numbers comprises: (i) a third integer that is a right-most column identification of the first non-empty block and (ii) a fourth integer that is a representation of a second binary number present in the second row of the first non-empty block.
2. The method according to claim 1 , wherein the graph is a directed graph, and each element of a plurality of elements in the adjacency matrix indicates whether a directed edge exists from a first node to a second node of the plurality of nodes.
3. The method according to claim 1 , wherein the encoding comprises:
dividing, by the 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; and
representing, by the 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.
4. The method according to claim 1 , wherein the reordering comprises:
obtaining, by the one or more processing units, node degrees for each node of the plurality of nodes in the graph;
determining, by the one or more processing units, a set of candidate nodes from the plurality of nodes in the graph based on the node degrees; and
determining, by the one or more processing units, an order of the set of candidate nodes and corresponding neighbor nodes based on common neighbor information.
5. The method according to claim 4 , 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.
6. The method according to claim 4 , wherein the determining the set of candidate nodes comprises:
sorting, by the one or more processing units, the plurality of nodes in the graph according to the node degrees, wherein the node with a highest node degree, which includes both in-degree and out-degree, is selected first, based on comparing a highest in-degree and a highest out-degree; and
determining, by the 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 graph.
7. The method according to claim 4 , 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.
8. The method according to claim 4 , wherein the determining the set of candidate nodes comprises:
sorting, by one or more processing units, the plurality of nodes in the graph according to the node degrees, wherein the node with a highest in-degree is selected first; and
determining, by the 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 graph.
9. The method according to claim 4 , wherein the determining the set of candidate nodes comprises:
sorting, by one or more processing units, the plurality of nodes in the graph according to the node degrees, wherein the node with a highest out-degree is selected first; and
determining, by the 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 graph.
10. The method according to claim 1 , wherein the first non-empty block is of a different size than a second non-empty block of the number of non-empty blocks.