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.