Measuring the complexity of directed graphs: A polynomial-based approach
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2019-11-14
Major/Subject
Mcode
Degree programme
Language
en
Pages
19
Series
PloS one, Volume 14, issue 11
Abstract
In this paper, we define novel graph measures for directed networks. The measures are based on graph polynomials utilizing the out- and in-degrees of directed graphs. Based on these polynomial, we define another polynomial and use their positive zeros as graph measures. The measures have meaningful properties that we investigate based on analytical and numerical results. As the computational complexity to compute the measures is polynomial, our approach is efficient and can be applied to large networks. We emphasize that our approach clearly complements the literature in this field as, to the best of our knowledge, existing complexity measures for directed graphs have never been applied on a large scale.Description
Keywords
Other note
Citation
Dehmer, M, Chen, Z, Emmert-Streib, F, Tripathi, S, Mowshowitz, A, Levitchi, A, Feng, L, Shi, Y & Tao, J 2019, ' Measuring the complexity of directed graphs : A polynomial-based approach ', PloS one, vol. 14, no. 11, e0223745 . https://doi.org/10.1371/journal.pone.0223745