Browsing by Author "Nanyanzi, Alice"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- ItemInvestigating diffusion on networks with long-range interactions: application to object clustering using the generalised heat kernel invariants(Stellenbosch : Stellenbosch University, 2018-12) Nanyanzi, Alice; Mutombo, Franck Kalala; Utete, Simukai Wanzira; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Mathematics.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.