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

English version

Autoři: Matthias Dehmer ^aff001; Zengqiang Chen ^aff002; Frank Emmert-Streib ^aff004; Shailesh Tripathi ^aff001; Abbe Mowshowitz ^aff006; Alexei Levitchi ^aff001; Lihua Feng ^aff007; Yongtang Shi ^aff008; Jin Tao ^aff009
Působiště autorů: Institute for Intelligent Production, Faculty for Management, University of Applied Sciences Upper Austria, Steyr, Austria ^aff001; College of Artificial Intelligence, Nankai University, Tianjin, China ^aff002; Department of Biomedical Computer Science and Mechatronics, UMIT - The Health and Lifesciences University, A-6060 Hall in Tyrol, Austria ^aff003; Predictive Medicine and Data Analytics Lab, Department of Signal Processing, Tampere University, Tampere, Finland ^aff004; Institute of Biosciences and Medical Technology, Tampere, Finland ^aff005; Department of Computer Science, The City College of New York (CUNY), 138th Street at Convent Avenue, New York, United States of America ^aff006; School of Mathematics and Statistics, Central South University, Changsha, China ^aff007; Center for Combinatorics and LPMC, Nankai University, Tianjin, China ^aff008; Department of Electrical Engineering and Automation, Aalto University, Espoo, Finland ^aff009; College of Engineering, Peking University, Beijing, China ^aff010
Vyšlo v časopise: PLoS ONE 14(11)
Kategorie: Research Article
prolekare.web.journal.doi_sk: https://doi.org/10.1371/journal.pone.0223745

Souhrn

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.

Klíčová slova:

Eigenvalues – Polynomials – Entropy – Directed graphs – Distance measurement – Random graphs – Game theory – Real numbers

Zdroje

1. Bang-Jensen J, Gutin G. Digraphs: Theory, Algorithms and Applications. 1st ed. Springer-Verlag; 2007.

2. Gruber H. Digraph complexity measures and applications in formal language theory. Discrete Mathematics & Theoretical Computer Science. 2012;14:189–204.

3. Obdržálek J. DAG-width—connectivity measure for directed graphs. Symposium on Discrete Algorithms, ACM-SIAM. 2006; p. 814–821.

4. Todeschini R, Consonni V. Handbook of Molecular Descriptors. Wiley-VCH; 2002.

5. Rodrigue JP, Comtois C, Slack B. The Geography of Transport Systems. Taylor & Francis; 2013.

6. Junker BH, Schreiber F. Analysis of Biological Networks. Wiley Series in Bioinformatics. Wiley-Interscience; 2008.

7. Emmert-Streib F, Dehmer M. Networks for Systems Biology: Conceptual Connection of Data and Function. IET Systems Biology. 2011;5:185–207. doi: 10.1049/iet-syb.2010.0025 21639592

8. Wiener H. Structural Determination of Paraffin Boiling Points. Journal of the American Chemical Society. 1947;69(17):17–20. doi: 10.1021/ja01193a005 20291038

9. Mowshowitz A. Entropy and the complexity of graphs: I. An index of the relative complexity of a graph. Bulletin of Mathematical Biophysics. 1968;30:175–204. doi: 10.1007/bf02476948 5666816

10. Knor M, Skrekovski R, Tepeh A. Some remarks on Wiener index of oriented graphs. Applied Mathematics and Computation. 2016;273:631–636. doi: 10.1016/j.amc.2015.10.033

11. Klavžar S, Rajapakse A, Gutman I. The Szeged and the Wiener index of graphs. Applied Mathematics Letters. 1996;9(5):45–49. doi: 10.1016/0893-9659(96)00071-7

12. Harary F. Structural models. An introduction to the theory of directed graphs. Wiley; 1965.

13. Johnson T, Robertson N, Seymour PD, Thomas R. Directed tree-width. Journal of Combinatorial Theory, Series B. 2001;82:138–154. doi: 10.1006/jctb.2000.2031

14. Bertz SH, Pereira GZ, Zamfirescu CMD. Complexity and Diversity of Digraphs. In: Minai AA, Braha D, Bar-Yam Y, editors. Unifying Themes in Complex Systems. Springer; 2011. p. 31–40.

