Directed graph compression

1. A system, comprising:

one or more processors;

a memory coupled to at least one of the processors; a set of computer program instructions stored in the memory and executed by at least one of the processors in order to perform actions of:

reordering 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 the reordered adjacency matrix with a plurality of integers, wherein the encoding comprises:

creating (j) 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; and

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 system 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 or not a directed edge exists from a first node to a second node of the plurality of nodes.

3. The system according to claim 1 , wherein the encoding comprises:

dividing 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 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 system according to claim 1 , wherein the reordering comprises:

obtaining node degrees for each node of the plurality of nodes in the graph;

determining a set of candidate nodes from the plurality of nodes in the graph based on the node degrees; and

determining an order of the set of candidate nodes and corresponding neighbor nodes based on common neighbor information.

5. The system 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 system according to claim 5 , wherein the determining the set of candidate nodes comprises:

sorting 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 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 system according to claim 1 , wherein the determining the set of candidate nodes comprises:

sorting 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 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.

8. A computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions readable by a device to cause the device to perform a method comprising:

reordering 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 the reordered adjacency matrix with a plurality of integers, wherein the encoding comprises:

creating (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; and

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.

9. The computer program product according to claim 8 , wherein the graph is a directed graph, and each element of a plurality of elements in the adjacency matrix indicates whether or not a directed edge exists from a first node to a second node of the plurality of nodes.

10. The computer program product according to claim 8 , wherein the encoding comprises:

dividing 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 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.

11. The computer program product according to claim 8 , wherein the reordering comprises:

obtaining node degrees for each node of the plurality of nodes in the graph;

determining a set of candidate nodes from the plurality of nodes in the graph based on the node degrees; and

determining an order of the set of candidate nodes and corresponding neighbor nodes based on common neighbor information.

12. The computer program product according to claim 11 , 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.

13. The computer program product according to claim 11 , wherein the determining the set of candidate nodes comprises:

sorting 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 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.

14. The computer program product according to claim 11 , 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.

15. The system according to claim 8 , wherein the determining the set of candidate nodes comprises:

sorting 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 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.