Robustness and decentralized search in complex networks

Abstract

Studies on complex networks have been motivated by the desire to better understand various real-life systems. Such systems, including Internet, world-wide web (WWW), airline transportation systems, food web, protein-protein reactions, co-authorship, and terrorist activities etc., when formulated into network models, display some nontrivial common features. For example, they all have heavy-tailed nodal-degree distributions, or in other words, all can be formulated into scale-free networks. Extensive research efforts have been made to study the robustness of complex networks especially scale-free networks. One of the most important results is that while scale-free networks are strongly tolerant against random failures, they are fragile under intentional attack which crashes network nodes in a decreasing order of their nodal degrees.