Go to Google Home
Go
A data-code-compute resource for research and education in information visualization
InfoVis Home Learning Modules Software Databases Compute Resources References

Learning Modules > Error and Attack Tolerance of Networks

Description | Usage Hints | Learning Task | Discussion | References | Acknowledgments


line
Description

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.


line
Usage Hints

The IVC Software Framework provides access to different algorithms to model and analyze networks:

The error and attack tolerance of networks can be tested using 'Analysis > Network Edit > Delete Random Nodes' and 'Analysis > Network Edit > Delete Highly Connected Nodes' respectively.

line
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.


line
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?

line
References

line
Acknowledgments

This learning module was compiled by Katy Börner and Hardik Sheth.

line
Information Visualization Cyberinfrastructure @ SLIS, Indiana University
Last Modified August 8, 2004