We use cookies to help us improve this website. Learn more

Skip to main content
  • Other Publications
    • Philosophical Transactions B
    • Proceedings B
    • Biology Letters
    • Open Biology
    • Philosophical Transactions A
    • Proceedings A
    • Royal Society Open Science
    • Interface
    • Interface Focus
    • Notes and Records
    • Biographical Memoirs

Advanced

  • Home
  • Content
    • Latest issue
    • All content
    • Subject collections
    • Podcasts
  • Information for
    • Authors
    • Reviewers
    • Readers
    • Institutions
    • The media
  • About us
    • About the journal
    • Editorial board
    • Author benefits
    • Policies
    • Citation metrics
    • Publication times
    • Open access
  • Sign up
    • Subscribe
    • eTOC alerts
    • Keyword alerts
    • RSS feeds
    • Newsletters
  • Submit
You have accessRestricted access

Fundamental limitations of network reconstruction from temporal data

Marco Tulio Angulo, Jaime A. Moreno, Gabor Lippner, Albert-László Barabási, Yang-Yu Liu
Published 1 February 2017.DOI: 10.1098/rsif.2016.0966
Marco Tulio Angulo
Institute of Mathematics, Universidad Nacional Autónoma de México, Juriquilla 76230, México
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
  • ORCID record for Marco Tulio Angulo
Jaime A. Moreno
Institute of Engineering, Universidad Nacional Autónoma de México, CdMx 04510, México
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
Gabor Lippner
Department of Mathematics, Northeastern University, Boston MA 02115, USA
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
Albert-László Barabási
Center for Complex Networks Research, Northeastern University, Boston MA 02115, USACenter for Cancer Systems Biology, Dana-Farber Cancer Institute, Boston, MA 02115, USACenter for Network Science, Central European University, Budapest 1052, Hungary
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
Yang-Yu Liu
Center for Cancer Systems Biology, Dana-Farber Cancer Institute, Boston, MA 02115, USAChanning Division of Network Medicine, Brigham and Women's Hospital, Boston, MA 02115, USAHarvard Medical School, Boston, MA 02115, USA
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
  • ORCID record for Yang-Yu Liu
  • Article
  • Figures & Data
  • Info & Metrics
  • eLetters
  • PDF
Loading

Abstract

Inferring properties of the interaction matrix that characterizes how nodes in a networked system directly interact with each other is a well-known network reconstruction problem. Despite a decade of extensive studies, network reconstruction remains an outstanding challenge. The fundamental limitations governing which properties of the interaction matrix (e.g. adjacency pattern, sign pattern or degree sequence) can be inferred from given temporal data of individual nodes remain unknown. Here, we rigorously derive the necessary conditions to reconstruct any property of the interaction matrix. Counterintuitively, we find that reconstructing any property of the interaction matrix is generically as difficult as reconstructing the interaction matrix itself, requiring equally informative temporal data. Revealing these fundamental limitations sheds light on the design of better network reconstruction algorithms that offer practical improvements over existing methods.

Footnotes

  • Electronic supplementary material is available online at https://dx.doi.org/10.6084/m9.figshare.c.3672004.

  • Received November 30, 2016.
  • Accepted January 3, 2017.
  • © 2017 The Author(s)
http://royalsocietypublishing.org/licence

Published by the Royal Society. All rights reserved.

View Full Text
PreviousNext
Back to top
PreviousNext
February 2017
Volume 14
, issue 127
Journal of The Royal Society Interface: 14 (127)
  • Table of Contents
  • About the Cover
  • Index by author
  • Ed Board (PDF)

Keywords

network reconstruction
system identification
networked systems
Share
Fundamental limitations of network reconstruction from temporal data
Marco Tulio Angulo, Jaime A. Moreno, Gabor Lippner, Albert-László Barabási, Yang-Yu Liu
J. R. Soc. Interface 2017 14 20160966; DOI: 10.1098/rsif.2016.0966. Published 1 February 2017
Permalink:
del.icio.us logo Digg logo Reddit logo Twitter logo CiteULike logo Connotea logo Facebook logo Google logo Mendeley logo
Email
Print
Manage alerts
Citation tools
Download
Request Permissions

