FINCA: Fast Inexact Combinatorial and Algebraic Solvers for Massive Networks

许多突破性的技术产生了大量的数据集，其中许多数据集可以建模为网络。生成的数据集包含隐藏在其中的有价值的信息，等待通过合适的分析算法和软件工具进行提取和进一步处理。在这个后续提案（第二个资助期）中，我们将重点关注网络中的距离（包括非标准距离度量）与算法网络分析中的基本主题之间的联系：(i)中心性度量，包括它们（ii）对群体中心性度量的泛化，（iii）影响最大化，以及（iv）网络双曲性。中心性度量表示节点和边的重要性；我们考虑根据节点到其他节点的平均距离对节点进行排序的度量。群体中心性，反过来，旨在识别一组节点，使得每个节点与集合中至少一个元素之间的距离很小。在影响传播中，影响从一个人传播到另一个人的概率可以解释为距离。最后，双曲性是表示图的度量空间与树的度量空间接近程度的一个属性。所有任务都有大量的大数据应用，包括营销策略、路由和网络安全。然而，当前用于这些任务的算法和软件在输入较大或具有复杂结构时显示出严重的局限性。由于大多数现实世界的数据集包含不准确性，我们提倡使用近似算法和启发式的不精确但更快的解决过程。对于上述任务，我们将开发和实现新的、显著改进的算法，用于也可以是动态的大规模网络。可以在合理时间内处理的输入尺寸应比现有技术水平至少增加一个数量级。我们将我们的新方法集成到我们的开源网络分析软件NetworKit中，它尽可能地使用共享内存并行性。该工具对公众和其他SPP项目免费提供，因此促进了我们对需要大量输入的代码的实际问题的直接应用。

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.