Thesis
Algorithms for exploring structure in complex networks
- Creator
- Rights statement
- Awarding institution
- University of Strathclyde
- Date of award
- 2023
- Thesis identifier
- T16706
- Person Identifier (Local)
- 201766484
- Qualification Level
- Qualification Name
- Department, School or Faculty
- Abstract
- As real-world networks grow increasingly complex, new and adaptable methods are required to analyse and understand the defining features of these networks. To find and exploit these unique network features, current methods, primarily for random model generation and detection of anti-communities, are explored, tested, and adapted with a wide range of networks from disparate fields including neuroscience, ecology, geology, social ecology, linguistics, network theory, psychology, microbiology, gene sequencing, business corporations, and sociology. In particular, to better approximate typical structural features of real-world networks, Erd˝os–R´enyi and scale-free network random models are modified by adding select subgraphs to match real-world networks with the aim of improving their usefulness in network analysis. Before looking for anti-communities we first look at ways to partition graphs into communities. As well as generic techniques such as local improvement methods and spectral partitioning, a number of specialised methods are studied. These include link centrality, similarity, communicability, optimisation, and the Louvain method. We then look at topics associated with near bipartivity in real world graphs. Particular attention is given to the measurement of bipartivity and anti-communities, and their definitions are broadened, refined and tested so that many more networks that demonstrate varying degrees of bipartivity can be analysed using those methods. We prove new theoretical results showing how widely measures can differ and then look to determine the best measures to use, as well as the most effective structure-revealing algorithms. Thorough testing involves nearly one hundred real-world networks including some which have a known tendency for bipartivity (such as airlines networks, and fullerene graphs) as well as near-bipartite graphs based on random trees (including those generated from Pr¨ufer sequences, and other artificially constructed examples. We are able to give conclusions about the measures and methods that should be employed in practice.
- Advisor / supervisor
- Knight, Philip A., 1968-
- Resource Type
- DOI
Relations
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
PDF of thesis T16706 | 2023-10-03 | Public | Download |