🚀 go-pugleaf

GRAPH: 5000 nodes, 1.8 M directed edges

Have tried: two greedy algs (one saves: 35%, the other: not done testing)
Want to try: simulated annealing (if someone knows a good algorithm?)
												 fuzzy common subset elimination (meaning nodes that point to
															a common subset do *not* have to be followed by all nodes in
															that subset -- we can store a few zeros to say so)

-----------------------------------------------------------------------------
I'm trying to compress very large directed graphs (0(5000) nodes,
O(2,000,000) directed edges) by finding common "subsets" of the nodes
that often follow other nodes.  The current representation uses adjacency
lists, and is very large.  By finding a common subset, I could store those
node in one place, then have all nodes that are followed by this subset
point to the subset once, rather than redundantly storing each node of the
subset in its adjacency list.  I am also storing probabilities along the
edges, which would be stored as a matrix within each subset.

This task is somewhat complicated by the fact that the subsets do not have
to be *exact* -- ie, I could find a subset that matches "pretty well",
meaning that a good number of nodes point to most of the nodes in the
subset, and then store zeros in the prob matrix for those few elements
of the subset that do not follow certain nodes.

I've considered a few greedy algorithms.  The first finds the size of the
intersection of the follow sets for all pairs of nodes, choosing that pair
of nodes with the maximum intersection and calling that intersection a
"subset".  Then it loops through all other nodes, seeing if the intersection
of their follow sets and this subset is "large enough", and setting up the
pointer if so (storing zeros for those elements in the subset but not in
the adjacency list for that node).  This saves roughly 35% of the space
used by the adjacency lists.

The second greedy algorithm finds that pair of nodes that ocurred the
most together (ie, ocurred together in follow sets of all nodes), and tries
to "grow" a subset by adding on the next most frequently ocurring node, etc.

I believe it should be quite feasible to obtain far better than 35%
compression.  One possibility suggested to me could be  a simulated annealing
approach, which I have not looked into at all.  I imagine this is a problem
that comes up pretty often in the compression world, so I hope there are
some standard approaches.

Any ideas?

mikem