Article reuse

  • Article
    • Abstract
    • 1. Introduction
    • Authors' contributions
    • Funding
    • Acknowledgements
    • Footnotes
    • References
  • Figures & Data
  • Info & Metrics
  • eLetters
  • PDF

See related subject areas:

  • bioinformatics
  • computational biology
  • systems biology

Related articles

  • No related articles found
  • PubMed
  • Google Scholar

Cited by

  • No citing articles found.
  • Google Scholar

Interface Focus To read similar articles, check out our sister journal

Recommended articles

  1. Inferring social network structure in ecological systems from spatio-temporal data streams.
    Ioannis Psorakis et al., Interface , 2012
  2. Form and function in gene regulatory networks: the structure of network motifs determines fundamental properties of their dynamical state space.
    S E Ahnert et al., Interface , 2016
  3. Spatio-temporal networks: reachability, centrality and robustness
    Matthew J. Williams et al., Royal Soc Open Sci , 2016
  4. Data-based reconstruction of complex geospatial networks, nodal positioning and detection of hidden nodes
    Ying-Cheng Lai et al., Royal Soc Open Sci , 2016

 

  1. Structural principles within the human-virus protein-protein interaction network.
    Eric A Franzosa et al., Proc Natl Acad Sci U S A , 2011
  2. Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences.
    Lauri Kovanen et al., Proc Natl Acad Sci U S A , 2013
  3. Double dissociation of two cognitive control networks in patients with focal brain lesions.
    Emi M Nomura et al., Proc Natl Acad Sci U S A , 2010
  4. Holistic Atlases of Functional Networks and Interactions Reveal Reciprocal Organizational Architecture of Cortical Function
    EMBS Trans Biomed Eng , 2015
Powered by TrendMD

Open biology

  • Interface
    • About this journal
    • Contact information
    • Purchasing information
    • Submit
    • Author benefits
    • Open access membership
    • Recommend to your library
    • FAQ
    • Help

Royal society publishing

  • ROYAL SOCIETY PUBLISHING
    • Our journals
    • Open access
    • Publishing policies
    • Conferences
    • Podcasts
    • News
    • Blog
    • Manage your account
    • Terms & conditions
    • Cookies

The royal society

  • THE ROYAL SOCIETY
    • About us
    • Contact us
    • Fellows
    • Events
    • Grants, schemes & awards
    • Topics & policy
    • Collections
    • Venue hire
1742-5662

Copyright © 2017 The Royal Society

 

Thank you for your interest in spreading the word on Journal of The Royal Society Interface.

NOTE: We only request your email address so that the person you are recommending the page to knows that you wanted them to see it, and that it is not junk mail. We do not capture any email address.

Enter multiple addresses on separate lines or separate them with commas.
Fundamental limitations of network reconstruction from temporal data
(Your Name) has sent you a message from Journal of The Royal Society Interface
(Your Name) thought you would like to see the Journal of The Royal Society Interface web site.
 

Please log in to add an alert for this article.

Sign In to Email Alerts with your Email Address
Citation tools
Research:

Fundamental limitations of network reconstruction from temporal data

Marco Tulio Angulo, Jaime A. Moreno, Gabor Lippner, Albert-László Barabási, Yang-Yu Liu
J. R. Soc. Interface 2017 14 20160966; DOI: 10.1098/rsif.2016.0966. Published 1 February 2017

Citation Manager Formats

  • BibTeX
  • Bookends
  • EasyBib
  • EndNote (tagged)
  • EndNote 8 (xml)
  • Medlars
  • Mendeley
  • Papers
  • RefWorks Tagged
  • Ref Manager
  • RIS
  • Zotero

Sign up Successful

Welcome to colwiz. An activation email has been sent. To get back into your account, follow the instructions we\'ve sent to you.