12
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Quantification of network structural dissimilarities

      research-article

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Identifying and quantifying dissimilarities among graphs is a fundamental and challenging problem of practical importance in many fields of science. Current methods of network comparison are limited to extract only partial information or are computationally very demanding. Here we propose an efficient and precise measure for network comparison, which is based on quantifying differences among distance probability distributions extracted from the networks. Extensive experiments on synthetic and real-world networks show that this measure returns non-zero values only when the graphs are non-isomorphic. Most importantly, the measure proposed here can identify and quantify structural topological differences that have a practical impact on the information flow through the network, such as the presence or absence of critical links that connect or disconnect connected components.

          Abstract

          Identifying and quantifying dissimilarities among graphs is a problem of practical importance, but current approaches are either limited or computationally demanding. Here, the authors propose an efficiently computable measure for network comparison that can identify structural topological differences.

          Related collections

          Most cited references11

          • Record: found
          • Abstract: found
          • Article: found
          Is Open Access

          Specificity and stability in topology of protein networks

          Molecular networks guide the biochemistry of a living cell on multiple levels: its metabolic and signalling pathways are shaped by the network of interacting proteins, whose production, in turn, is controlled by the genetic regulatory network. To address topological properties of these two networks we quantify correlations between connectivities of interacting nodes and compare them to a null model of a network, in which al links were randomly rewired. We find that for both interaction and regulatory networks, links between highly connected proteins are systematically suppressed, while those between a highly-connected and low-connected pairs of proteins are favored. This effect decreases the likelihood of cross talk between different functional modules of the cell, and increases the overall robustness of a network by localizing effects of deleterious perturbations.
            Bookmark
            • Record: found
            • Abstract: found
            • Article: not found

            Biological network comparison using graphlet degree distribution.

            Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics, such as the degree distribution, clustering coefficient, diameter, and relative graphlet frequency distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in all of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar. We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes 'touching' k edges, into distributions measuring the number of nodes 'touching' k graphlets, where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 graphlet degree distributions of graphlets with 2-5 nodes, but it is easily extendible to a greater number of constraints (i.e. graphlets), if necessary, and the extensions are limited only by the available CPU. Furthermore, we show a way to combine the 73 graphlet degree distributions into a network 'agreement' measure which is a number between 0 and 1, where 1 means that networks have identical distributions and 0 means that they are far apart. Based on this new network agreement measure, we show that almost all of the 14 eukaryotic PPI networks, including human, resulting from various high-throughput experimental techniques, as well as from curated databases, are better modeled by geometric random graphs than by Erdös-Rény, random scale-free, or Barabási-Albert scale-free networks. Software executables are available upon request.
              Bookmark
              • Record: found
              • Abstract: found
              • Article: not found

              Structural reducibility of multilayer networks.

              Many complex systems can be represented as networks consisting of distinct types of interactions, which can be categorized as links belonging to different layers. For example, a good description of the full protein-protein interactome requires, for some organisms, up to seven distinct network layers, accounting for different genetic and physical interactions, each containing thousands of protein-protein relationships. A fundamental open question is then how many layers are indeed necessary to accurately represent the structure of a multilayered complex system. Here we introduce a method based on quantum theory to reduce the number of layers to a minimum while maximizing the distinguishability between the multilayer network and the corresponding aggregated graph. We validate our approach on synthetic benchmarks and we show that the number of informative layers in some real multilayer networks of protein-genetic interactions, social, economical and transportation systems can be reduced by up to 75%.
                Bookmark

                Author and article information

                Journal
                Nat Commun
                Nat Commun
                Nature Communications
                Nature Publishing Group
                2041-1723
                09 January 2017
                2017
                : 8
                : 13928
                Affiliations
                [1 ]Departmento de Engenharia de Produção, Engineering School, Universidade Federal de Minas Gerais , Avenida Antonio Carlos 6627, Belo Horizonte 31.270-901, Brazil
                [2 ]Departament de Física, Universitat Politècnica de Catalunya , 08222 Terrassa, Spain
                [3 ]Departament de Física Fonamental, Universitat de Barcelona , 08028 Barcelona, Spain
                [4 ]Universitat de Barcelona, Institute of Complex Systems (UBICS) , 08028 Barcelona, Spain
                [5 ]Industrial and Systems Engineering, University of Florida , Gainesville, Florida 32611-6595, USA
                Author notes
                Article
                ncomms13928
                10.1038/ncomms13928
                5227707
                28067266
                b13273ca-4e0b-40fa-a310-6e646bcccb82
                Copyright © 2017, The Author(s)

                This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the article's Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

                History
                : 26 May 2016
                : 15 November 2016
                Categories
                Article

                Uncategorized
                Uncategorized

                Comments

                Comment on this article