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; Jin Tao

doi:10.1371/journal.pone.0223745

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
, Jin Tao

^*Corresponding author for this work

Upper Austria University of Applied Sciences
Nankai University
UMIT - The Health and Lifesciences University
Tampere University
Institute of Biosciences and Medical Technology
City University of New York
School of Mathematics and Statistics
Aalto University
Peking University

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	e0223745
Journal	PLoS ONE
Volume	14
Issue number	11
DOIs	https://doi.org/10.1371/journal.pone.0223745
Publication status	Published - 1 Nov 2019
Externally published	Yes

Access to Document

10.1371/journal.pone.0223745

Cite this

@article{3f141e97b5c841a88bcba1871d36c495,

title = "Measuring the complexity of directed graphs: A polynomial-based approach",

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.",

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

note = "Publisher Copyright: {\textcopyright} 2019 Dehmer et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.",

year = "2019",

month = nov,

day = "1",

doi = "10.1371/journal.pone.0223745",

language = "English",

volume = "14",

journal = "PLoS ONE",

issn = "1932-6203",

publisher = "Public Library of Science",

number = "11",

}

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

N1 - Publisher Copyright: © 2019 Dehmer et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

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.

UR - https://www.scopus.com/pages/publications/85075058050

U2 - 10.1371/journal.pone.0223745

DO - 10.1371/journal.pone.0223745

M3 - Article

C2 - 31725742

AN - SCOPUS:85075058050

SN - 1932-6203

VL - 14

JO - PLoS ONE

JF - PLoS ONE

IS - 11

M1 - e0223745

ER -

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this