How easy is it to estimate a graph by observing only a few random cuts? Is there prior work related to this? I did google but could not find anything concrete.
Any help would be appreciated. Thanks.
$\begingroup$
$\endgroup$
-
6$\begingroup$ What does "estimate a graph" mean? Estimate the number of vertices/edges in a graph? $\endgroup$ – Huck Bennett Apr 27 '12 at 7:55
-
$\begingroup$ @HuckBennett By estimation, i mean recovering the graph with their edge weights. $\endgroup$ – Vedarun May 8 '12 at 5:04
$\begingroup$
$\endgroup$
Its not clear what you want to estimate, or what you mean by looking at a random cut. But it is hard to learn much about a graph by just observing the size of a random cut. This is because a random cut will always cut $m/2$ edges in expectation (where $m$ is the number of edges in the graph), independent of the structure of the graph. Of course, the entire graph can be thought of as a vector of length ${n \choose 2}$, so if you get to observe the -exact- size of that many random cuts, because they are likely to be linearly independent, you can reconstruct the graph. There's nothing special about cuts here: you're just observing the exact value of the dotproduct of $d$ linearly independent vectors with an unknown vector of length $d$, and this system of linear equations will have an exact solution.
-
$\begingroup$ Thanks for the comment. By estimation i meant recovering the edges of the graphs with their weights. I agree if one gets to observe all the cuts, then the graph can be reconstructed. But can one say more if the graph is sparse and one is allowed to query only using a subset of nodes rather than edges? In particular, if one queries using I(S) - the indicator vector for a subset of vertices S, what one gets is I(S)*L*I(S_c) where S_c is the complement of S and L is the Laplacian of the graph. Do the results of compressed sensing apply directly in this case? Thanks in advance $\endgroup$ – Vedarun May 8 '12 at 5:02
