Elisabetta Bergamini

Elisabetta Bergamini

Auto-generated profile, based on publicly available information

Elisabetta Bergamini

Karlsruhe Institute of Technology, Germany

Research Focus & Metrics

Academic Career Length

11Years (2016-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2016
Verified
Book Chapter
Open access
EBElisabetta Bergamini
Elisabetta Bergamini
MWMichael Wegner
Michael Wegner
DLDimitar Lukarski
Dimitar Lukarski
HMHenning Meyerhenke
Henning Meyerhenke
Matrices associated with graphs, such as the Laplacian, lead to numerous interesting graph problems expressed as linear systems. One field where Laplacian linear systems play a role is network analysis, e. g. for certain centrality measures that indicate if a node (or an edge) is important in the network. One such centrality measure is current-flow closeness. To allow network analysis workflows to profit from a fast Laplacian solver, we provide an implementation of the LAMG multigrid solver in the NetworKit package, facilitating the computation of current-flow closeness values or related quantities. Our main contribution consists of two algorithms that accelerate the current-flow computation for one node or a reasonably small node subset significantly. One algorithm is an unbiased estimator using sampling, the other one is based on the Johnson-Lindenstrauss transform. Our inexact algorithms lead to very accurate results in practice. Thanks to them one is now able to compute an estimation of current-flow closeness of one node on networks with tens of millions of nodes and edges within seconds or a few minutes. From a network analytical point of view, our experiments indicate that current-flow closeness can discriminate among different nodes significantly better than traditional shortest-path closeness and is also considerably more resistant to noise – we thus show that two known drawbacks of shortest-path closeness are alleviated by the current-flow variant.

7 July 2022 in ACM Journal of Experimental Algorithmics
Verified
Journal Article
Open access
AGAlexander van der Grinten
Alexander van der Grinten
EBElisabetta Bergamini
Elisabetta Bergamini
OGOded Green
Oded Green
David BaderDavid Bader
David Bader
HMHenning Meyerhenke
Henning Meyerhenke
Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. In this article, we consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. Previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings; however, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. We extend our algorithm to dynamic graphs while maintaining its correctness guarantees. Experiments demonstrate that our static graph algorithm outperforms both numerical approaches and heuristics with speedups between \( 1.5\times \) and \( 3.5\times \) , depending on the desired quality guarantees. Our dynamic graph algorithm improves upon the static algorithm for update batches of less than 10,000 edges. We provide efficient parallel CPU and GPU implementations of our algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of edges in fractions of seconds.