I have a very large graph and a function of its vertices, and want to estimate mean value of this function. It's not possible to sample vertices uniformly in this problem, so a reasonable choice for estimation would be simple random walk. The problem is that for any vertex I can only pick a random neighbour of it; finding the whole neighbourhood of a vertex is extremely hard. So I don't know degrees of sampled vertices, can't find stationary probabilities and can't use standard random walk estimators. Are there still any ways to get unbiased estimate of mean function value?
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ (+1) Nice question. I've seen work on similar problems from a few years ago; I'll try to find it and dig it out of my notes. It would be a very nice addition if you could add some detail to explain how you can randomly sample an outlink of a given vertex without knowing the corresponding outdegree! Such additional detail may help readers provide better guidance. Welcome to the site. Cheers. $\endgroup$– cardinalCommented Feb 3, 2013 at 21:26
-
$\begingroup$ Thank you! Well, I'm studying arrangements of hyperplanes. Each cell of such arrangement corresponds to a vertex in my graph; two vertices are incident iff corresponding cells are adjacent. It's very easy to get one random neighbour of a vertex --- I just pick any point within corresponding cell and send a ray from it in a random direction. This ray intersects some of my hyperplanes; any point between first and second intersections will lie in neighbour cell. But finding all neighbours involves algorithms which are too slow for high dimensions. $\endgroup$– esokolovCommented Feb 4, 2013 at 1:05
-
$\begingroup$ @esokolov: This sounds an awful lot like algebraic geometry, specifically Schubert Calculus. Could you elaborate some more on how these arrangements arise? $\endgroup$– Alex R.Commented Apr 3, 2018 at 22:12
-
$\begingroup$ Otherwise, I'm skeptical this is workable. One thing is if the graph is irreducible (and positive recurrent), then the stationary distribution satisfies $\pi_i=cd_i$, where $d_i$ is the vertex degree, and $c$ depends only on the graph $G$. So this way you can try to estimate $c$, and get away without knowing $d_j$. This gives you $m_i=1/\pi_i$, where $m_i$ is the mean return time to $i$. But you're interested in function values on vertices, so to answer this question better, you need some sort of regularity conditions on $f$, for example $|f(i)-f(j)|<K$, where $i,j$ are neighboring vertices. $\endgroup$– Alex R.Commented Apr 3, 2018 at 22:15
Add a comment
|