Communities in annotated, multilayer, and correlated networks

Thesis

Networks are abstract representations of systems in which objects called "nodes" interact with each other via "edges", typically in a pairwise fashion. Examples of networks include neurons interacting via synapses in the brain, people connected on an online social network, and cities linked by roads. Most real-world networks have a complex structure that is neither fully random nor fully regular, and characterising their "mesoscale" structures is an important topic in network science that is traditionally known as "community detection". Two of the most popular approaches for community detection are maximising an objective function called "modularity" and performing statistical inference using stochastic block models, and these both play a prominent role in our work.

For many applications, an ordinary graph is an inadequate representation of the underlying data. In this thesis, we study community detection in networks that incorporate additional features beyond a set of nodes linked together by edges. First, we study annotated networks, which include additional data as node labels that help describe the network architecture. We then consider multilayer networks, which combine a collection of related networks into a single object. We uncover a deep connection between multilayer modularity maximisation and some multilayer stochastic block models, and we use this result to guide the selection of tuning parameters in modularity maximisation. Finally, we study correlated multilayer networks, in which we sample edges that connect a given pair of nodes across multiple layers from multivariate distributions, rather than as independent events.

Throughout this thesis, we are guided by consumer-behaviour applications. Specifically, we study "bipartite" networks in which customers are linked to products that they previously purchased. Detecting communities in these networks is valuable for designing personalised recommendation systems and for other business insights. We illustrate our main methodological contributions on consumer–product networks that we construct using "pseudonymised" transaction data from several stores of a large UK retailer.

Authors: Pamfil, A

• DOI: 10.5287/ora-g7m0pqaae
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: Community Detection; Multilayer Networks; Bipartite Networks; Network Science
• Subjects: Mathematics; Applied Mathematics