IDEAS home Printed from https://ideas.repec.org/a/nat/natcom/v8y2017i1d10.1038_ncomms13928.html
   My bibliography  Save this article

Quantification of network structural dissimilarities

Author

Listed:
  • Tiago A. Schieber

    (Engineering School, Universidade Federal de Minas Gerais)

  • Laura Carpi

    (Departament de Física, Universitat Politècnica de Catalunya)

  • Albert Díaz-Guilera

    (Departament de Física Fonamental, Universitat de Barcelona
    Universitat de Barcelona, Institute of Complex Systems (UBICS))

  • Panos M. Pardalos

    (Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611-6595, USA)

  • Cristina Masoller

    (Departament de Física, Universitat Politècnica de Catalunya)

  • Martín G. Ravetti

    (Engineering School, Universidade Federal de Minas Gerais
    Departament de Física Fonamental, Universitat de Barcelona)

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.

Suggested Citation

  • Tiago A. Schieber & Laura Carpi & Albert Díaz-Guilera & Panos M. Pardalos & Cristina Masoller & Martín G. Ravetti, 2017. "Quantification of network structural dissimilarities," Nature Communications, Nature, vol. 8(1), pages 1-10, April.
    • Handle: RePEc:nat:natcom:v:8:y:2017:i:1:d:10.1038_ncomms13928
    DOI: 10.1038/ncomms13928
    as

    Download full text from publisher

    File URL: https://www.nature.com/articles/ncomms13928
    File Function: Abstract
    Download Restriction: no
    File URL: https://libkey.io/10.1038/ncomms13928?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Chen, Gaolin & Zhou, Shuming & Li, Min & Zhang, Hong, 2022. "Evaluation of community vulnerability based on communicability and structural dissimilarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 606(C).
    2. Gao, Cuixia & Tao, Simin & Su, Bin & Mensah, Isaac Adjei & Sun, Mei, 2023. "Exploring renewable energy trade coopetition relationships: Evidence from belt and road countries, 1996-2018," Renewable Energy, Elsevier, vol. 202(C), pages 196-209.
    3. Tofighy, Sajjad & Charkari, Nasrollah Moghadam & Ghaderi, Foad, 2022. "Link prediction in multiplex networks using intralayer probabilistic distance and interlayer co-evolving factors," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 606(C).
    4. Erick Armingol & Hratch M. Baghdassarian & Cameron Martino & Araceli Perez-Lopez & Caitlin Aamodt & Rob Knight & Nathan E. Lewis, 2022. "Context-aware deconvolution of cell–cell communication with Tensor-cell2cell," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    5. Nie, Chun-Xiao, 2022. "Generalized correlation dimension and heterogeneity of network spaces," Chaos, Solitons & Fractals, Elsevier, vol. 162(C).
    6. Wang, Xiaoyan & Tang, Ming & Guan, Shuguang & Zou, Yong, 2023. "Quantifying time series complexity by multi-scale transition network approaches," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 622(C).
    7. Keun-Woo Lee & So-Young Yeo & Jeong-Ryeol Gong & Ok-Jae Koo & Insuk Sohn & Woo Yong Lee & Hee Cheol Kim & Seong Hyeon Yun & Yong Beom Cho & Mi-Ae Choi & Sugyun An & Juhee Kim & Chang Ohk Sung & Kwang-, 2022. "PRRX1 is a master transcription factor of stromal fibroblasts for myofibroblastic lineage progression," Nature Communications, Nature, vol. 13(1), pages 1-23, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:nat:natcom:v:8:y:2017:i:1:d:10.1038_ncomms13928. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.nature.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.