Complex Systems

From Sierpinski Carpets to Directed Graphs Download PDF

Martin Hülse
Computer Science Department
Aberystwyth University
Aberystwyth, SY23 3DB, UK


Models of complex information processing based on artificial neural networks frequently apply fully connected or random graph structures. However, it is well known that biological neural systems operate on sparsely connected networks having properties quite distinct to random graphs. In this paper, a simple method is introduced for the deterministic generation of strongly connected digraphs. The method is inspired by Sierpinski carpets. Despite the large size of these digraphs, the distance between most of the nodes is short, that is, it scales logarithmically. It is further shown that important network properties, such as average degree and degree distribution, can directly be determined by the initial structure of this process. These findings lead to the formulation of general conditions providing a targeted generation of complex networks of arbitrary size. The circumstances under which these digraphs can show scale-free and small-world properties are discussed and finally possible applications of this method are outlined in the domain of artificial neural networks.