Associate Professor (Reader) in Machine Learning
School of Mathematics, The University of Edinburgh
The Maxwell Institute for Mathematical Sciences
School of Mathematics, Gran Sasso Science Institute
JCMB, King’s Buildings, Edinburgh EH93FD UK
email: f dot tudisco at ed.ac.uk
Abstract: One of the most relevant tasks in network analysis is the detection of community structures, or clustering. Most popular techniques for community detection are based on the maximization of a quality function called modularity, which in turn is based upon particular quadratic forms associated to a real symmetric modularity matrix $M$, defined in terms of the adjacency matrix and a rank one null model matrix. That matrix could be posed inside the set of relevant matrices involved in graph theory, alongside adjacency, incidence and Laplacian matrices. ... Read more
Abstract: When a linear system $Ax = y$ is solved by means of iterative methods (mainly CG and GMRES) and the convergence rate is slow, one may consider a preconditioner $P$. The use of such preconditioner changes the spectrum of the matrix defining the system and could result into a great acceleration of the convergence rate. The construction of optimal rank preconditioners is strongly related to the possibility of splitting $A$ as $A = P + R + E$, where $E$ is a small perturbation and $R$ is of low rank. ... Read more
Abstract: Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler-Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra $\mathcal U$ of matrices, thereby obtaining an ER-$\mathcal U$ method, and we observe that ER-$\mathcal U$ can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. ... Read more