Structure and randomness in complex networks applied to the target set selection problem : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Manawatu, New Zealand
Loading...
Date
2014
DOI
Open Access Location
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Massey University
Rights
The Author
Abstract
Advances in technology have enabled the empirical study of large, so-called `complex'
networks with tens of thousands to millions of vertices, such as social networks
and large communications networks. It has been discovered that these networks share
a non-random topology characterised mainly by highly skewed, heavy-tailed degree distributions
and small average distances between vertices. The work of this thesis is to
attempt to leverage the well-known topological properties of complex networks to efficiently
solve difficult NP-complete problems, with the aim of obtaining better or faster
solutions than would be possible for general graphs.
Two related NP-complete problems are selected for study: the minimum target set
problem, and the maximum activation set problem. Both problems relate to finding
a `target set' of vertices which is capable of initiating a spreading process (such as
the spread of a rumour) that reaches a large proportion of the network. This thesis
introduces several novel heuristics for these two problems inspired by the topology
of complex networks. It is discovered that in many (but not all) cases it is possible
to make relatively small alterations to the network that enable the computation of a
considerably smaller target set than would be possible on general graphs.
The evaluation of the various heuristics is entirely experimental, which required
the development of procedures to generate `random' networks that can be used as
experimental controls. This thesis includes a survey of several popular techniques for
generating random networks and finds all but one (random rewiring) to be unsuitable
as controls. The validity of random rewiring relies on a somewhat obscure theorem.
Although a proof of the theorem (essentially an existence proof) is already known, this
thesis offers a constructive algorithmic proof. The new proof advances on the old by
providing an upper bound on the maximum number of rewiring operations required
to transform between networks of the same degree-sequence, whereas an upper bound
could not be determined under the old proof.
Description
Keywords
Connections (Mathematics), Complex networks, Target set selection problem, Random rewiring, Research Subject Categories::MATHEMATICS::Applied mathematics::Theoretical computer science