TY - JOUR
T1 - Measuring the complexity of directed graphs
T2 - A polynomial-based approach
AU - Dehmer, Matthias
AU - Chen, Zengqiang
AU - Emmert-Streib, Frank
AU - Tripathi, Shailesh
AU - Mowshowitz, Abbe
AU - Levitchi, Alexei
AU - Feng, Lihua
AU - Shi, Yongtang
AU - Tao, Jin
PY - 2019/11/1
Y1 - 2019/11/1
N2 - 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.
AB - 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.
KW - Computational Biology/statistics & numerical data
KW - Computer Graphics/statistics & numerical data
KW - Computer Simulation
KW - Game Theory
KW - Mathematical Concepts
KW - Systems Biology/statistics & numerical data
UR - http://www.scopus.com/inward/record.url?scp=85075058050&partnerID=8YFLogxK
U2 - 10.1371/journal.pone.0223745
DO - 10.1371/journal.pone.0223745
M3 - Article
C2 - 31725742
AN - SCOPUS:85075058050
SN - 1932-6203
VL - 14
SP - e0223745
JO - PLoS ONE
JF - PLoS ONE
IS - 11
M1 - e0223745
ER -