From graphs to signals and back: Identification of network structures using spectral analysis
arXiv:1502.04697
Abstract
Many systems comprising entities in interactions can be represented as graphs, whose structure gives significant insights about how these systems work. Network theory has undergone further developments, in particular in relation to detection of communities in graphs, to catch this structure. Recently, an approach has been proposed to transform a graph into a collection of signals: Using a multidimensional scaling technique on a distance matrix representing relations between vertices of the graph, points in a Euclidean space are obtained and interpreted as signals, indexed by the vertices. In this article, we propose several extensions to this approach, developing a framework to study graph structures using signal processing tools. We first extend the current methodology, enabling us to highlight connections between properties of signals and graph structures, such as communities, regularity or randomness, as well as combinations of those. A robust inverse transformation method is next described, taking into account possible changes in the signals compared to original ones. This technique uses, in addition to the relationships between the points in the Euclidean space, the energy of each signal, coding the different scales of the graph structure. These contributions open up new perspectives in the study of graphs, by enabling processing of graphs through the processing of the corresponding collection of signals, using reliable tools from signal processing. A technique of denoising of a graph by filtering of the corresponding signals is then described, suggesting considerable potential of the approach.
References in corpus (7)
- Stochastic blockmodels and community structure in networks
- Signals on Graphs: Uncertainty Principle and Sampling
- Sampling of graph signals with successive local aggregations
- Analytical framework for recurrence-network analysis of time series
- Discovering the structure of complex networks by minimizing cyclic bandwidth sum
- Toward An Uncertainty Principle For Weighted Graphs
- A Probabilistic Interpretation of Sampling Theory of Graph Signals