Measuring the complexity of directed graphs: A polynomial-based approach
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
doi:
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:
Directed graphs – Distance measurement – Eigenvalues – Entropy – Game theory – Polynomials – Random graphs – 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;.
Článek vyšel v časopise
PLOS One
2019 Číslo 11
- S diagnostikou Parkinsonovy nemoci může nově pomoci AI nástroj pro hodnocení mrkacího reflexu
- Je libo čepici místo mozkového implantátu?
- Pomůže v budoucnu s triáží na pohotovostech umělá inteligence?
- AI může chirurgům poskytnout cenná data i zpětnou vazbu v reálném čase
- Nová metoda odlišení nádorové tkáně může zpřesnit resekci glioblastomů
Nejčtenější v tomto čísle
- A daily diary study on maladaptive daydreaming, mind wandering, and sleep disturbances: Examining within-person and between-persons relations
- A 3’ UTR SNP rs885863, a cis-eQTL for the circadian gene VIPR2 and lincRNA 689, is associated with opioid addiction
- A substitution mutation in a conserved domain of mammalian acetate-dependent acetyl CoA synthetase 2 results in destabilized protein and impaired HIF-2 signaling
- Molecular validation of clinical Pantoea isolates identified by MALDI-TOF
Zvyšte si kvalifikaci online z pohodlí domova
Všechny kurzy