A computational approach to construct a multivariate complete graph invariant

Research output: Contribution to journal › Article › Scientific › peer-review

Standard

A computational approach to construct a multivariate complete graph invariant. / Dehmer, Matthias; Emmert-Streib, Frank; Grabner, Martin.

In: Information Sciences, Vol. 260, 01.03.2014, p. 200-208.

Research output: Contribution to journal › Article › Scientific › peer-review

Bibtex - Download

@article{ff301f9dc9d9461ea51530e263b0280b,

title = "A computational approach to construct a multivariate complete graph invariant",

abstract = "In this paper, we present a computational approach for finding complete graph invariants. Specifically, we generate exhaustive sets of connected, non-isomorphic graphs with 9 and 10 vertices and demonstrate that a 97-dimensional multivariate graph invariant is capable to distinguish each of the non-isomorphic graphs. Furthermore, in order to tame the computational complexity of the problem caused by the vast number of graphs, e.g., involving over 10 million networks with 10 vertices, we suggest a low-dimensional, iterative procedure that is based on highly discriminative individual graph invariants. We show that also this computational approach leads to a perfect discrimination. Overall, our numerical results prove the existence of such graph invariants for networks with 9 and 10 vertices. Furthermore, we show that our iterative approach has a polynomial time complexity.",

keywords = "Information inequality, Quantitative graph theory, Random network model, Statistics",

author = "Matthias Dehmer and Frank Emmert-Streib and Martin Grabner",

year = "2014",

month = "3",

day = "1",

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

language = "English",

volume = "260",

pages = "200--208",

journal = "Information Sciences",

issn = "0020-0255",

publisher = "Elsevier",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - A computational approach to construct a multivariate complete graph invariant

AU - Dehmer, Matthias

AU - Emmert-Streib, Frank

AU - Grabner, Martin

PY - 2014/3/1

Y1 - 2014/3/1

N2 - In this paper, we present a computational approach for finding complete graph invariants. Specifically, we generate exhaustive sets of connected, non-isomorphic graphs with 9 and 10 vertices and demonstrate that a 97-dimensional multivariate graph invariant is capable to distinguish each of the non-isomorphic graphs. Furthermore, in order to tame the computational complexity of the problem caused by the vast number of graphs, e.g., involving over 10 million networks with 10 vertices, we suggest a low-dimensional, iterative procedure that is based on highly discriminative individual graph invariants. We show that also this computational approach leads to a perfect discrimination. Overall, our numerical results prove the existence of such graph invariants for networks with 9 and 10 vertices. Furthermore, we show that our iterative approach has a polynomial time complexity.

AB - In this paper, we present a computational approach for finding complete graph invariants. Specifically, we generate exhaustive sets of connected, non-isomorphic graphs with 9 and 10 vertices and demonstrate that a 97-dimensional multivariate graph invariant is capable to distinguish each of the non-isomorphic graphs. Furthermore, in order to tame the computational complexity of the problem caused by the vast number of graphs, e.g., involving over 10 million networks with 10 vertices, we suggest a low-dimensional, iterative procedure that is based on highly discriminative individual graph invariants. We show that also this computational approach leads to a perfect discrimination. Overall, our numerical results prove the existence of such graph invariants for networks with 9 and 10 vertices. Furthermore, we show that our iterative approach has a polynomial time complexity.

KW - Information inequality

KW - Quantitative graph theory

KW - Random network model

KW - Statistics

UR - http://www.scopus.com/inward/record.url?scp=84891738883&partnerID=8YFLogxK

U2 - 10.1016/j.ins.2013.11.008

DO - 10.1016/j.ins.2013.11.008

M3 - Article

VL - 260

SP - 200

EP - 208

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

ER -

TUTCRIS Research Portal