Graph measures with high discrimination power revisited: A random polynomial approach

Matthias Dehmer; Zengqiang Chen; Frank Emmert-Streib; Yongtang Shi; Shailesh Tripathi

doi:10.1016/j.ins.2018.07.072

Graph measures with high discrimination power revisited: A random polynomial approach

Matthias Dehmer, Zengqiang Chen, Frank Emmert-Streib, Yongtang Shi, Shailesh Tripathi

Tutkimustuotos: Artikkeli › Tieteellinen › vertaisarvioitu

6 Sitaatiot (Scopus)

Abstrakti

Finding graph measures with high discrimination power has been triggered by searching for so-called complete graph invariants. In a series of papers, we have already investigated highly discriminating measures to distinguish graphs (networks) based on their topology. In this paper, we propose an approach where the graph measures are based on the roots of random graph polynomials. The polynomial coefficients have been defined by utilizing information functionals which capture structural information of the underlying networks. Our numerical results obtained by employing exhaustively generated graphs reveal that the new approach outperforms earlier results in the literature.

Alkuperäiskieli	Englanti
Sivut	407-414
Sivumäärä	8
Julkaisu	Information Sciences
Vuosikerta	467
DOI - pysyväislinkit	https://doi.org/10.1016/j.ins.2018.07.072
Tila	Julkaistu - 1 lokak. 2018
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Rahoitus

Matthias Dehmer thanks the Austrian Science Funds for supporting this work (project P26142). Yongtang Shi was supported by National Natural Science Foundation of China and PCSIRT.

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.07.072

Siteeraa tätä

@article{a40db4c6a2e04a008297862c4bb6421e,

title = "Graph measures with high discrimination power revisited: A random polynomial approach",

abstract = "Finding graph measures with high discrimination power has been triggered by searching for so-called complete graph invariants. In a series of papers, we have already investigated highly discriminating measures to distinguish graphs (networks) based on their topology. In this paper, we propose an approach where the graph measures are based on the roots of random graph polynomials. The polynomial coefficients have been defined by utilizing information functionals which capture structural information of the underlying networks. Our numerical results obtained by employing exhaustively generated graphs reveal that the new approach outperforms earlier results in the literature.",

keywords = "Data science, Graphs, Networks, Quantitative graph theory, Statistics",

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

note = "EXT={"}Tripathi, Shailesh{"}",

year = "2018",

month = oct,

day = "1",

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

language = "English",

volume = "467",

pages = "407--414",

journal = "Information Sciences",

issn = "0020-0255",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Graph measures with high discrimination power revisited

T2 - A random polynomial approach

AU - Dehmer, Matthias

AU - Chen, Zengqiang

AU - Emmert-Streib, Frank

AU - Shi, Yongtang

AU - Tripathi, Shailesh

N1 - EXT="Tripathi, Shailesh"

PY - 2018/10/1

Y1 - 2018/10/1

N2 - Finding graph measures with high discrimination power has been triggered by searching for so-called complete graph invariants. In a series of papers, we have already investigated highly discriminating measures to distinguish graphs (networks) based on their topology. In this paper, we propose an approach where the graph measures are based on the roots of random graph polynomials. The polynomial coefficients have been defined by utilizing information functionals which capture structural information of the underlying networks. Our numerical results obtained by employing exhaustively generated graphs reveal that the new approach outperforms earlier results in the literature.

AB - Finding graph measures with high discrimination power has been triggered by searching for so-called complete graph invariants. In a series of papers, we have already investigated highly discriminating measures to distinguish graphs (networks) based on their topology. In this paper, we propose an approach where the graph measures are based on the roots of random graph polynomials. The polynomial coefficients have been defined by utilizing information functionals which capture structural information of the underlying networks. Our numerical results obtained by employing exhaustively generated graphs reveal that the new approach outperforms earlier results in the literature.

KW - Data science

KW - Graphs

KW - Networks

KW - Quantitative graph theory

KW - Statistics

U2 - 10.1016/j.ins.2018.07.072

DO - 10.1016/j.ins.2018.07.072

M3 - Article

AN - SCOPUS:85051518614

SN - 0020-0255

VL - 467

SP - 407

EP - 414

JO - Information Sciences

JF - Information Sciences

ER -

Graph measures with high discrimination power revisited: A random polynomial approach

Abstrakti

Rahoitus

Julkaisufoorumi-taso

!!ASJC Scopus subject areas

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä