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

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

    Research output: Contribution to journalArticleScientificpeer-review

    6 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)407-414
    Number of pages8
    JournalInformation Sciences
    Volume467
    DOIs
    Publication statusPublished - 1 Oct 2018
    Publication typeA1 Journal article-refereed

    Funding

    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.

    Keywords

    • Data science
    • Graphs
    • Networks
    • Quantitative graph theory
    • Statistics

    Publication forum classification

    • Publication forum level 1

    ASJC Scopus subject areas

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

    Fingerprint

    Dive into the research topics of 'Graph measures with high discrimination power revisited: A random polynomial approach'. Together they form a unique fingerprint.

    Cite this