Towards Network Complexity

Matthias Dehmer; Frank Emmert-Streib

Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009. Revised Papers, Part 1

Research Article

Towards Network Complexity

Download

460 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1007/978-3-642-02466-5_68,
    author={Matthias Dehmer and Frank Emmert-Streib},
    title={Towards Network Complexity},
    proceedings={Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009. Revised Papers, Part 1},
    proceedings_a={COMPLEX PART 1},
    year={2012},
    month={5},
    keywords={networks network complexity information measures},
    doi={10.1007/978-3-642-02466-5_68}
}

Matthias Dehmer
Frank Emmert-Streib
Year: 2012
Towards Network Complexity
COMPLEX PART 1
Springer
DOI: 10.1007/978-3-642-02466-5_68

Matthias Dehmer¹^,*, Frank Emmert-Streib²^,*

1: Institute for Bioinformatics and Translational Research, UMIT
2: Queen’s University Belfast

*Contact email: Matthias.Dehmer@umit.at, v@bio-complexity.com

Abstract

In this paper, we briefly present a classification scheme of information-based network complexity measures. We will see that existing as well as novel measures can be divided into four major categories: (i) partition-based measures, (ii) non partition-based measures, (iii) non-parametric local measures and (iv) parametric local measures. In particular, it turns out that (ii)-(iv) can be obtained in polynomial time complexity because we use simple graph invariants, e.g., metrical properties of graphs. Finally, we present a generalization of existing local graph complexity measures to obtain parametric complexity measures.

Keywords: networks network complexity information measures

Published: 2012-05-11

: http://dx.doi.org/10.1007/978-3-642-02466-5_68