SIG-NET: Exploring the interface between SIGnal processing and NETwork science

Lead Research Organisation: Queen Mary, University of London
Department Name: Sch of Mathematical Sciences

Abstract

The qualitative step forward that Complexity Science has experienced in the last years is directly related to an increase of computation capacity, enabling the possibility of running large scale simulations and handling large amounts of (empirical) data: the so called Big Data paradigm. It is fundamental to come along with new methods and insights to deal, store and extract information from large amounts of data.
These datasets naturally come in two different types. First, from the time evolution of some financial indicator or the irregular motion of turbulent fluids to the waveform signal of speech, complex systems produce incredibly complicated univariate/multivariate time series, whose hidden structure should be processed and analysed using fast and novel approaches. Second, the intertwined architecture of the interaction patterns of complex systems is naturally represented and modeled in terms of graphs -a paradigmatic of this approach being the brain, modeled by single units (neurons) connected by edges that model synaptic connections. These distributed processing systems usually lay at the edge between order and randomness (the so-called complex network paradigm) and come in different flavours (undirected/directed, static/temporal, monolayer/multilayer). Each of these two families of datasets have its own mathematical corpus that deals with the description and characterisation of these data, namely signal processing and network science.

The working hypothesis of this project is that information encoded or hidden in a data set can be retrieved by mapping such data set into an alternative mathematical representation, where the extraction of information may be eventually simpler. As such, we aim to explore what new information can be extracted by mapping time series into graphs and therefore using network science to characterise signals and their underlying dynamics: in short, to make graph-theoretical time series analysis. We are also interested in the dual problem, namely extracting time series from graphs and therefore using the tools of time series analysis and signal processing to describe, compare and classify networks of many kinds: a signal processing of graphs.

We will consider specific methods (visibility algorithms, Markov chain theory, fluctuation analysis) and will be able to define and validate new graph-theoretical measures to describe signals and new signal-theoretic measures to describe graphs, as well as to build a mathematically sound and solid theory to relate these two approaches.

Ultimately, the results of our research will be implemented in a software whose input is a time series/complex network and whose output is a set of key features which describe the object under study from several angles (both the signal processing and graph theoretic angle). These features will then feed automatic classifiers for pattern recognition and data analytics.

Planned Impact

This proposal will have impact on several academic, technological and industrial actors, as well as an impact on UK's societal welfare.

- A dedicated webpage will be hosted by the School of Mathematical Sciences containing the description and findings of the project, serving as a hub to catalyse the transfer of knowledge between academia and industry and to make outreach (via the publication of blog-like summaries of the most relevant research results).

- The school will host of a workshop on nonlinear time series analysis and networks, bringing together time series analysis practitioners, UK national and international scientists working on nonlinear time series analysis and data mining, and UK interested industrial partners.

Specific impact is expected at four levels:

(i) Fostering Interdisciplinarity in academia:
The research agenda on visibility algorithms is currently having a large impact in different scientific fields beyond applied mathematicians or theoretical physicists, including neuroscience, physiology, socio-economics, computer science, or applied physics, to cite some. We pretend to consolidate such impact within this project by both providing mathematical rigour to the method (WP1), by widening its spectrum of features (WP2) and by validating it in realistic scenarios of data classification (WP3).

(ii) Impact on clinical and biomedical realm:
An aspect of particular importance is the possibility of developing, as an outcome of the research involving analysis and classification of physiological time series, non-invasive diagnosis & clinical tests. Previous research on visibility algorithms suggest that this application is realistic and specific case tests will be addressed within WP3, in the context of implementing our feature based extraction and classification tool and validating in classification of cardiac diseases and cancer phenotypes. We have an ongoing collaboration with the Cancer Institute (Statistical Cancer Genomics Group) at UCL, which we plan to strengthen also within WP3 of this project.

(iii) Impact on software and telecommunication sectors:
We will collaborate (WP3) with Dr. Jordi Luque from Telefonica R&D (who is a partner in this fellowship) in validating the visibility network features for speaker recognition, mood and personality traits detection, these being classification problems of genuine research and long-term commercial interest for Telefonica, as expressed in their statement of support.

