Investigating diffusion on networks with long-range interactions: application to object clustering using the generalised heat kernel invariants

[摘要] ENGLISH ABSTRACT : Diffusion on networks is widely used to model dynamical processes on networks such aspropagation of information through a social network for marketing purposes [79], spread ofepidemics within a social network [41], among others. The most common model (which werefer 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. Backedby 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 alsothrough long-range interactions between non-nearest nodes. These interactions are accountedfor 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 thegeneralised diffusion model. We study this model in some detail and perform simulationsbased on this model to ascertain the impact of long-range interactions on the diffusion processon networks of different structures.The diffusion equation in its simple and generalised version has been extensively studied inthe literature [40, 118, 119]. Its fundamental solution, known as the heat kernel, is very vitalwith applications ranging from graph characterisation and clustering [118], community detection [72] and node centrality measure [24]. Particularly, we focus on the application of theheat 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 characterisationfor purposes of clustering has been explored in detail. In this thesis, however, we extend thisconcept by considering the generalised heat kernel, that is to say, the heat kernel associatedwith 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 incharacterisation of graphs for purposes of clustering.Given a database of objects, we obtain a set of graphs representing each of the images andfurther show how different invariants of the generalised heat kernel can be used to constructfeature 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-pathLaplacian matrices decreases, better clusters are obtained. This can be explained by the factthat an increase in the value of exponents results in a decrease in strength of long-rangeinteractions.

[发布机构] Stellenbosch University