search

graspologic-org / graspologic

Python package for graph statistics
https://graspologic-org.github.io/graspologic/
MIT License
822 stars 144 forks source link

Graph utility: "At Most N Edges" #456

Open daxpryce opened 4 years ago

daxpryce commented 4 years ago

Post graspy + topologic merger, we have a request to make it easy to turn a large graph into a smaller graph based on edge cuts. The idea is that a user may have a graph with 10 million edges and want to work with at most 1m edges, so we should be able to do that automatically on their behalf

bdpedigo commented 4 years ago

based on edge cuts

like just by weight, or by any other properties of the network? reason I ask is I saw some math voodoo paper about "sparsifying" networks (adjacency matrices) and keeping the spectral structure as similar as possible

daxpryce commented 4 years ago

I know for sure we want to do weight, but I guarantee that @bryantower is going to be interested in hearing more about the other options

bryantower commented 4 years ago

The specific feature that I would like to see is the one that Dwayne mentioned. I want at most X total edges, please cut the minimum number of edges to make that happen, by removing the lowest weight edges first.

alyakin314 commented 4 years ago

well, an obvious way is : turn_to_edgelist -> sort -> head(X), which is O(V^2 + E log(E)) i think (V^2 comes from converting to edgelist if you are given adjacency matrix, so it's there, but it is fast), but we might be able to do better than that..