Measuring the complexity of directed graphs: A polynomial-based approach

Matthias Dehmer, Zengqiang Chen, Frank Emmert-Streib, Shailesh Tripathi, Abbe Mowshowitz, Alexei Levitchi, Lihua Feng, Yongtang Shi and Jin Tao

PLOS ONE, 2019, vol. 14, issue 11, 1-19

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.

Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0223745 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 23745&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0223745

DOI: 10.1371/journal.pone.0223745

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().