15. Hunter P, Kreutzer S. Digraph measures: Kelly decompositions, games, and orderings. Theoretical Computer Science. 2008;399:206–219. doi: 10.1016/j.tcs.2008.02.038

16. Berwanger D, Grädel E. Entanglement—A Measure for the Complexity of Directed Graphs with Applications to Logic and Games. In: Proceedings of LPAR 2004, Montevideo, Uruguay. vol. 3452 of LNCS. Springer-Verlag; 2005. p. 209–223.

17. Estrada E, Hatano N. Returnability in complex directed networks (digraphs). Discrete Mathematics & Theoretical Computer Science. 2009;430:1886–1896.

18. Ye C, Wilson RC, Comin CH, da F Costa L, Hancock ER. Entropy and Heterogeneity Measures for Directed Graphs. In: Hancock E, Pelillo M, editors. Similarity-Based Pattern Recognition. SIMBAD 2013. Lecture Notes in Computer Science. vol. 7953. Springer; 2013. p. 219–234.

19. Dehmer M, Emmert-Streib F. Quantitative Graph Theory. Theory and Applications. CRC Press; 2014.

20. Emmert-Streib F, Dehmer M, Shi Y. Fifty years of graph matching, network alignment and network comparison. Information Sciences. 2016;346-347:180–197. doi: 10.1016/j.ins.2016.01.074

21. Harary F. Graph Theory. Addison Wesley Publishing Company; 1969.

22. Marden M. Geometry of Polynomials. 2nd ed. American Mathematical Society; 1966.

23. Weber H. Lehrbuch der Algebra, Vol. 1; 1895.

24. Dehmer M, Shi Y, Mowshowitz A. Discrimination power of graph measures based on complex zeros of the partial Hosoya polynomial. Applied Mathematics and Computation. 2015;250:352–355. doi: 10.1016/j.amc.2014.10.048

25. Dehmer M, Moosbrugger M, Shi Y. Encoding structural information uniquely with polynomial-based descriptors by employing the Randić matrix. Applied Mathematics and Computation. 2015;268:164–168. doi: 10.1016/j.amc.2015.04.115

26. Konstantinova EV. The Discrimination Ability of Some Topological and Information Distance Indices for Graphs of Unbranched Hexagonal Systems. J Chem Inf Comput Sci. 1996;36:54–57. doi: 10.1021/ci9502461

27. da F Costa L, Rodrigues F, Travieso G. Characterization of complex networks: A survey of measurements. Advances in Physics. 2007;56:167–242. doi: 10.1080/00018730601170527

28. R Core Team. R: A Language and Environment for Statistical Computing; 2018. Available from: https://www.R-project.org/.

29. Csardi G, Nepusz T. The igraph software package for complex network research. InterJournal. 2006;Complex Systems:1695.

30. Gentleman R, Whalen E, Huber W, Falcon S. graph: A package to handle graph data structures; 2017.

31. Mueller LAJ, Kugler KG, Dander A, Graber A, Dehmer M. QuACN: An R package for analyzing complex biological networks quantitatively. Bioinformatics. 2011;27:140–141. doi: 10.1093/bioinformatics/btq606 21075747

32. Erdős P, Rényi A. On random graphs. Publicationes Mathematicae. 1959;6:290–297.

33. Dehmer M, Emmert-Streib F. Structural similarity of directed universal hierarchical graphs: A low computational complexity approach. Applied Mathematics and Computation. 2007;194:7–20. doi: 10.1016/j.amc.2007.04.006

34. Hopp WJ, Spearman ML, Physics F. Foundations of Manufacturing Management. New York: Irwin; 2011.

35. Ptak C, Smith C. Orlicky’s Material Requirements Planning 3/E. McGraw-Hill’s AccessEngineering. Mcgraw-hill; 2011. Available from: https://books.google.at/books?id=CMKNhCdROt4C.

36. Bonchev D. Information Theoretic Indices for Characterization of Chemical Structures. Research Studies Press, Chichester; 1983.

37. Dehmer M, Chen Z, Emmert-Streib F, Mowshowitz A, Varmuza K, Jodlbauer H, et al. The Orbit-polynomial: A novel Measure of Symmetry in Graphs. submitted for publication. 2019;.

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

Souhrn

Klíčová slova:

Zdroje

PLOS One

Aktuální možnosti diagnostiky a léčby litiáz