Learning Modules > Error and Attack Tolerance of Networks
Description | Usage Hints | Learning Task | Discussion | References | Acknowledgments
Many real world networks are surprisingly robust again failure of single nodes. Albert et al, 2000 showed that this robustness if only displayed by a class of inhomogeneously wired networks, called scale-free networks, which include the World-Wide Web, the Internet, social networks and cells. Nodes in scale-free networks are able to stay interconnected and hence can communicate even by unrealistically high failure rates. However, these networks are extremely vulnerable to attacks of the very few highly interconnected nodes that hold interconnect many of the nodes in the network.
In this learning module you will examine the error and attack tolerance of a random network, a small world network and a scale free network.
 Usage Hints |
The IVC Software Framework provides access to different algorithms to model and analyze networks:
- Random Networks using the model proposad by Erdös and Rényi, 1957.
- Small World Networks using the model proposad by Watts and Strogatz, 1998.
- Scale-Free Networks using the model proposed by Barabasi and Albert, 2000.
| Learning Task |
Model a random, a small world and a scale-free network with 25 nodes each. For the random graph use a wiring probability of 0.2. For the small world network use a Beta of 0.2 and 2 for the degree of nodes.
Now, randomly delete nodes from each of the three networks using 'Analysis > Network Edit > Delete Random Nodes' to determine the effect of random node failures.
Next, delete the top n highly connected nodes from each of the three networks using 'Analysis > Network Edit > Delete Highly Connected Nodes' to determine the effect of attacks/deletions of highly connected nodes.
Visualize the networks before and after the modifications using Visualization > Kamada-Kawai Layout.
 |
 |
 |
| Random Network | Small-World Network | Scale-Free Network |
Run different search algorithms over the network to see the effect of errors and attacks on search performance. Use the same source and target nodes to perform the search on all the networks. Compare the search performance across 5 runs on each network. See p-rand Breadth-First Search Algorithm and k Random-Walk Search Algorithm for more details.
| Discussion |
In this learning module you used network modeling algorithms to build different types of networks. You similated errors in and the attack of networks and compared the effects for different network topologies. Visualizations were used to communicate network structures. Answer the subsequent questions for yourself:
- What type of network is most robust in case of random node failures?
- What type of network performs well even if highly-connected nodes fail/are attacked?
| References |
- Erdös, P.and A. Rényi (1959) On random graphs, Publicationes Mathematicae, 6:290-297.
- Watts, D. J. and S. H. Strogatz (1998) Collective dynamics of 'small-world' networks. Nature, 393:440.
- Albert, R., Jeong, H. and A.-L. Barabási (2000) Error and attack tolerance in complex networks. Nature, 406:378 - 382.
- Barabasi,
A.-L. and Reka Albert (1999) Emergence of
scaling in random networks. Science, 286:509-512.
| Acknowledgments |
This learning module was compiled by Katy Börner and Hardik Sheth.
Information Visualization
Cyberinfrastructure @ SLIS,
Indiana University
Last Modified August 8, 2004