CIF: SMALL: Metric Representations of Network Data

CIF：SMALL：网络数据的公制表示

• 批准号: 1717120
• 负责人: Alejandro Ribeiro
• 金额: $ 45万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1717120&HistoricalAwards=false
• 关键词: CIF; SMALL; Metric; Representations; Network

Network data, defined as one that encodes relationships between elements, is a pervasive component of modern data analytics. The purpose of this project is to advance our capacity to process and understand network data. The contention is that the central difficulty in analyzing large-scale complex networks comes from lack of structure. This loose nature contrasts with the rigidity of a closely related construction: the metric space. If understanding networks is challenging but understanding metric spaces is not, a route to network analysis is to project networks into metric spaces. This motivates the technical goal of designing methods and algorithms to implement these projections. The project builds on preliminary results combining a projection axiom (networks that are already metric remain unchanged after projection) and a dissimilarity-reducing axiom (smaller networks have smaller projections) to establish existence and uniqueness results. Further explorations are pursued in four thrusts: (1) Study of projection methods in symmetric networks. (2) Incorporation of asymmetric networks and asymmetric quasimetric spaces. (3) Metric representations derived from triangle inequalities written in dioid algebras; which albeit metric in an abstract sense are very different from regular metrics. (4) Generalizations to high order networks in which dissimilarities are defined for tuples other than binary. Applications to search, network comparison, and diffusion processes, complement the theoretical research. Broader impacts come through industrial partnerships and an aggressive educational agenda that leverages the University of Pennsylvania's institutional commitment to play a leading role in the education of engineers that are to exploit the opportunities afforded by the ever increasing access to data and the ever broadening scope that networks play in our society.

网络数据被定义为对元素之间的关系进行编码的数据，是现代数据分析的普遍组成部分。该项目的目的是提高我们处理和理解网络数据的能力。争论的焦点是，分析大规模复杂网络的主要困难来自缺乏结构。这种松散的性质与一个密切相关的结构--度量空间--的刚性形成对比。如果理解网络具有挑战性，而理解度量空间不具有挑战性，那么网络分析的一个途径就是将网络投影到度量空间中。这激发了设计方法和算法来实现这些投影的技术目标。该项目建立在初步结果的基础上，结合了投影公理（已经是度量的网络在投影后保持不变）和相异减少公理（较小的网络具有较小的投影），以建立存在性和唯一性结果。本文主要从四个方面进行了深入的研究：（1）对称网络中投影方法的研究。(2)非对称网络与非对称拟度量空间的结合。(3)度量表示来自三角形不等式写在dioid代数;虽然度量在抽象意义上是非常不同的常规度量。(4)推广到高阶网络，其中为二元以外的元组定义了相异性。应用于搜索，网络比较和扩散过程，补充了理论研究。更广泛的影响来自工业伙伴关系和积极的教育议程，该议程利用宾夕法尼亚大学的机构承诺，在工程师教育中发挥主导作用，以利用不断增加的数据访问和网络在我们社会中发挥的不断扩大的范围所提供的机会。

项目成果

Controllability of Bandlimited Graph Processes Over Random Time Varying Graphs

• DOI: 10.1109/tsp.2019.2952053
• 发表时间: 2019-04
• 期刊: IEEE Transactions on Signal Processing
• 影响因子: 5.4
• 作者: Fernando Gama;E. Isufi;Alejandro Ribeiro;G. Leus