Investigating diffusion on networks with long-range interactions: application to object clustering using the generalised heat kernel invariants
Date
2018-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
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.
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.
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.
Description
Thesis (MSc)--Stellenbosch University, 2018.
Keywords
Clustering, Matrices, Mathematical physics -- Research, Heat kernels, Networks, Diffusion -- Mathematical models, UCTD