A problem about the compression of directed graphs
Right now I encountered a problem in my research that is about graph compressing (or contraction, etc.). I've searched in various ways for existing techniques on this problem and found nothing. I've been trying to figure out this problem by myself. However I would also like to seek some advice from you guys.
>The description of this problem:
>
>Given a directed graph G = (V, E) where V is the set of vertices and E
>is the set of directed edges. These vertices and directed edges
>represent the events and the directional relationships between pairs of
>events. Each edge is associated with a weight (or confidence score)
>which indicates the degree of the relationship. Now I want to compress
>the graph by merging some of the vertices into one superior vertex,
>which implies that several lower-level events are merged into one
>high-level event (this is mainly because the extent of news events
>defined are usually flexible). After that we can reorganize the
>vertices and edges and repeat this process until the size of the graph
>reaches a certain limit. Purely looking from the point of graph theory,
>is there any existing graph algorithm that solves this problem? As far as I have searched, the answer seems to be negative.
This seems to be an interesting novel problem which falls in the area of graph algorithms. Could you suggest anything? Attached is a sample directed graph of such a kind which may be interesting.
Check this URL to find out more about this kind of DAG:
http://ihome.cuhk.edu.hk/~s042162/2005-05-24.jpg
Thank you very much for your time and help.
Regards,
Daniel
Although it is not directly related to your problem you might want to look at the
stoer wagner min-cut algorithm. It finds the minimum capacity cut of undirected weighted graphs.
I bring it up because of the technique used to find the cut. The algorithm merges adjacent
vertices (and thier associated weights). This is done recursively until only two vertices exist at
which point you have the minimum capacity cut. The technique they use to perform the merge
may be adaptable to your situation.
matfud
Sounds like an interesting problem. The temporal aspect presents an interesting wrinkle. Graph models have been becoming popular for the standard clustering problem recently, but they are typically undirected formulations. The idea of compressing a graph reminded me of work done by G. Karypis and V. Kumar on graph partitioning, some of their papers are available here:
http://www-users.cs.umn.edu/~karypis/publications/partitioning.html
SImilar to the reference given by matfud, with the additional restriction that there may be a size restriction on the size of the partitions or there may be multiple partitions (both restrictions make the problem NP-complete, IIRC).
There's also the area of spectral graph partitioning which may be of interest. Its a way of finding relatively dense areas in a graph by using the eigenvalues of the adjacency matrix. Most of the results in this area are dependent on the fact that adjacency matrices for graphs are symmetric and semi-definite, which wouldn't be the case for a directed graph, but could be worth some experimentation if you have MATLAB or something similar.
There's something else this problem reminds me of, but I can't think of it right now. Maybe later something will come to me.
Good luck.
