FINCA: Fast Inexact Combinatorial and Algebraic Solvers for Massive Networks

• Applicant: Professor Dr. Henning Meyerhenke
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 255185982

Numerous groundbreaking technologies generate massive data sets, many of whichcan 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 innetworks (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.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1736: Algorithms for Big Data