BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Henning Meyerhenke

Henning Meyerhenke contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingSocial and Information NetworksMachine LearningComputational Engineering, Finance, and ScienceHuman-Computer Interactionphysics.ao-phphysics.soc-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2022arXiv

Fast Dynamic Updates and Dynamic SpGEMM on MPI-Distributed Graphs

Sparse matrix multiplication (SpGEMM) is a fundamental kernel used in many diverse application areas, both numerical and discrete. For example, many algebraic graph algorithms rely on SpGEMM in the tropical semiring to compute shortest paths in graphs. Recently, SpGEMM has received growing attention regarding implementations for specific (parallel) architectures. Yet, this concerns only the static problem, where both input matrices do not change. In many applications, however, matrices (or their corresponding graphs) change over time. Although recomputing from scratch is very expensive, we are not aware of any dynamic SpGEMM algorithms in the literature. In this paper, we thus propose a batch-dynamic algorithm for MPI-based parallel computing. Building on top of a distributed graph/matrix data structure that allows for fast updates, our dynamic SpGEMM reduces the communication volume significantly. It does so by exploiting that updates change far fewer matrix entries than there are non-zeros in the input operands. Our experiments with popular benchmark graphs show that our approach pays off. For batches of insertions or removals of matrix entries, our dynamic SpGEMM is substantially faster than the static algorithms in the state-of-the-art competitors CombBLAS, CTF and PETSc.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Interactive Visualization of Protein RINs using NetworKit in the Cloud

Network analysis has been applied in diverse application domains. In this paper, we consider an example from protein dynamics, specifically residue interaction networks (RINs). In this context, we use NetworKit -- an established package for network analysis -- to build a cloud-based environment that enables domain scientists to run their visualization and analysis workflows on large compute servers, without requiring extensive programming and/or system administration knowledge. To demonstrate the versatility of this approach, we use it to build a custom Jupyter-based widget for RIN visualization. In contrast to existing RIN visualization approaches, our widget can easily be customized through simple modifications of Python code, while both supporting a good feature set and providing near real-time speed. It is also easily integrated into analysis pipelines (e.g., that use Python to feed RIN data into downstream machine learning tasks).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

More Recent Advances in (Hyper)Graph Partitioning

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 algorithms for balanced (hyper)graph partitioning together with future research directions. Our work serves as an update to a previous survey on the topic. In particular, the survey extends the previous survey by also covering hypergraph partitioning and streaming algorithms, and has an additional focus on parallel algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Tarema: Adaptive Resource Allocation for Scalable Scientific Workflows in Heterogeneous Clusters

Scientific workflow management systems like Nextflow support large-scale data analysis by abstracting away the details of scientific workflows. In these systems, workflows consist of several abstract tasks, of which instances are run in parallel and transform input partitions into output partitions. Resource managers like Kubernetes execute such workflow tasks on cluster infrastructures. However, these resource managers only consider the number of CPUs and the amount of available memory when assigning tasks to resources; they do not consider hardware differences beyond these numbers, while computational speed and memory access rates can differ significantly. We propose Tarema, a system for allocating task instances to heterogeneous cluster resources during the execution of scalable scientific workflows. First, Tarema profiles the available infrastructure with a set of benchmark programs and groups cluster nodes with similar performance. Second, Tarema uses online monitoring data of tasks, assigning labels to tasks depending on their resource usage. Third, Tarema uses the node groups and task labels to dynamically assign task instances evenly to resources based on resource demand. Our evaluation of a prototype implementation for Kubernetes, using five real-world Nextflow workflows from the popular nf-core framework and two 15-node clusters consisting of different virtual machines, shows a mean reduction of isolated job runtimes by 19.8% compared to popular schedulers in widely-used resource managers and 4.54% compared to the heuristic SJFN, while providing a better cluster usage. Moreover, executing two long-running workflows in parallel and on restricted resources shows that Tarema is able to reduce the runtimes even more while providing a fair cluster usage.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis

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 measures for the analysis of large small-world graphs $G = (V, E)$ -- i.e., graphs with diameter in $O(\log |V|)$, which are abundant in complex network analysis. From a computational point of view, the three measures have in common that their crucial component is the diagonal of the graph Laplacian's pseudoinverse, $L^\dagger$. Computing diag$(L^\dagger)$ exactly by pseudoinversion, however, is as expensive as dense matrix multiplication -- and the standard tools in practice even require cubic time. Moreover, the pseudoinverse requires quadratic space -- hardly feasible for large graphs. Resorting to approximation by, e.g., using the Johnson-Lindenstrauss transform, requires the solution of $O(\log |V| / ε^2)$ Laplacian linear systems to guarantee a relative error, which is still very expensive for large inputs. In this paper, we present a novel approximation algorithm that requires the solution of only one Laplacian linear system. The remaining parts are purely combinatorial -- mainly sampling uniform spanning trees, which we relate to diag$(L^\dagger)$ via effective resistances. For small-world networks, our algorithm obtains a $\pm ε$-approximation with high probability, in a time that is nearly-linear in $|E|$ and quadratic in $1 / ε$. Another positive aspect of our algorithm is its parallel nature due to independent sampling. We thus provide two parallel implementations of our algorithm: one using OpenMP, one MPI + OpenMP. In our experiments against the state of the art, our algorithm (i) yields more accurate results, (ii) is much faster and more memory-efficient, and (iii) obtains good parallel speedups, in particular in the distributed setting.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

