Back to Search Start Over

Measuring the complexity of directed graphs

Authors :
Dehmer, Matthias
Chen, Zengqiang
Emmert-Streib, Frank
Tripathi, Shailesh
Mowshowitz, Abbe
Levitchi, Alexei
Feng, Lihua
Shi, Yongtang
Tao, Jin
Upper Austria University of Applied Sciences
Nankai University
Tampere University
City University of New York
Central South University
Robotic Instruments
Department of Electrical Engineering and Automation
Aalto-yliopisto
Aalto University
Publication Year :
2019
Publisher :
PUBLIC LIBRARY SCIENCE, 2019.

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.

Details

Language :
English
Database :
OpenAIRE
Accession number :
edsair.od.......661..9e9105f5166102621cd0750fa563984f