CASOS Working PAPER

"An Axiomatic Approach to Network Complexity" (PDF file)
Author: Carter Butts

Abstract
Despite the recent wave of interest in the social and physical sciences regarding "complexity", relatively little attention has been given to the logical foundation of complexity measurement. Whish this in mind, a number of fairly sinple, "reasonable" axioms for the measurement of networkcomplexity are here presented, and some of the implications of these axioms are It is shown that the only family of graph complexity measures satisfying the "reasonable" axioms is of limited theoretical utility, and hence that those seeking more interesting measures of complexity must be willing to sacrifice at least one intuitively reasonable constraint. Several existing complexity measures are also described, and are differentiated from one another on an axiomatic basis. Finally, some suggestions are offered regarding future efforts at measuring graph complexity.