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

Simple item page
dc.contributor.authorLowcay, Callum William
dc.date.accessioned2014-11-27T22:11:27Z
dc.date.available2014-11-27T22:11:27Z
dc.date.issued2014
dc.description.abstractAdvances 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.en_US
dc.identifier.urihttp://hdl.handle.net/10179/5969
dc.language.isoenen_US
dc.publisherMassey Universityen_US
dc.rightsThe Authoren_US
dc.subjectConnections (Mathematics)en_US
dc.subjectComplex networksen_US
dc.subjectTarget set selection problemen_US
dc.subjectRandom rewiringen_US
dc.subjectResearch Subject Categories::MATHEMATICS::Applied mathematics::Theoretical computer scienceen_US
dc.titleStructure 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 Zealanden_US
dc.typeThesisen_US
massey.contributor.authorLowcay, Callum Williamen_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorMassey Universityen_US
thesis.degree.levelDoctoralen_US
thesis.degree.nameDoctor of Philosophy (Ph.D.)en_US
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
01_front.pdf
Size:
68.55 KB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
02_whole.pdf
Size:
1.44 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
804 B
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Theses and Dissertations