say you've got a huge graph with millions of edges and nodes and want to transform it into a smaller graph losing some edges and also some nodes, it could be still big but more manageable in size compared to the first one; nevertheless the new graph shouldn't be a new graph altogether but just a deformed version of the original one, meanwhile it must be preserving some features, for instance you want them both to have a similar page-rank vectors(remaining nodes have the same precedence as before using page-rank), or the new graph has a very similar degree distribution pattern to the old one; so i was to ask, does anybody know of any operations or methods that would help? any suggestions are very much appreciated.
Graph sampling is indeed useful, see the link for an example
http://www.vldb.org/pvldb/2/vldb09-713.pdf
Graph sampling is indeed useful, see the link for an example
http://www.vldb.org/pvldb/2/vldb09-713.pdf
What if you simply select a threshold and binarize the adjacency matrix? Afterwards, you can apply measures based on graph theory to characterize the matrixes. See Rubinov and Sporns 2010.
Cool paper! The idea of a threshold depends on a weighted edges though. The paper mentions the use of centrality measures, which can be a decent heuristic once you know the threshold of eliminating the vertices but not the edges. Very good discussion you all, thanks!
.
"structural reservoir sampling" for streaming graphs may be of interest to you ; see for instance
http://ecmlpkdd2014.loria.fr/wp-content/uploads/2014/09/Aggarwal-Network-Analysis-in-the-Big-Data-Age.pdf
.
A graph arising from practice might have many nodes adjacent to 0, 1 or 2 nodes. Isolated nodes may be counted and removed without loss of information, suspended nodes may be (depending on the goal of course) also removed from the graph (and stored separately if needed), and if the node has two incident edges, it may be (also depending of the goal) removed, merging these two edges. In _some_ sense, most of the important structural information would be preserved. This, however, would not help you much with "facebook friends"-like graphs.
I guess you are generally interested in approaches to reduce the graph size to something more manageable, while at the same time preserving the key properties of the graph. If it is so, though I am afraid I am not acquainted with the details of this, interesting examples might be: Sketching, Sparsification, and Streaming:
http://shonan.nii.ac.jp/shonan/blog/2013/03/01/algorithms-for-large-scale-graphs/
Everything hinges on what you consider to be "important" (or key) properties of the network you want to preserve. Simply conditioning on the degree distribution may or may not preserve other things, like the relative sizes of 2-cores, 3-cores... (how tree-like / or cyclic the network is, as a proportion of its total size). Numbers/kinds of cyclic structures... these things can be more difficult to approximate.
What I'd probably do, is do an iterative degree-reduction (n-core) analysis on it, to peel back the layers of the onion, as it were. Then try randomly sampling dyads from the larger network, but conditioning the dyad's probability of being selected on the "n" (of the n-core) values.
The hope would be that the sampled network would reduce similarly to the big one. (would peel off roughly similarly-sized layers, as a proportion of N, the number of nodes in the graph). I'm really shooting from the hip here, but it seems to me that some kind of modified degree-reduction procedure would yield smaller graphs, but with some similarities (like relative k-plex or n-clique rankings). Not sure how well a "page-rank" would survive such a procedure. But certain qualities of the graph would probably be similar (or could be made to be similar).
A lot really depends on the topology of the big network... What proportion of it is trees & what proportion of it is cycles // how nested the cycles are... what does the component structure look like? (are we caring about this whole problem in a "directed" or "undirected" network sense?) Does the resulting sample have to be a single connected component because the big one is (and because many graph metrics make sense only for connected components)? That kind of thing.
Have a look to my paper Extracting Winning Strategies in Update Games. We use a technique called Contractor Operator that reduces the size of a graph but preserving its properties. If you want to get your original graph, use another technique called Unfolding Operator to reverse the changes in the graph.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs