You may be able to leverage axioms about small world networks to optimize this type of traversal.
Small world networks are characterized by “hubs” the represent very dense interconnections of other nodes. Most nodes in the network will generally either connect within a few hops to a topologically nearby node (1-4 hops away) or will route through one or more such hubs. This is one of the main reasons that small world networks behave the way they do.