TY - GEN
T1 - Towards network complexity
AU - Dehmer, Matthias
AU - Emmert-Streib, Frank
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - Information measures
KW - Network complexity
KW - Networks
UR - https://www.scopus.com/pages/publications/84885886016
U2 - 10.1007/978-3-642-02466-5_68
DO - 10.1007/978-3-642-02466-5_68
M3 - Conference contribution
AN - SCOPUS:84885886016
SN - 3642024653
SN - 9783642024658
T3 - Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering
SP - 707
EP - 714
BT - Complex Sciences - First International Conference, Complex 2009, Revised Papers
T2 - 1st International Conference on Complex Sciences: Theory and Applications, Complex 2009
Y2 - 23 February 2009 through 25 February 2009
ER -