Deformed Laplacians on Graphs and Networks with Applications to Ranking, Visualization and Community Detection

Michael Fanuel¹

Many problems related to graphs and networks, like for instance multiscale community detection or visualization, can be solved by using the so-called combinatorial Laplacian. Various diffusion processes on networks are generated by a series of normalized combinatorial Laplacians, providing efficient tools in many applications. Recently, several deformations of this discrete Laplacian have been used for solving a variety of problems in applied mathematics; some important examples are the signed Laplacian and the connection Laplacian. Within this context, we propose a class of deformed Laplacians and discuss their properties in view of applications. Among all the options, a possible deformation is the dilation Laplacian whose least eigenvector (i.e., the one of the smallest eigenvalue) can be used to rank objects from “noisy” pairwise comparisons; in this problem, the objects are the nodes of a graph and the comparisons are the directed edges. The nodes may for instance represent currencies and the edges may be associated to exchange rates. While still using the dilation Laplacian, we can compute a ranking of players in sport tournaments, where cyclic inconsistencies in the comparisons may arise. Another type of deformed Laplacian is the magnetic Laplacian, which is complex valued and Hermitian. The least eigenvectors of the magnetic Laplacian, called the magnetic eigenmaps, can be used in order to visualize directed networks and to uncover certain types of community structures in directed graphs. In this talk, an overview of the construction of such deformed Laplacians will be given in the light of certain analogies with physical systems. Several illustrations of potential applications will be outlined.