The impact of topology on diffusion processes in complex networks

Abstract

In this thesis we explore how the structure of a network impacts upon spreading behaviours on that network. We have created a dataset of 2,400 hyperbolic random geometric graphs, of increasing edge density from 0 to 1, and analysed local and global graph properties in the set, with a view to correlating graph properties with emergent behaviours in the set of graphs. These networks share many features of real world complex networks, such as power law degree distribution, high clustering and short path length.

A key focus is on observing the impact that the net result of all the local node interactions will have on the emergent behaviour in a population. When an individual node in a population is viewed in isolation, it is extremely difficult to forecast the likely global effect this one node might have on a spreading process. In spatial networks, each node is an integral part of a neighbourhood, defined by its links with its neighbours. This community structure can have a profound effect on the outcome of a spreading process, such as the spread of a disease, or the adoption of an activity within a population.

Modelling such networks also provides opportunities to control the outcomes, for example, looking at measures to control the spread of a contagion by identifying influential nodes. In a computer network, hub nodes might be selected to receive enhanced virus protection, or key players in a population might be immunised in an epidemic scenario. Governments might seek to identify influential nodes to enhance the spread of public information and warnings in emergency situations.

Our experiments use agent based simulation of diffusion processes on the set of graphs. We observe the evolution of defection in the simple game of the Prisoner’s Dilemma, and the spread of an activity by bootstrap percolation. In both processes, we observed a clearly defined state transition threshold as the number of edges increases in the set of graphs. Above the threshold, the activity completely spread, below the threshold, the network was robust against the spread. Our analysis of graph properties allows us to correlate emergent behaviour with topological features in the graphs. This has allowed insights into features of the graphs which inhibit or facilitate the spread of an activity.

As an extension to this work, we developed a modified form of the standard bootstrap percolation process, which allows for recovery. This introduces a stochastic element to an otherwise deterministic process. This had a delaying impact on the spread of an activity, which was enhanced when targeted at nodes of high degree, compared with at random.

In our final set of simulations, our goal is to enhance this inhibitory effect on percolation, returning to the standard form of bootstrap percolation, by specific targeting of nodes to be immune to the percolation process. Instead of allowing a percentage of active nodes to recover, we investigate outcomes when certain nodes are chosen to be unaffected by the percolation process, essentially granting them immunity from percolation. Our selected graph properties were high degree, betweenness and closeness centrality, low local clustering, and random for comparison.

This work has demonstrated that identifying influential nodes and targeting them for immunity has an inhibitory effect on the bootstrap percolation process on hyperbolic networks, when compared with random immunity. This indicates that in these graphs certain nodes are highly influential in the network and warrant being protected. Our results suggest that under similar conditions it may be possible to immunise a relatively small number of influential nodes and effectively grant herd immunity to the whole network.