4
$\begingroup$

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:

  • We take a random walk starting at $v_0$.
  • Along the way, we can collect local information such as the degrees of vertices visited. We can also make local modifications to $G$, e.g. by deleting vertices and edges adjacent to where we've been.
  • At the end of the walk (triggered by some event such as having no remaining moves), we use the collected information to compute an unbiased estimator for the number of vertices in $G$.

Specifically, I'm interested in such methods that may be feasible in some cases (all would be too much to ask) where generating $G$ in its entirety is not feasible.

The inspiration for this question is a paper of Donald Knuth that does precisely the above for trees. Applying Knuth's method to a more general graph produces an estimate of the number of possible walks, not the number of vertices.

Ideas?

Improve this question
$\endgroup$
6
  • $\begingroup$ Move from $v_0$ to $v_1$, remove $v_0$ and connect all the vertices which were connected to $v_0$ by edges; move from $v_1$ to $v_2$ and so on as far as you can walk. The number of steps gives you the number of vertices in a connected graph. $\endgroup$
    – Anton Petrunin
    Commented Aug 16, 2013 at 0:21
  • $\begingroup$ @Anton: I guess those are local modifications! But I'm looking for a method that will work when $G$ is too big to do, say, a number of operations as large as the number of vertices of $G$. $\endgroup$
    – tuna
    Commented Aug 16, 2013 at 0:33
  • $\begingroup$ I'd guess that what you're asking is too difficult, unless we have a DAG. One intuition is that, if we cannot remember which vertices we've visited, then it will be difficult to distinguish between a small cycle and a very long line. $\endgroup$
    – usul
    Commented Aug 16, 2013 at 1:39
  • $\begingroup$ @usul: Remember that we can modify the graph locally, for example by deleting vertices we've visited. $\endgroup$
    – tuna
    Commented Aug 16, 2013 at 5:37
  • $\begingroup$ @Tino, ok, but if you are visiting $o(n)$ vertices and making $o(n)$ modifications (where $n$ is the number of vertices), it still seems very unlikely to me. $\endgroup$
    – usul
    Commented Aug 16, 2013 at 16:26

2 Answers 2

Reset to default
1
$\begingroup$

Unless you use some exhaustive criterion for stopping, such as Anton Petrunin's suggestion of deleting vertices while maintaining connectivity and not stopping until all vertices are gone, I do not see what class of graphs you hope will yield to such a process. The example below highlights my pessimism.

Take a graph G you wish to reveal. I will pick a large positive integer k. Pick your v_0. I will construct k copies of G, and pick random pairs of vertices to use to add a single edge between two copies. I will attach my connected construct to your copy at a single vertex, perhaps even at v_0. I do not see how you will determine k, much less the size of either G or my construct, without visiting all the vertices.

I think you will need something like knowing G has a nontrivial automorphism group as well as what that group is, and use that with your locally connected information, to say much about G.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This kind of example is an Achilles' heel for Knuth's method, too. What happens (I think) is that the expected value of his estimator is still the number of vertices, but the second and third moments may be very large, making it infeasible to get a good estimate. That doesn't stop Knuth's method from being useful for trees which are sufficiently "balanced" (in a fuzzier way than having an actual automorphism). That's why I still hold out hope of an extension to graphs that are not trees. $\endgroup$
    – tuna
    Commented Aug 16, 2013 at 20:38
1
$\begingroup$

Giving appropriate meaning to "generating $G$", here is one thing that could give some information: start from $v_0$ and walk until the walk has come back $k$ times to $v_0$; or possibly, instead, walk for a deterministic time $N$ and count how many times the walk visits $v_0$ during this time. This gives you, as $k$ or $N$ goes to infinity, enough information on the distribution of the return times to in particular deduce the size of the graph.

Admittedly the time needed for the algorithm will be quite a bit larger than the number of vertices. But OTOH, maybe $G$ is given implicitly as the set of states of some process, with edges given by transitions of that process, in such a way that storing the current state is (very) cheap and running the walk is easy. So, it can work with $o(n)$ memory requirement if not $o(n)$ time...

Here is a nice paper going into exactly what kind of info can on $G$ be reconstructed that way: Waiting for a bat to fly by (in polynomial time).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .