Theory and Application of Temporal Network Embedding

现实世界中的许多复杂系统都可以建模为网络。事实上，许多网络会随着时间而变化。例如，随着人们四处走动，结识不同的人，联系网络会从一种形状转变为另一种形状。在更长的时间尺度上，友谊网络也会随着时间而变化。这种时间（即时变）网络数据已经越来越多地可用，并且可以有效地总结复杂的时间网络数据以帮助增强对数据的直观理解的数学基础方法是可取的。首席研究员（PI）将开发将时间网络数据映射到空间轨迹的方法。具体来说，这些方法将使网络在给定时间点的表示简洁地表示为轨迹上的一个点。这是一个巨大的减少，但这种方式旨在捕获数据的总体属性，并可能将它们用于数据挖掘任务，如可视化、异常检测和发现隐藏的周期性。然后，PI将为所提出的方法建立数学基础，并将其应用于经验数据。所提出的方法有望在在线社交网络服务、金融交易、书目引文数据、神经成像数据和气候时间网络中找到应用，仅举几例。此外，项目成果预计将鼓励数据科学和工程领域的研究人员研究与网络嵌入相关的各种算法（例如，使用深度学习架构）。通过这种方式，该项目涉及多个研究团体和行业。本项目将开发的方法是时间网络嵌入（TNE）方法。与迄今为止可用的大多数TNE方法（其中将节点嵌入潜在空间）相比，PI将追求的TNE方法类别是从网络空间到低维潜在空间的映射。TNE面临的一个基本挑战是，经验数据通常以节点对之间的一组时间戳事件的形式出现，这将在任何给定时间生成一个极其稀疏的网络，阻碍了合理的网络分析。为了克服这种情况，PI将把称为tie-decay temporal networks的建模框架与Nystrom通用降维方法家族结合起来，建立TNE方法家族。这种特殊的技术组合将允许PI缩小方法选择范围，例如应该使用哪种降维方法、网络距离测量和捆绑衰减函数，以及促进有效的计算和数学研究。然后，PI将开发所提出方法的数学基础，如连续性，对马尔可夫输入的响应，以及对输入数据扰动的敏感性。最后，PI将通过将这些方法应用于社会和金融实证数据来展示这些方法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many complex systems in the real world can be modeled as networks. In fact, many networks vary over time. For example, contact networks change from one shape to another as people move around to meet different people. Friendship networks also vary over time on a longer timescale. Such temporal (i.e., time-varying) network data have been increasingly available, and mathematically founded methods that can efficiently summarize complex temporal network data to help enhance intuitive understanding of the data are desirable. The Principal Investigator (PI) will develop methods to map temporal network data to trajectories in a space. Specifically, the methods will enable representation of the network at a given time point succinctly as a point on the trajectory. This is a drastic reduction, but in this manner aims to capture gross properties of the data and potentially use them for data mining tasks such as visualization, anomaly detection, and discovery of hidden periodicity. The PI will then build mathematical foundations of the proposed methods and apply them to empirical data. The proposed methods are expected to find applications in online social network services, financial transactions, bibliographic citation data, neuroimaging data, and climate temporal networks, to name a few. Furthermore, the project outcomes are expected to encourage researchers in data science and engineering to work on various algorithms related to network embedding (e.g., use of deep learning architecture). In this manner, the project relates to multiple research communities and industries. The methods to be developed in this project are temporal network embedding (TNE) methods. In contrast with most TNE methods available to date, in which one embeds nodes into a latent space, the class of TNE methods the PI will pursue is a mapping from the space of networks to a low-dimensional latent space. A fundamental challenge to TNE is that empirical data usually come in the form of a set of time-stamped events between pairs of nodes, which would generate an extremely sparse network at any given time, hampering sensible network analyses. To overcome this situation, the PI will combine the modeling framework called tie-decay temporal networks with a Nystrom family of general-purpose dimension reduction methods to establish a family of TNE methods. This particular combination of techniques will allow the PI to narrow down the methodological choice, such as which dimension reduction methods, network distance measures, and tie-decay functions should be used, as well as to facilitate efficient computations and mathematical investigations. The PI will then develop mathematical foundations of the proposed methods such as continuity, responses to Markovian inputs, and sensitivity to perturbation in the input data. Finally, the PI will showcase the methods by applying them to social and financial empirical data.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.