Investigating diffusion on networks with long-range interactions: application to object clustering using the generalised heat kernel invariants
| dc.contributor.advisor | Mutombo, Franck Kalala | en_ZA |
| dc.contributor.advisor | Utete, Simukai Wanzira | en_ZA |
| dc.contributor.author | Nanyanzi, Alice | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Mathematics. | en_ZA |
| dc.date.accessioned | 2018-11-27T12:23:37Z | |
| dc.date.accessioned | 2018-12-07T06:57:40Z | |
| dc.date.available | 2018-11-27T12:23:37Z | |
| dc.date.available | 2018-12-07T06:57:40Z | |
| dc.date.issued | 2018-12 | |
| dc.description | Thesis (MSc)--Stellenbosch University, 2018. | en_ZA |
| dc.description.abstract | ENGLISH ABSTRACT : Diffusion on networks is widely used to model dynamical processes on networks such as propagation of information through a social network for marketing purposes [79], spread of epidemics within a social network [41], among others. The most common model (which we refer to as the standard diffusion model) studied in literature is based on the idea that a diffusing substance spreads from one node to another along the edges of the network. Backed by empirical evidence from real-world processes, Estrada et al. [40] put forward another diffusion model in which the substance is considered to spread not only via the edges but also through long-range interactions between non-nearest nodes. These interactions are accounted for using the Mellin or Laplace transforms of k-path Laplacian matrices, where k is the shortest path distance between a given pair of nodes [38]. We propose to refer to this model as the generalised diffusion model. We study this model in some detail and perform simulations based on this model to ascertain the impact of long-range interactions on the diffusion process on networks of different structures. The diffusion equation in its simple and generalised version has been extensively studied in the literature [40, 118, 119]. Its fundamental solution, known as the heat kernel, is very vital with applications ranging from graph characterisation and clustering [118], community detection [72] and node centrality measure [24]. Particularly, we focus on the application of the heat kernel for graph clustering purposes. In [118], the heat kernel associated with the standard diffusion equation is studied and the utility of its invariants to graph characterisation for purposes of clustering has been explored in detail. In this thesis, however, we extend this concept by considering the generalised heat kernel, that is to say, the heat kernel associated with diffusion on networks with long-range interactions taken into account. We discuss how to extract stable and useful invariants of the heat kernel and the use of these invariants in characterisation of graphs for purposes of clustering. Given a database of objects, we obtain a set of graphs representing each of the images and further show how different invariants of the generalised heat kernel can be used to construct feature vectors used for clustering of the objects. We further investigate the impact of longrange influence on the quality of resulting clustering. From the results of the experiments, we deduce that as the value of exponents of the Mellin and Laplace transforms of k-path Laplacian matrices decreases, better clusters are obtained. This can be explained by the fact that an increase in the value of exponents results in a decrease in strength of long-range interactions. | en_ZA |
| dc.description.abstract | AFRIKAANSE OPSOMMING : Diffusie op netwerke word wyd gebruik om dinamiese prosesse op netwerke soos verspreiding van inligting deur ’n sosiale netwerk vir bemarkingsdoeleindes [79], verspreiding van epidemies met in ’n sosiale netwerk [41], onder andere. Die mees algemene model (wat ons verwys na as die standaard diffusie model) bestudeer in die literatuur is gebaseer op die idee dat ’n dif- smeltstof versprei van een knoop na ’n ander langs die kante van die netwerk. Gerugsteun Deur empiriese bewyse uit werklike prosesse, Estrada et al. [40] stel nog ’n ander uiteensetting voor samesmeltingsmodel waarin die stof nie net oor die kante versprei word nie, maar ook deur langafstand interaksies tussen nie-naaste nodes. Hierdie interaksies word verantwoord vir die gebruik van die Mellin- of Laplace-transformasies van k-pad Laplaciese matrikse, waar k die kort- est pad afstand tussen ’n gegewe paar nodes [38]. Ons stel voor om na hierdie model te verwys as die algemene diffusie model. Ons bestudeer hierdie model in detail en voer simulasies uit gebaseer op hierdie model om die impak van langafstandinteraksies op die diffusieproses te bepaal op netwerke van verskillende strukture. Die diffusievergelyking in sy eenvoudige en algemene weergawe is omvattend bestudeer die literatuur [40, 118, 119]. Die fundamentele oplossing, bekend as die hitte kern, is baie belangrik met toepassings wat wissel van grafiek karakterisering en clustering [118], gemeenskap de- tection [72] en node sentraliteitsmaatreël [24]. In die besonder fokus ons op die toepassing van die hitte kern vir grafiek clustering doeleindes. In [118], word die hittepyp geassosieer met die standaard- Dard diffusievergelyking word bestudeer en die nut van sy invariante om grafiekkarakterisering te bepaal Vir die doeleindes van clustering is in detail ondersoek. In hierdie proefskrif verruim ons dit egter konsep deur die algemene hitte kern te oorweeg, dit wil sê die hittepyp wat verband hou met diffusie op netwerke met langafstand interaksies in ag geneem. Ons bespreek hoe Om stabiele en bruikbare invariante van die hitte kern en die gebruik van hierdie invariante in te onttrek karakterisering van grafieke vir die doel van clustering. Gegee ’n databasis van voorwerpe, kry ons ’n stel grafieke wat elk van die beelde verteenwoordig wys verder hoe verskillende invariante van die genormaliseerde hitte kern gebruik kan word om te konstrueer funksie vektore wat gebruik word vir die samestelling van die voorwerpe. Ons ondersoek verder die impak van langtermyn- omvang invloed op die kwaliteit van die gevolglike clustering. Uit die resultate van die eksperimente, ons aflei dit as die waarde van eksponente van die Mellin- en Laplace-transformasies van k-pad Laplaciese matrikse afneem, beter clusters word verkry. Dit kan verklaar word deur die feit dat ’n toename in die waarde van eksponente lei tot ’n afname in sterkte van langafstand interaksies. | af_ZA |
| dc.format.extent | xvi, 109 pages : illustrations (chiefly colour) | en_ZA |
| dc.identifier.uri | http://hdl.handle.net/10019.1/105064 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | en_ZA |
| dc.rights.holder | Stellenbosch University | en_ZA |
| dc.subject | Clustering | en_ZA |
| dc.subject | Matrices | en_ZA |
| dc.subject | Mathematical physics -- Research | en_ZA |
| dc.subject | Heat kernels | en_ZA |
| dc.subject | Networks | en_ZA |
| dc.subject | Diffusion -- Mathematical models | en_ZA |
| dc.subject | UCTD | en_ZA |
| dc.title | Investigating diffusion on networks with long-range interactions: application to object clustering using the generalised heat kernel invariants | en_ZA |
| dc.type | Thesis | en_ZA |