|
|
|
|
|
|
by taeric
1296 days ago
|
|
|
Do you, though? I think I can agree that you are most likely to select an F with your random initial choice. And since the degree of your average L is >> the degree of your average F, it just takes a single L in a highly connected group of Fs to make the general statement true. As such, if you pick an F in a connected group and make a single jump, you are probably not on an L, but another connected F. This would be similar to how famous you are compared to your friends. On average, your friends are more famous than you. But only because you likely have a few much more famous friends. Such that, a random choice of your friends is not likely to be one of these few. (Agreed that it is higher than that initial selection. But would still be low.) Edit: Reading your post, I think I can easily agree that you /increase/ your chances of selecting an L by taking a single hop from a random node. I'm more asking if it is better than 50% at that point. Seems like it shouldn't be. |
|
|
In a simple case, consider a subgraph with one L connected to all F, and every F is connected to 2 Fs (in addition to their connection to L). You have a 1/3 chance of selecting the L in this case (but since there must be at least 3 Fs to draw this graph, you have no better than a 1/4 chance of selecting an L at random and thus you still find more connected nodes on average by using this algorithm).
[edit]
The above example was too simple as the majority of edges do not contain an L, and in fact you don't improve your odds in the 4-node case (they are the same in that case, but at 5 and more nodes you do). It still shows how a small number of highly connected nodes can dominate rather quickly though.