187 citations · 581 across the 39 of their papers we have counts for
29 papers · 1 filter
More Recent Advances in (Hyper)Graph Partitioning
Ümit V. Çatalyürek, Karen D. Devine, Marcelo Fonseca Faraj +8
In recent years, significant advances have been made in the design and evaluation of balanced (hyper)graph partitioning algorithms. We survey trends of the last decade in practical…
Fully-dynamic Weighted Matching Approximation in Practice
Eugenio Angriman, Henning Meyerhenke, Christian Schulz +1
Finding large or heavy matchings in graphs is a ubiquitous combinatorial optimization problem. In this paper, we engineer the first non-trivial implementations for approximating th…
New Approximation Algorithms for Forest Closeness Centrality -- for Individual Vertices and Vertex Groups
Alexander van der Grinten, Eugenio Angriman, Maria Predari +1
The emergence of massive graph data sets requires fast mining algorithms. Centrality measures to identify important vertices belong to the most popular analysis methods in graph mi…
Group-Harmonic and Group-Closeness Maximization -- Approximation and Engineering
Eugenio Angriman, Ruben Becker, Gianlorenzo D'Angelo +3
Centrality measures characterize important nodes in networks. Efficiently computing such nodes has received a lot of attention. When considering the generalization of computing cen…
Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis
Eugenio Angriman, Maria Predari, Alexander van der Grinten +1
The ubiquity of massive graph data sets in numerous applications requires fast algorithms for extracting knowledge from these data. We are motivated here by three electrical measur…
High-Quality Hierarchical Process Mapping
Marcelo Fonseca Faraj, Alexander van der Grinten, Henning Meyerhenke +2
Partitioning graphs into blocks of roughly equal size such that few edges run between blocks is a frequently needed operation when processing graphs on a parallel computer. When a…
Local Search for Group Closeness Maximization on Big Graphs
Eugenio Angriman, Alexander van der Grinten, Henning Meyerhenke
In network analysis and graph mining, closeness centrality is a popular measure to infer the importance of a vertex. Computing closeness efficiently for individual vertices receive…
Group Centrality Maximization for Large-scale Graphs
Eugenio Angriman, Alexander van der Grinten, Aleksandar Bojchevski +3
The study of vertex centrality measures is a key aspect of network analysis. Naturally, such centrality measures have been generalized to groups of vertices; for popular measures i…
Scalable Katz Ranking Computation in Large Static and Dynamic Graphs
Alexander van der Grinten, Elisabetta Bergamini, Oded Green +2
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 net…
Updating Dynamic Random Hyperbolic Graphs in Sublinear Time
Moritz von Looz, Henning Meyerhenke
Generative network models play an important role in algorithm development, scaling studies, network analysis, and realistic system benchmarks for graph data sets. A complex network…
Computing Top-k Closeness Centrality in Fully-dynamic Graphs
Patrick Bisenius, Elisabetta Bergamini, Eugenio Angriman +1
Closeness is a widely-studied centrality measure. Since it requires all pairwise distances, computing closeness for all nodes is infeasible for large real-world networks. However,…
Scaling up Group Closeness Maximization
Elisabetta Bergamini, Tanya Gonser, Henning Meyerhenke
Closeness is a widely-used centrality measure in social network analysis. For a node it indicates the reciprocal of the average shortest-path distance to the other nodes of the net…
Maxent-Stress Optimization of 3D Biomolecular Models
Michael Wegner, Oskar Taubert, Alexander Schug +1
Knowing a biomolecule's structure is inherently linked to and a prerequisite for any detailed understanding of its function. Significant effort has gone into developing technologie…
Faster Betweenness Centrality Updates in Evolving Networks
Elisabetta Bergamini, Henning Meyerhenke, Mark Ortmann +1
Finding central nodes is a fundamental problem in network analysis. Betweenness centrality is a well-known measure which quantifies the importance of a node based on the fraction o…
Computing top-k Closeness Centrality Faster in Unweighted Graphs
Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi +2
Given a connected graph , the closeness centrality of a vertex is defined as . This measure is widely used in the analysis of real-w…
Improving the betweenness centrality of a node by adding links
Elisabetta Bergamini, Pierluigi Crescenzi, Gianlorenzo D'Angelo +3
Betweenness is a well-known centrality measure that ranks the nodes according to their participation in the shortest paths of a network. In several scenarios, having a high between…
Estimating Current-Flow Closeness Centrality with a Multigrid Laplacian Solver
Elisabetta Bergamini, Michael Wegner, Dimitar Lukarski +1
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 rol…
Generating massive complex networks with hyperbolic geometry faster in practice
Moritz von Looz, Mustafa Özdayi, Sören Laue +1
Generative network models play an important role in algorithm development, scaling studies, network analysis, and realistic system benchmarks for graph data sets. The commonly used…
Better partitions of protein graphs for subsystem quantum chemistry
Moritz von Looz, Mario Wolter, Christoph R. Jacob +1
Determining the interaction strength between proteins and small molecules is key to analyzing their biological function. Quantum-mechanical calculations such as \emph{Density Funct…
k-way Hypergraph Partitioning via n-Level Recursive Bisection
Sebastian Schlag, Vitali Henne, Tobias Heuer +3
We develop a multilevel algorithm for hypergraph partitioning that contracts the vertices one at a time. Using several caching and lazy-evaluation techniques during coarsening and…
Approximating Betweenness Centrality in Fully-dynamic Networks
Elisabetta Bergamini, Henning Meyerhenke
Betweenness is a well-known centrality measure that ranks the nodes of a network according to their participation in shortest paths. Since an exact computation is prohibitive in la…
Querying Probabilistic Neighborhoods in Spatial Data Sets Efficiently
Moritz von Looz, Henning Meyerhenke
In this paper we define the notion of a probabilistic neighborhood in spatial data: Let a set of points in , a query…
Drawing Large Graphs by Multilevel Maxent-Stress Optimization
Henning Meyerhenke, Martin Nöllenburg, Christian Schulz
Drawing large graphs appropriately is an important step for the visual analysis of data from real-world networks. Here we present a novel multilevel algorithm to compute a graph la…
n-Level Hypergraph Partitioning
Vitali Henne, Henning Meyerhenke, Peter Sanders +2
We develop a multilevel algorithm for hypergraph partitioning that contracts the vertices one at a time and thus allows very high quality. This includes a rating function that avoi…