An axiomatic approach to network complexity

Despite the recent wave of interest in the social and physical sciences reg arding "complexity," relatively title attention has been given to the logic al foundation of complexity measurement. With this in mind, a number of fai rly simple, "reasonable" axioms for the measurement of network complexity a re here presented, and some of the implications of these axioms are conside red. It is shown that the only family of graph complexity measures satisfyi ng the "reasonable" axioms is of limited theoretical utility, and hence tha t 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 ano ther on an axiomatic basis. Finally, some suggestions are offered regarding future efforts at measuring graph complexity.