Towards detecting structural branching and cyclicity in graphs: A polynomial-based approach

Matthias Dehmer; Zengqiang Chen; Frank Emmert-Streib; Abbe Mowshowitz; Yongtang Shi; Shailesh Tripathi; Yusen Zhang

doi:10.1016/j.ins.2018.08.043

Towards detecting structural branching and cyclicity in graphs: A polynomial-based approach

Matthias Dehmer, Zengqiang Chen, Frank Emmert-Streib, Abbe Mowshowitz, Yongtang Shi, Shailesh Tripathi, Yusen Zhang

Tutkimustuotos: Artikkeli › Tieteellinen › vertaisarvioitu

8 Sitaatiot (Scopus)

Abstrakti

Structural properties of graphs and networks have been investigated across scientific disciplines ranging from mathematics to structural chemistry. Structural branching, cyclicity and, more generally, connectedness are well-known examples of such properties. In particular, various graph measures for detecting structural branching and cyclicity have been investigated. These measures are of limited applicability since their interpretation relies heavily on a certain definition of structural branching. In this paper we define a related measure, taking an approach to measurement similar to that of Lovász and Pelikán (On the eigenvalues of trees, Periodica Mathematica Hungarica, Vol. 3 (1–2), 1973, 175–182). We define a complex valued polynomial which also has a unique positive root. Analytical and numerical results demonstrate that this measure can be interpreted as a structural branching and cyclicity measure for graphs. Our results generalize the work of Lovász and Pelikán since the measure we introduce is not restricted to trees.

Alkuperäiskieli	Englanti
Sivut	19-28
Sivumäärä	10
Julkaisu	Information Sciences
Vuosikerta	471
Varhainen verkossa julkaisun päivämäärä	29 elok. 2018
DOI - pysyväislinkit	https://doi.org/10.1016/j.ins.2018.08.043
Tila	Julkaistu - 1 tammik. 2019
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Rahoitus

Matthias Dehmer thanks the Austrian Science Funds for supporting this work (project P 30031). Yongtang Shi was partially supported by Natural Science Foundation of Tianjin (No. 17JCQNJC00300 ) and National Natural Science Foundation of China. Zengqiang Chen was supported by National Natural Science Foundation of China ( No. 61573199 ).

Julkaisufoorumi-taso

Jufo-taso 1

!!ASJC Scopus subject areas

Software
Control and Systems Engineering
Theoretical Computer Science
Computer Science Applications
Information Systems and Management
Artificial Intelligence

Pääsy asiakirjaan

10.1016/j.ins.2018.08.043

Siteeraa tätä

@article{a5ce2431e45541b782feb84976b6a806,

title = "Towards detecting structural branching and cyclicity in graphs: A polynomial-based approach",

abstract = "Structural properties of graphs and networks have been investigated across scientific disciplines ranging from mathematics to structural chemistry. Structural branching, cyclicity and, more generally, connectedness are well-known examples of such properties. In particular, various graph measures for detecting structural branching and cyclicity have been investigated. These measures are of limited applicability since their interpretation relies heavily on a certain definition of structural branching. In this paper we define a related measure, taking an approach to measurement similar to that of Lov{\'a}sz and Pelik{\'a}n (On the eigenvalues of trees, Periodica Mathematica Hungarica, Vol. 3 (1–2), 1973, 175–182). We define a complex valued polynomial which also has a unique positive root. Analytical and numerical results demonstrate that this measure can be interpreted as a structural branching and cyclicity measure for graphs. Our results generalize the work of Lov{\'a}sz and Pelik{\'a}n since the measure we introduce is not restricted to trees.",

keywords = "Data science, Graphs, Networks, Quantitative graph theory, Structural branching",

author = "Matthias Dehmer and Zengqiang Chen and Frank Emmert-Streib and Abbe Mowshowitz and Yongtang Shi and Shailesh Tripathi and Yusen Zhang",

year = "2019",

month = jan,

day = "1",

doi = "10.1016/j.ins.2018.08.043",

language = "English",

volume = "471",

pages = "19--28",

journal = "Information Sciences",

issn = "0020-0255",

publisher = "Elsevier",

}

TY - JOUR

T1 - Towards detecting structural branching and cyclicity in graphs

T2 - A polynomial-based approach

AU - Dehmer, Matthias

AU - Chen, Zengqiang

AU - Emmert-Streib, Frank

AU - Mowshowitz, Abbe

AU - Shi, Yongtang

AU - Tripathi, Shailesh

AU - Zhang, Yusen

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Structural properties of graphs and networks have been investigated across scientific disciplines ranging from mathematics to structural chemistry. Structural branching, cyclicity and, more generally, connectedness are well-known examples of such properties. In particular, various graph measures for detecting structural branching and cyclicity have been investigated. These measures are of limited applicability since their interpretation relies heavily on a certain definition of structural branching. In this paper we define a related measure, taking an approach to measurement similar to that of Lovász and Pelikán (On the eigenvalues of trees, Periodica Mathematica Hungarica, Vol. 3 (1–2), 1973, 175–182). We define a complex valued polynomial which also has a unique positive root. Analytical and numerical results demonstrate that this measure can be interpreted as a structural branching and cyclicity measure for graphs. Our results generalize the work of Lovász and Pelikán since the measure we introduce is not restricted to trees.

AB - Structural properties of graphs and networks have been investigated across scientific disciplines ranging from mathematics to structural chemistry. Structural branching, cyclicity and, more generally, connectedness are well-known examples of such properties. In particular, various graph measures for detecting structural branching and cyclicity have been investigated. These measures are of limited applicability since their interpretation relies heavily on a certain definition of structural branching. In this paper we define a related measure, taking an approach to measurement similar to that of Lovász and Pelikán (On the eigenvalues of trees, Periodica Mathematica Hungarica, Vol. 3 (1–2), 1973, 175–182). We define a complex valued polynomial which also has a unique positive root. Analytical and numerical results demonstrate that this measure can be interpreted as a structural branching and cyclicity measure for graphs. Our results generalize the work of Lovász and Pelikán since the measure we introduce is not restricted to trees.

KW - Data science

KW - Graphs

KW - Networks

KW - Quantitative graph theory

KW - Structural branching

U2 - 10.1016/j.ins.2018.08.043

DO - 10.1016/j.ins.2018.08.043

M3 - Article

AN - SCOPUS:85052883508

SN - 0020-0255

VL - 471

SP - 19

EP - 28

JO - Information Sciences

JF - Information Sciences

ER -

Towards detecting structural branching and cyclicity in graphs: A polynomial-based approach

Abstrakti

Rahoitus

Julkaisufoorumi-taso

!!ASJC Scopus subject areas

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä