Theory and Application of Temporal Network Embedding

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.

Award Number: 2611677
Principal Investigator: Naoki Masuda
Funds Obligated: $85,411
State: MI