Speaker
Description
Graph (or network) analysis is concerned with knowledge discovery from graph data. Corresponding analysis methods usually have their roots in graph theory, matrix computations, and statistics.
A growing class of analysis algorithms consists of methods based on the graph's Laplacian matrix. These include traditional methods using Laplacian eigenvectors such as spectral partitioning, spectral clustering, or spectral embedding. In the past 10-15 years, Laplacian linear systems received significant interest in the context of graph analysis as well. They have applications in graph partitioning, graph sparsification, electrical networks, and graph robustness, to name just a few.
Our poster focuses on Laplacian linear systems in the context of centrality measures. Centrality measures indicate the importance of a node (or edge) in the graph based on its position and belong to the most important analysis methods. Typically, they assign a real number to each node (or edge), which yields a ranking. On the poster we review (i) the state of the art concerning efficient algorithms for computing Laplacian-based centrality measures and (ii) describe recent and ongoing work on accelerating such algorithms. We also portray briefly our implementation of the Lean Algebraic Multigrid (LAMG) solver in NetworKit, our growing open-source software for large-scale graph/network analysis.
