Computer Science

Colloquium Details

Small-World Communication Networks

Abstract

Many real world networks, including the world wide web, electric power grids, social networks, and the network of mathematicians with finite Erdos numbers, can be modelled as small-world networks. The three main distinguishing characteristics of small-world networks are high local connectedness or clustering (nodes have many mutual neighbours), sparseness, and small average or maximum distances between pairs of nodes. In communication networks, typical traffic patterns exhibit large amounts of local communication, and fast communication between arbitrary pairs of nodes is also needed, so small-world networks are natural candidates for communication networks. I will show how to construct deterministic small-world networks that exhibit the same properties as naturally-occurring small-world networks such as social networks.

The patterns by which contagious diseases spread in networks resemble the broadcasting communication pattern, in which the information of an originating node is distributed to the other nodes of a network. This is true for both human diseases in social networks and computer viruses. Cascaded network failures also follow a broadcast-like pattern. I will describe a parameterized deterministic model that can be adjusted to model different ways that a virus can spread in a communication network. I will then show that viruses can spread very quickly in small-world networks and that without active intervention such as the use of firewalls, a virus is guaranteed to infect all nodes of these networks.