Thumbnail
Access Restriction
Open

Author Standish, Russell K.
Source arXiv.org
Content type Text
File Format PDF
Date of Submission 2009-11-18
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Natural sciences & mathematics ♦ Mathematics ♦ Physics ♦ Life sciences; biology
Subject Keyword Computer Science - Information Theory ♦ Nonlinear Sciences - Adaptation and Self-Organizing Systems ♦ Quantitative Biology - Populations and Evolution ♦ G.2.2 ♦ cs ♦ math ♦ nlin ♦ q-bio
Abstract Network or graph structures are ubiquitous in the study of complex systems. Often, we are interested in complexity trends of these system as it evolves under some dynamic. An example might be looking at the complexity of a food web as species enter an ecosystem via migration or speciation, and leave via extinction. In a previous paper, a complexity measure of networks was proposed based on the {\em complexity is information content} paradigm. To apply this paradigm to any object, one must fix two things: a representation language, in which strings of symbols from some alphabet describe, or stand for the objects being considered; and a means of determining when two such descriptions refer to the same object. With these two things set, the information content of an object can be computed in principle from the number of equivalent descriptions describing a particular object. The previously proposed representation language had the deficiency that the fully connected and empty networks were the most complex for a given number of nodes. A variation of this measure, called zcomplexity, applied a compression algorithm to the resulting bitstring representation, to solve this problem. Unfortunately, zcomplexity proved too computationally expensive to be practical. In this paper, I propose a new representation language that encodes the number of links along with the number of nodes and a representation of the linklist. This, like zcomplexity, exhibits minimal complexity for fully connected and empty networks, but is as tractable as the original measure. ...
Description Comment: Accepted in Complexity
Reference: Complexity, v 17, 50-61, (2012)
Educational Use Research
Learning Resource Type Article


Open content in new tab

   Open content in new tab