metric invariant random graph pruning?

Mar 1, 2009 at 4:24 AM
I'm hoping someone could give me the bottom line on what I presume is a large and technical literature...

I have more than a dozen large graphs. (Large means my machine takes tens of seconds, at best, to do simple chart manipulations in NodeXL.) In order to get a sense of how the graphs change from year to year, I'd like to look at representative subsets.  Once I have some intuition, I can then calculate with the full graphs.

The obvious step is to randomly prune the graph in a way that leave the metrics unaffected. What's the best way to do that?  My intuition is that one should prune edges rather than nodes, but beyond that...

A better-formed question may be: given specific metrics that I would like to leave invariant, what is the most appropriate pruning strategy?  I suspect that different prunings affect metrics differently...

thanks in advance
Pierre