Let G be a connected graph, and let S be a specified, randomly selected, subset of the nodes of the graph (say 5%). Let a and b be two randomly selected nodes from the graph. What is the probability that the shortest path between a and b passes thought at least one node from S?
I know the answer to this question is surely contingent on a number of factors I’m not including in this description. Anyone interested in aiding me in answering this question can just states the hypothesis he needs (small world etc.).