Towards network complexity

Matthias Dehmer, Frank Emmert-Streib

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

7 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering
Pages707-714
Number of pages8
Volume4 LNICST
EditionPART 1
DOIs
Publication statusPublished - 2009
Externally publishedYes
Publication typeA4 Article in conference proceedings
Event1st International Conference on Complex Sciences: Theory and Applications, Complex 2009 - Shanghai, China
Duration: 23 Feb 200925 Feb 2009

Publication series

NameLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering
NumberPART 1
Volume4 LNICST
ISSN (Print)18678211

Conference

Conference1st International Conference on Complex Sciences: Theory and Applications, Complex 2009
Country/TerritoryChina
CityShanghai
Period23/02/0925/02/09

Keywords

  • Information measures
  • Network complexity
  • Networks

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Towards network complexity'. Together they form a unique fingerprint.

Cite this