FINCA: Fast Inexact Combinatorial and Algebraic Solvers for Massive Networks

FINCA：大规模网络的快速不精确组合和代数求解器

• 批准号: 255185982
• 负责人: Professor Dr. Henning Meyerhenke
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Priority Programmes
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2020-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/255185982?language=en
• 关键词: FINCA; Fast; Inexact; Combinatorial; Algebraic

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.

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