Fast Inexact Combinatorial and Algebraic Solvers for Massive Networks
Numerous groundbreaking technologies generate massive data sets, many of which can be modeled as networks. The produced data sets contain valuable information hidden inside, waiting to be extracted and further processed with suitable analysis algorithms and software tools. In this follow-up proposal (second funding period), we focus on the connection of distances in networks (including non-standard distance measures) with essential topics in algorithmic network analysis: (i) centrality measures, including their (ii) generalization to group centrality measures, (iii) influence maximization, and (iv) network hyperbolicity. Centrality measures indicate importance of nodes and edges; we consider measures that rank the nodes according to their average distance to the other nodes. Group centrality, in turn, aims to identify a set of nodes such that the distance between each node and at least one element of the set is small. In influence spread the probability of propagating influence from one to another can be interpreted as a distance. Finally, hyperbolicity is a property that indicates how much the metric space of a graph is close to that of a tree. All tasks have numerous big data applications, including marketing strategies, routing, and network security. Nevertheless, current algorithms and software for these tasks show serious limitations when the input is large or has a
complex structure. Since most real-world data sets contain inaccuracies, we advocate an inexact, yet faster solution process with approximation algorithms and heuristics. For the aforementioned tasks we will develop and implement new and significantly improved algorithms for large-scale networks that can also be dynamic. The input size that can be handled in reasonable time shall be increased by at least one order of magnitude compared to the state of the art. We integrate our new methods into our open-source network analysis software NetworKit, which uses shared-memory parallelism whenever possible. The tool is freely available to the public and to other SPP projects, hence fostering immediate application of our contributions to real-world problems requiring codes that scale to very large inputs.
Financer
DFG Individual Research Grant
Duration of project
Start date: 10/2017
End date: 11/2020
Research Areas
Theoretical Computer Science
Research Areas
Big Data, Mathematical Modeling and algorithms for exascale simulations and data-intensive science, Theoretische Informatik
Publications
A. van der Grinten, E. Angriman, H. Meyerhenke: Scaling up Network Centrality Computations ‐ a Brief Overview. Accepted by it - Information Technology. Feb. 2020 (to appear), de Gruyter.
Mehmet Şimşek, Henning Meyerhenke, Combined centrality measures for an improved characterization of influence spread in social networks, Journal of Complex Networks, Volume 8, Issue 1, February 2020, cnz048, https://doi.org/10.1093/comnet/cnz048
Alexander van der Grinten, Henning Meyerhenke: Scaling Betweenness Approximation to Billions of Edges by MPI-based Adaptive Sampling. In Proc. 34th IEEE Intl. Parallel and Distributed Processing Symposium (IPDPS'20), IEEE Computer Society.
Eugenio Angriman, Alexander van der Grinten, Aleksandar Bojchevski, Daniel Zügner, Stephan Günnemann, Henning Meyerhenke: Group Centrality Maximization for Large-scale Graphs. ALENEX 2020: 56-69.
Eugenio Angriman, Alexander van der Grinten, Henning Meyerhenke: Local Search for Group Closeness Maximization on Big Graphs. In Proc. IEEE Intl. Conf. Big Data 2019, IEEE Computer Society.
Eugenio Angriman, Alexander van der Grinten, Moritz von Looz, Henning Meyerhenke, Martin Nöllenburg, Maria Predari, Charilaos Tzovas: Guidelines for Experimental Algorithmics: A Case Study in Network Analysis. Algorithms 12(7): 127 (2019)
Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, Henning Meyerhenke: Computing top-k Closeness Centrality Faster in Unweighted Graphs. TKDD 13(5): 53:1-53:40 (2019)
Alexander van der Grinten, Henning Meyerhenke: Scaling up Network Centrality Computations. DATE 2019: 1319-1324
Alexander van der Grinten, Eugenio Angriman, Henning Meyerhenke: Parallel Adaptive Sampling with Almost No Synchronization. Euro-Par 2019: 434-447
Elisabetta Bergamini, Pierluigi Crescenzi, Gianlorenzo D'Angelo, Henning Meyerhenke, Lorenzo Severini, Yllka Velaj: Improving the Betweenness Centrality of a Node by Adding Links. ACM Journal of Experimental Algorithmics 23 (2018)
Moritz von Looz, Henning Meyerhenke: Updating Dynamic Random Hyperbolic Graphs in Sublinear Time. ACM Journal of Experimental Algorithmics 23 (2018)
Henning Meyerhenke, Martin Nöllenburg, Christian Schulz: Drawing Large Graphs by Multilevel Maxent-Stress Optimization. IEEE Trans. Vis. Comput. Graph. 24(5): 1814-1827 (2018)
Patrick Bisenius, Elisabetta Bergamini, Eugenio Angriman, Henning Meyerhenke: Computing Top-k Closeness Centrality in Fully-dynamic Graphs. ALENEX 2018: 21-35
Elisabetta Bergamini, Tanya Gonser, Henning Meyerhenke: Scaling up Group Closeness Maximization. ALENEX 2018: 209-222
Alexander van der Grinten, Elisabetta Bergamini, Oded Green, David A. Bader, Henning Meyerhenke: Scalable Katz Ranking Computation in Large Static and Dynamic Graphs. ESA 2018: 42:1-42:14
Roland Glantz, Henning Meyerhenke: Many-to-many Correspondences between Partitions: Introducing a Cut-based Approach. SDM 2018: 1-9