Research Article
Towards Network Complexity
497 downloads
@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
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.
Copyright © 2009–2024 ICST