[aidenn0]

Yes, if the plurality of nodes are F<->F and F >> L then the odds are less than 50%.

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.

[taeric]

Cool, that matches my current intuition for this. I'm curious on what the numbers say in realistic social networks. My gut call was that the distinction between "most of your friends have more friends than you do" and "your friends have more friends, on average," is one that is confusing to most people. Myself included.