An axiomatic approach to network complexity

One can set out a number of ``reasonable axioms regarding the complexity of graps, and then use these for both constructive and classificatory purposes. While complexity measures do exist which satisfy all of the suggested axioms, such measures are not interesting for most purposes; they are structurally degenerate, depending only on the grap size. By relaxing certain of the author's requirements, it is possible to admit measures which exhibit more variability within size classes, with the particular relaxation in question determining the properties of the measures permitted. Examining one such relaxation (that of full monotonicity) allows for the definition of a new and distinct complexity measure, the induced subgraph complexity, which increases with the diversity of substructures present within a graph. Considering the relaxations required to admit (and fully classify) a number of extent complexity measures, it can be seen that the existing notions of graph complexity span a wide range of assumptions; although certain family resemblances between measures exist (e.g., within information -- based measures), the number of widely shared properties is limited (absent certain very basic properties such as determinism and existence). Among those definitions of complexity considered here, almost all do obey the properties of labeling insensitivity and complementarity. Most do not obey monotonicity or normalization, although most do obey the less restrictive sample monotonicity property. This study has limited itself to postulating a small number of fairly general axioms, and to examining only a handful of complexity measures, with the intent of establishing a set of basic results on which a more complete axiomatic treatment could expand. At least two directions, then suggest themselves: first, the possibility of elaborating and refining the axiom set to allow a larger set of deductions; and, second, the classification of measures beyond those considered here. Given the current fragmentation of the subject, it would seem highly advisable for those proposing new measures of graph complexity to (at the very least) demonstrate those of the basic axioms presented here which are or are not satisfied by the measures in question, and (ideally) to show how the new measures may be derived axiomatized in their entirety. While admittedly somewhat time consuming, such a procedure would ensure that the assumptions underlying novel measures may be clearly understood and examined, and would facilitate the comparison (and possible unificaton) of disparate notions of graph complexity. Though complexity appears to be a powerful and compelling concept, its study is unduly hampered by a lack of attention to foundational issues; it is hoped that the axiomatic approach presented here will aid in rectifying this situation.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: An axiomatic approach to network complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2731526)