2
$\begingroup$

I have a set of nodes in 3d physical space. Some of those nodes are connected to one another by a graph edge, while others are not. Just because two nodes are physically close doesn't necessarily mean they're connected. (For example, Node A and Node B might be physically next to each other, but there's no graph edge permitting travel between them.) I know about the existence of all of the nodes in advance, but I don't necessarily know their exact physical locations. I don't know any of the edges in advance.

An observer moves around in this graph using an instrument to determine which node they're currently located at. The instrument is reasonably accurate, but will sometimes confuse a node for a different node close by. For example, usually when the observer is at Node A, the instrument will read "Node A." Sometimes, it will read "Node B." The instrument is capable of giving a confidence score.

If the observer moves around this graph for an extended period of time and I have continuous readings from the instrument, can I learn the graph? (Assume readings are close enough together such that there's no "gaps" in time where the observer moved more than 1 node.) Essentially, I'd need to separate transitions (Node A -> Node B) that occur because of real edges in the graph from transitions from spurious transitions that occur because the instrument gave a false reading.

I've done quite a bit of Googling, but I can't seem to find much about this specific problem. Most of the "edge prediction" literature seems to be about predicting new graph edges when a bunch of graph edges are already known (e.g., in social networks). But, this is not relevant to my problem.

Is there a body of literature I should be looking at? A search term might even suffice as an answer to my question.

This also relates significantly to a hidden Markov model, but I don't know any of the transition or emission probabilities in advance and essentially want to learn transition probabilities...

$\endgroup$
2
$\begingroup$

One solution is to use sample size estimators and your edge detection confidence scores to map the most “confident” edges.

For instance if you frequently observe unique traversal between Node A and Node B and with high confidence, this is likely an edge. However if you observe relatively few traversal between node B to C, and with low confidence, this is unlikely an edge. As you pointed out you might want to use a higher acceptance criteria for nodes that are physically close to one another to avoid erroneous edges being created due to signal error.

Are these GPS coordinates or similar data within a dynamic network? If so the above approach can be applied for varying levels of spatial resolution e.g coarse resolution to detect major routes and high way, moderate for regional roads, high for local roads, etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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