(iv) Societal welfare:
The ultimate beneficiary is UK society, whose welfare shall be increased as a consequence of the development of new tools for data analysis, as these have a direct impact in societal challenges such as healthcare or economic resilience, as acknowledged in the case for support. We will also use the webpage to make scientific outreach, making press releases and publishing non technical papers on the blog section of the site, much in the spirit of the Systems and Signals group blog at Imperial College London (http://systems-signals.blogspot.co.uk). Note that the PI belongs to the School's outreach committee, and has an independent track record of publishing scientific results in popular media such as newspapers, science magazines, and science websites. Furthermore, previous steps of this research have received press coverage in French magazine "La recherche" or in the popular "IEEE circuits and systems magazine".

Publications

10 25 50
publication icon
Amato R (2018) The dynamics of norm change in the cultural evolution of language. in Proceedings of the National Academy of Sciences of the United States of America

publication icon
Ballesteros FJ (2018) On the thermodynamic origin of metabolic scaling. in Scientific reports

publication icon
Bonaventura M (2020) Predicting success in the worldwide start-up network. in Scientific reports

publication icon
Challen R (2021) Estimates of regional infectivity of COVID-19 in the United Kingdom following imposition of social distancing measures. in Philosophical transactions of the Royal Society of London. Series B, Biological sciences

publication icon
Danon L (2021) Household bubbles and COVID-19 transmission: insights from percolation theory. in Philosophical transactions of the Royal Society of London. Series B, Biological sciences

publication icon
Flanagan R (2020) On the spectral properties of Feigenbaum graphs in Journal of Physics A: Mathematical and Theoretical

publication icon
González-Espinoza A (2020) Arrow of time across five centuries of classical music in Physical Review Research

 
Description On direct relation to specific objectives of the project and to the general topic of the fellowship (interface between time series analysis and network science), the results obtained so far have been published in 20 papers, including:

(i) A paper (published in Physica D) on the relation between visibility graphs and symbolic dynamics. In this paper we found that the visibility graph is effectively making an adaptive partition of the phase space, and thus sets a link between visibility graphs and symbolic dynamics.

(ii) A paper showcasing the applicability of visibility graphs to integer sequences has been published in Journal of Physics A. We found that previous analytical results know for real-valued time series do not apply for integer-valued time series, and thus application of these methods to genuinely integer-valued series should be treated differently.

(iii) In collaboration with Ghent University, a paper applying the multivariate extension of visibility algorithms to functional magnetic resonance imaging (fmri) time series has been published in Network Neuroscience, highlighting the usefulness of these methods in neuroscience, and showcasing that features extracted from multiplex visibility graphs can be used to classify mental diseases from fmri data, such as the distinction between patients with schizophrenia from healthy controls.

(iv,v) A paper extending the visibility algorithms to deal with spatial data has been published in Physical Review E, and a paper on the applications of these for image processing has been recently accepted for publication in IEEE Transactions in Pattern Analysis and Machine Intelligence (TPAMI).

(vi, vii) Two papers investigating the motif structure of visibility graphs have been published in Physical Review E. In these papers we obtain analytical formulas for the motif abundance associated to several canonical dynamical processes. Using motif profiles as a feature for time series classification has been demonstrated to be a useful approach. Recently, a collaboration with the AI-based company Tooso (San Francisco, US) has been set to explore the applicability of visibility graphs for time series classification in the context of user intent prediction in e-commerce. A paper has been published in a workshop of the prestigious conference KDD.

(viii) In collaboration with researchers from University of Trento (Italy), a paper exploring the asymmetry between top and bottom visibility graphs has been accepted for publication in Scientific Reports. In that paper we show that exploiting the difference between top and bottom visibility graphs reveals hidden information on the associated time series.

(ix) In collaboration with researchers from several universities (Spain, UK, Germany) a paper exploring the use of Markov Chains to unfold multiplex structures has been published in Physical Review X. In that paper we show how to unfold a multiplex network of several layers if we only have access to the projection of such network in the aggregated network.

(x) A paper on the spectral properties of a class of visibility graphs has been published in Journal of Physics A.

(xi) A total of four additional papers have been published in high profile journals (including two papers in PNAS and a paper in Nature Communications) on topics closely related to the proposal although not specifically stated as concrete milestones.
Exploitation Route The extensions of visibility algorithms to both multivariate time series and spatial data enable the definition of new features, to be used in statistical learning as applied to signal and image recognition problems.
Sectors Digital/Communication/Information Technologies (including Software),Financial Services, and Management Consultancy,Pharmaceuticals and Medical Biotechnology,Retail,Transport,Other

URL http://www.maths.qmul.ac.uk/~lacasa/main.html
 
Description The application of some of the techniques investigated in this project (namely, visibility graph motifs) have been successfully used in the task of user intent prediction in e-commerce, in a joint collaboration with AI-tech Silicon Valley company Tooso, recently acquired by Coveo. https://towardsdatascience.com/to-buy-or-not-to-buy-that-is-the-question-3a4d99330dcc These results, and my collaboration with Tooso, form the basis of an impact case that QMUL will submit in the next REF (2021).
First Year Of Impact 2018
Sector Retail
Impact Types Economic

 
Description During 2020 I participated in an advisory committee that gave guidance to the Spanish Secretary of state of digitialisation in the rollout and deployment of the spanish contact tracing app RadarCOVID
Geographic Reach Europe 
Policy Influence Type Participation in a advisory committee
Impact During 2020 I participated in an advisory committee that gave guidance to the Spanish Secretary of state of digitialisation in the rollout and deployment of the spanish contact tracing app RadarCOVID. The app has been downloaded over 7 million times in Spain. The results of an experimental pilot assessing its validity that was conducted in the Canary Islands have been published in Nature Communications, and I am the corresponding author.
URL https://radarcovid.gob.es/
 
Description EPSRC Complexity Science long-term funding strategy review panel
Geographic Reach National 
Policy Influence Type Participation in a advisory committee
 
Description EPSRC Complexity Science review panel 
Form Of Engagement Activity A formal working group, expert panel or dialogue
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Professional Practitioners
Results and Impact I was invited to attend the kick-off meeting for a review panel at EPSRC. The purpose of this panel is to review the medium and long-term funding strategy that EPSRC puts into the broad research area of Complexity Science. A total of about 15 experts in the are were called upon to attend this meeting from several UK universities.
Year(s) Of Engagement Activity 2017
 
Description Invited talk 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Invited talk at Technical University of Madrid (Madrid, Spain) January 2018
Year(s) Of Engagement Activity 2018
 
Description Invited talk 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Invited talk at Alephsys lab (University Rovira I Virgili, Tarragona, Spain) January 2018
Year(s) Of Engagement Activity 2018
 
Description Invited talk 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Invited talk at the Maths Department, University of California Los Angeles (UCLA), California, US, on July 2017.
Year(s) Of Engagement Activity 2017
 
Description Opinion Piece published in "The Conversation" 
Form Of Engagement Activity A magazine, newsletter or online publication
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Media (as a channel to the public)
Results and Impact Wrote an article for "The Conversation"
https://theconversation.com/las-multitudes-suenan-afinadas-incluso-si-todos-sus-miembros-desentonan-101912?utm_source=facebook&utm_medium=facebookbutton

I have been nominated for a QMUL Engagement Award for this opinion piece.
Year(s) Of Engagement Activity 2018
URL https://theconversation.com/las-multitudes-suenan-afinadas-incluso-si-todos-sus-miembros-desentonan-...
 
Description Press release 
Form Of Engagement Activity A press release, press conference or response to a media enquiry/interview
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Media (as a channel to the public)
Results and Impact Press release by Technical University of Madrid of a publication: Emergence of linguistic laws in human voice
Ivan Gonzalez Torre, Bartolo Luque, Lucas Lacasa, Jordi Luque and Antoni Hernandez-Fernandez
Nature Scientific Reports 7, 43862 (2017)
Featured in Research News Portal, Technical University of Madrid
Year(s) Of Engagement Activity 2017
URL http://www.upm.es/UPM/SalaPrensa/Noticias_de_investigacion?id=eabb1997a4b3d510VgnVCM10000009c7648a__...
 
Description Press release and media interviews of three papers published in 2020 
Form Of Engagement Activity A press release, press conference or response to a media enquiry/interview
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Media (as a channel to the public)
Results and Impact Three of my 2020-2021 publications (papers published in Nature Communications, Physical Review Research, and PLoS ONE) have received wide media attention. A press release was produced for these papers which had echo in other media outlets. I also made specific interviews for Scientific American and Nature News on relation to these.
Year(s) Of Engagement Activity 2020
 
Description Press release and several features in popular press. 
Form Of Engagement Activity A press release, press conference or response to a media enquiry/interview
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Press release (and several subsequent feature articles, including radio interview) on relation to the publication of the paper: On the thermodynamic origin of metabolic scaling
Fernando Ballesteros, Vicent Martinez, Bartolo Luque, Lucas Lacasa, Enric Valor and Andres Moya
Nature Scientific Reports 8, 1448 (2018)
Year(s) Of Engagement Activity 2018
URL https://www.uv.es/institute-integrative-systems-biology-i2sysbio/en/novetats-1285990801509/Novetat.h...
 
Description Press release of a paper 
Form Of Engagement Activity A press release, press conference or response to a media enquiry/interview
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Media (as a channel to the public)
Results and Impact Press release (and several subsequent feature articles) on relation to the publication of the paper:
The dynamics of norm change in the cultural evolution of language.
Roberta Amato, Lucas Lacasa, Albert Diaz-Guilera, Andrea Baronchelli
PNAS 115, 33 (2018)
Year(s) Of Engagement Activity 2019
URL https://www.city.ac.uk/news/2018/august/city-lecturer-uncovers-the-mechanisms-of-norm-changes-by-ana...
 
Description Seminar at IFISC (Institute for cross-disciplinary physics and complex systems, Spain) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Seminar
Year(s) Of Engagement Activity 2019
 
Description Several research seminars and talks in the UK and abroad 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact In 2018 I delivered the following research seminars and invited talks at conferences:
- Imperial College London(UK)
Complexity Seminar
Seminar title: New Methods for Complex Systems (Apr 2018)

- University of Bristol (UK)
Workshop in Network Science
Invited Talk: Identifying hidden layers in networksInvited speaker at UK Workshop in Network Science (May 2018)

- Higher-Order Models in Network Science (NETSCI 2018 Satellite, France)
Talk: Identifying hidden layers in networks (June 2018) [Invited speaker]

- Instituto de Fisica de Cantabria IFCA (Spain) Institute's Colloqium
Seminar title: Visibility graphs (Jun 2018)

- Universidad Carlos III de Madrid UC3M (Spain)
Department of Signal Theory & Communications
Seminar title: Visibility graphs (Jun 2018)

- University of Loughborough(UK)
Department of Mathematics
Seminar title: Visibility graphs (Oct 2018)

- Kings College London (UK)
CANES Centre for Doctoral Training
Seminar title: Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstructionproblem (Dec 2018)

- Queen Mary University of London(UK)
School of Mathematical Sciences
Seminar title: Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstructionproblem (Jan 2019)
Year(s) Of Engagement Activity 2018
 
Description Talk at Fellowship Forum Presentation 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Regional
Primary Audience Postgraduate students
Results and Impact Talk at the Fellowship Forum Presentation (QMUL), where I presented a summary of the objectives and results of my EPSRC fellowship in front of a selected number of speakers including Prof. Didier Queloz, Nobel Prize in Physics
Year(s) Of Engagement Activity 2020
 
Description Talk at UBICS Complex Systems and Covid colloquium 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Online UBICS Complex Systems and Covid colloqium.
Year(s) Of Engagement Activity 2020
 
Description Talks in national and international conferences 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact - UK Workshop in Network Science | Bristol, UK 2018
Talk title:Identifying the hidden multiplex structure of complex systems

- Netsci 2018 (Satellite) | Paris, France 2018
Talk title:Identifying the hidden multiplex structure of complex systems

- International Conference on Complex Networks | Cambridge, UK 2018
Talk title:Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem

- Complenet 19 | Tarragona, Spain 2019
Talk title:Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
Year(s) Of Engagement Activity 2018
 
Description talk at Zenith (London) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Industry/Business
Results and Impact Seminar at Zenith, fostering impact.
Year(s) Of Engagement Activity 2019