4
$\begingroup$

I'm working on a problem about $N$ nodes that are randomly positioned on a rectangular grid. I want to take a sample of $n\leq N$ nodes by randomly selecting the first node then visiting the nearest neighbour of the last selected node. Once a node is visited, it is excluded from future selctions. If a node has there multiple nearest neighbours, one is randomly picked among them.

I'm interested in the probability that a node is visited (I'm also interested in the probability that a pair of nodes appear in the same sample). I'm using the following population as an example: $$\{(-4,6),(0,5),(-3,4),(-2,4),(2,4),(3,4),(1,3),(5,3),(3,2),(2,1),(-1,0),(-3,1),(1,-1),(-4,-2),(-3,-2),(-1,-2),(3,-2),(4,-2),(2,-3),(4,-3),(2,-4),(4,-4),(5,-4),(-5,-5),(2,-5)\}$$

enter image description here (Note: The numbers above the points are just identifying labels. They do not indicate anything about the order in which they are visited. A sample of three points would be something like $6 \rightarrow 5 \rightarrow 7$)

Here are my two approaches:

  1. Enumerate all the possible paths of a specified length, calculate the probability of each path, then sum up the probabilities of the paths that include a particular node.

  2. Repeatedly take samples then calculate the proportion of paths that include a particular node.

Is there a better way to solve my problem? By the way, I'm using R to do the computing.

I don't have any background in graph theory whatsoever. I'd like to look up terms and concepts that would be relevant to what I'm doing, but I'm not even sure where to begin. Do you have any ideas for a solution or do you know of any resources that can be understood by a novice?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ How many nodes are there that have multiple neighbors at the same distance? Note that if there aren't any such nodes, then the path is entirely determined by the choice of starting node, so there are only $N$ possible paths, and all paths can be easily enumerated. If we let $k$ be the number of nodes that have multiple neighbors at the same distance, and if $k$ is sufficiently small, the number of possible paths might not be too bad (and there might be even more efficient algorithms). Do you have any reason to expect $k$ to be especially small? $\endgroup$
    – D.W.
    Commented May 18, 2015 at 22:36
  • $\begingroup$ Yes, that's a good point. The example above has 25 nodes (I edited the post to give the coordinates). If I take a sample of 3 nodes, there are 41 possible paths and if I take a sample of 24 nodes, there are 1036 paths, so it isn't too bad to compute. Later though, I'll be analyzing several populations, each with 80-200 nodes, where I will sample 10-180 nodes per population. I haven't yet decided how many nodes will have multiple neighbours, but it would probably be a sizeable portion. $\endgroup$
    – Maria Reyes
    Commented May 19, 2015 at 1:02
  • 2
    $\begingroup$ It is not clear to me from what distribution the $N$ points are picked? Are they uniformly random points in a square? Are they uniformly random points from an $m\times m$ grid, and if so how big is $m$ with respect to $N$? Depending on your answer, it may be the case that with very high probability each point has a unique nearest neighbor, and, as DW noted, that means you'd only need to consider N paths. Also, how did you arrive at 41 length 3 paths for your example input? $\endgroup$
    – Sasho Nikolov
    Commented May 19, 2015 at 3:30
  • $\begingroup$ That's right, the points will be uniformly distributed on an $m \times m$ grid. I haven't thought about how big my grid will be. I'm glad you brought up this point. I'm guessing that for a fixed value of N, if I increase the grid size then the probability that each point has a unique neighbour will be higher. Is this correct? $\endgroup$
    – Maria Reyes
    Commented May 20, 2015 at 2:54
  • 2
    $\begingroup$ Yes, surely bigger values of $m$ give you a higher probability that each point has a unique nearest neighbor, and in the limit the probability is 1 if you have a continuous distribution on the square. For your case, a heuristic calculation suggests that for $m$ slightly bigger than $N$, say about $N\log N$, with high probability all points have unique nearest neighbors. $\endgroup$
    – Sasho Nikolov
    Commented May 21, 2015 at 18:37

1 Answer 1

Reset to default
1
$\begingroup$

You can make a state machine from this as follows.

Let the set of points generated be $V$.

Add extra dummy start node $s$. Add edges $(s, v)$ for all $v \in V$. And add edge from $(u, v)$ where $u, v \in V$ are nearest neighbors.

Assuming points to visit are chosen uniformly assign probability $1/|V|$ to edges $(s,v)$ and probability of $1/\text{number of nearest neighbors}$ to edges that connect nearest neighbors.

This now forms a state diagram like http://en.wikipedia.org/wiki/Markov_chain#Example

The graph can be represented as matrix $G$ where $G_{ij} =1$ if there is edge between $i$ and $j$. And probabilities can be put in a matrix $P$ of size $N + 1 \times N + 1$.

$G^k_{ij}$ gives number of paths of length $k$ from $i$ to $j$.

$(P^k x)_j$ gives probability of reaching $j$ from $i$ in $k$ steps where $x$ is a vector where only $i^{th}$ entry is 1 and others are 0.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the idea. I wonder if there's a way to account for the following situation using a state machine. As I understand, the matrix G is constant at each step, but in my example, the nearest neighbour of a point depends on all previously selected points. If we start at point 4, its nearest neighbour is point 3. But if point 3 was selected before point 4, then point 2 is now the nearest neighbour of point 4. $\endgroup$
    – Maria Reyes
    Commented May 20, 2015 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.