Evolutionary Dynamics of Complex Communications Networks

i

i

“K15155” — 2013/9/10 — 9:05

i

i

i

i

i

i

Distinctive Structure and Features of Complex Networks 185

• Complexity: Expander graphs are proven to amplify the success proba-

bility of randomized algorithms.

The interested reader may refer to [89] for a more extensive and detailed

presentation of expander graphs. Since we are studying communications net-

works in this book, we are interested in the second and third applications of

the expander graphs presented before. In general, by proving that a network

graph is an expander, we have proved that it inherently has short paths be-

tween the node pairs without being overcrowded with shortcuts, as in the case

of small-world networks. Also, routing becomes very efficient by avoiding bot-

tlenecks. Finally, since according ...