Applications of graph theory to real-world networks

Abstract

We apply graph theory to two problems involving real-world networks. The first problem is to model sexual contact networks, while the second involves criminal networks. The structure of an underlying sexual contact network is important for the investigation of sexually transmitted infections. Some measures are very difficult to estimate for real-world contact networks. Therefore, mathematical models and simulations can be used for estimating these measures. In this paper we introduce the spatially embedded evolving network model. We compare simulated results to real-world data from two surveys against three measures of sexual contact networks: the number of partners; duration of partnerships; gaps and overlaps lengths. We found that each of these measures can be captured independently by our model by choosing suitable values of the input parameters. Investigation of drug markets and the criminal syndicates groups that operate within them is important in order to target drug law enforcement interventions in the most effective ways. We explore the effectiveness of four different hypothetical intervention strategies that aim to dismantle a criminal network: interventions which target individuals based on degree; interventions which target individuals based on role; interventions which combine the first two strategies; and random intervention. The results of our research shows that the most effective strategy is targeting individuals based on high degree and roles within the networks.