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

Research output: Contribution to journalArticleScientificpeer-review


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

Research units

  • Upper Austria University of Applied Sciences
  • Nankai University
  • UMIT – Private University for Health Sciences, Medical Informatics and Technology
  • Tampere University
  • City University of New York
  • Central South University
  • Peking University


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.


Original languageEnglish
Article numbere0223745
Number of pages19
JournalPloS one
Issue number11
Publication statusPublished - 14 Nov 2019
MoE publication typeA1 Journal article-refereed

Download statistics

No data available

ID: 39087886