Edit: It would clearly require some pretty complex network interactions. You can't be able to precompute a proof and send it to another place.
I'm thinking something like every node broadcasting a public key, which every other node then uses to sign an identifier and sends back. From this, you can generate local maps of the network. While nodes could collude to seem close to each other or lie and claim other nodes are far away, there's presumably some density of truth at which you can construct a reliable global map.