I have a graph and don't know how nodes in it are connected to each other.

  • I know the number of nodes in the graph.
  • I know the degree of each node in the graph.
  • I know that given any node $A$ that any other node $B$ is $n$-connected (where $n$ may vary per $B$) to a sub-graph containing $A$. So if I trim $n$ specific edges edges from $B$, then $B$ won't be connected to the sub-graph containing $A$.

The question I want to know is given this information, if it's possible with high probability to learn the entire graph topology.

  • 3
    $\begingroup$ The word random has a very specific meaning in mathematics, which is different than its usual English meaning. Similarly, topology is a specific mathematical area, though I can imagine it being used for the “structure” of a graph rather than any topological properties. $\endgroup$ Oct 27, 2021 at 20:45
  • $\begingroup$ One keyword sometimes used for learning a graph is graph reconstruction. $\endgroup$ Oct 28, 2021 at 5:43
  • 1
    $\begingroup$ You want to reconstruct the graph "with high probability" — what is the probability over? Everything in your question is deterministic. Perhaps the original graph was chosen according to a specific distribution? $\endgroup$ Oct 31, 2021 at 8:31
  • 1
    $\begingroup$ What do you mean when you say that $B$ is $n$-connected to a subgraph containing $A$? When is a node $n$-connected to a graph? $\endgroup$ Oct 31, 2021 at 8:32
  • $\begingroup$ Maybe that's the wrong terminology. But there are n cuts before B and A are disjoint graphs $\endgroup$ Nov 1, 2021 at 13:35


Your Answer

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

Browse other questions tagged or ask your own question.