An official website of the United States government
We present a novel framework to represent sets of time-varying signals as dynamic graphs using the non-negative kernel (NNK) graph construction. We extend the original NNK framework to allow explicit delays as part of the graph construction, so that unlike in NNK, two nodes can be connected with an edge corresponding to a non-zero time delay, if there is higher similarity between the signals after shifting one of them. We also propose to characterize the similarity between signals at different nodes using the node degree and clustering coefficients of their respective visibility graphs. Graph edges that can representing temporal delays, we provide a new perspective that enables us to see the effect of synchronization in graph construction for time-series signals. For both temperature and EEG datasets, we show that our proposed approach can achieve sparse and interpretable graph representations. Furthermore, the proposed method can be useful in characterizing different EEG experiments using sparsity.
more »
« less
An Adjacency Matrix Approach to Delay Analysis in Temporal Networks
Wireless communications networks are often mod- eled as graphs in which the vertices represent wireless devices and the edges represent the communication links between them. However, graphs fail to capture the time-varying nature of wire- less networks. Temporal networks are graphs in which the sets of nodes or edges are time-varying. We consider the most common case, in which the set of nodes is fixed but the presence of edges changes over time. Most previous work on analyzing temporal networks has focused on summary measures that combine the contributions of different paths by using different weights for paths with different delays. Such summary measures are efficient to compute but may lose valuable information about the temporal behavior of the network. We propose techniques that characterize the delays of all paths between nodes in temporal networks. We then apply these techniques to identify dominant patterns in the temporal paths connecting nodes. Example temporal networks are used to illustrate these phenomena, and we consider implications to wireless networks.
more »
« less
- Award ID(s):
- 1642973
- PAR ID:
- 10046905
- Date Published:
- Journal Name:
- MILCOM IEEE Military Communications Conference
- ISSN:
- 2155-7578
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Many real-world networks evolve over time, and predicting the evolution of such networks remains a challenging task. Graph Neural Networks (GNNs) have shown empirical success for learning on static graphs, but they lack the ability to effectively learn from nodes and edges with different timestamps. Consequently, the prediction of future properties in temporal graphs remains a relatively under-explored area. In this paper, we aim to bridge this gap by introducing a principled framework, named GraphPulse. The framework combines two important techniques for the analysis of temporal graphs within a Newtonian framework. First, we employ the Mapper method, a key tool in topological data analysis, to extract essential clustering information from graph nodes. Next, we harness the sequential modeling capabilities of Recurrent Neural Networks (RNNs) for temporal reasoning regarding the graph's evolution. Through extensive experimentation, we demonstrate that our model enhances the ROC-AUC metric by 10.2% in comparison to the top-performing state-of-the-art method across various temporal networks. We provide the implementation of GraphPulse at https://github.com/kiarashamsi/GraphPulse.more » « less
-
Many real-world networks evolve over time, and predicting the evolution of such networks remains a challenging task. Graph Neural Networks (GNNs) have shown empirical success for learning on static graphs, but they lack the ability to effectively learn from nodes and edges with different timestamps. Consequently, the prediction of future properties in temporal graphs remains a relatively under-explored area. In this paper, we aim to bridge this gap by introducing a principled framework, named GraphPulse. The framework combines two important techniques for the analysis of temporal graphs within a Newtonian framework. First, we employ the Mapper method, a key tool in topological data analysis, to extract essential clustering information from graph nodes. Next, we harness the sequential modeling capabilities of Recurrent Neural Networks (RNNs) for temporal reasoning regarding the graph's evolution. Through extensive experimentation, we demonstrate that our model enhances the ROC-AUC metric by 10.2% in comparison to the top-performing state-of-the-art method across various temporal networks. We provide the implementation of GraphPulse at https://github.com/kiarashamsi/GraphPulse.more » « less
-
This work presents a framework for studying temporal networks using zigzag persistence, a tool from the field of Topological Data Analysis (TDA). The resulting approach is general and applicable to a wide variety of time-varying graphs. For example, these graphs may correspond to a system modeled as a network with edges whose weights are functions of time, or they may represent a time series of a complex dynamical system. We use simplicial complexes to represent snapshots of the temporal networks that can then be analyzed using zigzag persistence. We show two applications of our method to dynamic networks: an analysis of commuting trends on multiple temporal scales, e.g., daily and weekly, in the Great Britain transportation network, and the detection of periodic/chaotic transitions due to intermittency in dynamical systems represented by temporal ordinal partition networks. Our findings show that the resulting zero- and one-dimensional zigzag persistence diagrams can detect changes in the networks’ shapes that are missed by traditional connectivity and centrality graph statistics.more » « less
-
The analysis of social and biological networks often involves model- ing clusters of interest as cliques or their graph-theoretic generaliza- tions. The 𝑘-club model, which relaxes the requirement of pairwise adjacency in a clique to length-bounded paths inside the cluster, has been used to model cohesive subgroups in social networks and functional modules/complexes in biological networks. However, if the graphs are time-varying, or if they change under different conditions, we may be interested in clusters that preserve their property over time or under changes in conditions. To model such clusters that are conserved in a collection of graphs, we consider a cross-graph 𝑘-club model, a subset of nodes that forms a 𝑘-club in every graph in the collection. In this paper, we consider the canonical optimization problem of finding a cross-graph 𝑘-club of maximum cardinality. We introduce algorithmic ideas to solve this problem and evaluate their performance on some benchmark instances. Published in: Proceedings of The International Network Optimization Conference (INOC) 2022, Aachen, Germanymore » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