New Approximation Algorithms for Forest Closeness Centrality -- for Individual Vertices and Vertex Groups

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 mining. A measure that is gaining attention is forest closeness centrality; it is closely related to electrical measures using current flow but can also handle disconnected graphs. Recently, [Jin et al., ICDM'19] proposed an algorithm to approximate this measure probabilistically. Their algorithm processes small inputs quickly, but does not scale well beyond hundreds of thousands of vertices. In this paper, we first propose a different approximation algorithm; it is up to two orders of magnitude faster and more accurate in practice. Our method exploits the strong connection between uniform spanning trees and forest distances by adapting and extending recent approximation algorithms for related single-vertex problems. This results in a nearly-linear time algorithm with an absolute probabilistic error guarantee. In addition, we are the first to consider the problem of finding an optimal group of vertices w.r.t. forest closeness. We prove that this latter problem is NP-hard; to approximate it, we adapt a greedy algorithm by [Li et al., WWW'19], which is based on (partial) matrix inversion. Moreover, our experiments show that on disconnected graphs, group forest closeness outperforms existing centrality measures in the context of semi-supervised vertex classification.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

The climatic interdependence of extreme-rainfall events around the globe

The identification of regions of similar climatological behavior can be utilized for the discovery of spatial relationships over long-range scales, including teleconnections. In this regard, the global picture of the interdependence patterns of extreme rainfall events (EREs) still needs to be further explored. To this end, we propose a top-down complex-network-based clustering workflow, with the combination of consensus clustering and mutual correspondences. Consensus clustering provides a reliable community structure under each dataset, while mutual correspondences build a matching relationship between different community structures obtained from different datasets. This approach ensures the robustness of the identified structures when multiple datasets are available. By applying it simultaneously to two satellite-derived precipitation datasets, we identify consistent synchronized structures of EREs around the globe, during boreal summer. Two of them show independent spatiotemporal characteristics, uncovering the primary compositions of different monsoon systems. They explicitly manifest the primary intraseasonal variability in the context of the global monsoon, in particular the `monsoon jump' over both East Asia and West Africa and the mid-summer drought over Central America and southern Mexico. Through a case study related to the Asian summer monsoon (ASM), we verify that the intraseasonal changes of upper-level atmospheric conditions are preserved by significant connections within the global synchronization structure. Our work advances network-based clustering methodology for (i) decoding the spatiotemporal configuration of interdependence patterns of natural variability and for (ii) the intercomparison of these patterns, especially regarding their spatial distributions over different datasets.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Combined Centrality Measures for an Improved Characterization of Influence Spread in Social Networks

Influence Maximization (IM) aims at finding the most influential users in a social network, i. e., users who maximize the spread of an opinion within a certain propagation model. Previous work investigated the correlation between influence spread and nodal centrality measures to bypass more expensive IM simulations. The results were promising but incomplete, since these studies investigated the performance (i. e., the ability to identify influential users) of centrality measures only in restricted settings, e. g., in undirected/unweighted networks and/or within a propagation model less common for IM. In this paper, we first show that good results within the Susceptible- Infected-Removed (SIR) propagation model for unweighted and undirected networks do not necessarily transfer to directed or weighted networks under the popular Independent Cascade (IC) propagation model. Then, we identify a set of centrality measures with good performance for weighted and directed networks within the IC model. Our main contribution is a new way to combine the centrality measures in a closed formula to yield even better results. Additionally, we also extend gravitational centrality (GC) with the proposed combined centrality measures. Our experiments on 50 real-world data sets show that our proposed centrality measures outperform well-known centrality measures and the state-of-the art GC measure significantly. social networks, influence maximization, centrality measures, IC propagation model, influential spreaders

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

High-Quality Hierarchical Process Mapping

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 topology of a distributed system is known an important task is then to map the blocks of the partition onto the processors such that the overall communication cost is reduced. We present novel multilevel algorithms that integrate graph partitioning and process mapping. Important ingredients of our algorithm include fast label propagation, more localized local search, initial partitioning, as well as a compressed data structure to compute processor distances without storing a distance matrix. Experiments indicate that our algorithms speed up the overall mapping process and, due to the integrated multilevel approach, also find much better solutions in practice. For example, one configuration of our algorithm yields better solutions than the previous state-of-the-art in terms of mapping quality while being a factor 62 faster. Compared to the currently fastest iterated multilevel mapping algorithm Scotch, we obtain 16% better solutions while investing slightly more running time.

0 citations0 reviewsNo code linkedOpen access