×

Fractality and the small-world effect in Sierpinski graphs. (English) Zbl 1113.28007

The authors construct a deterministic family of graphs based on the Sierpiński family of fractals that exhibits both the small world phenomenon and fractal self-similarity. To quantify this fractality the authors calculate various box-counting dimensions of the graphs under consideration. Thus the authors construct a family of graphs which simultaneously exhibit two of the major properties found in many real world networks. The paper contains constructions and proofs of the basic properties of three families of Sierpiński graphs; the gasket, the carpet and the tetra. The graphs are constructed in an entirely deterministic manner using the underlying self-similar structure of the respective families. The authors go on to compute the diameter, the clustering and the box-counting dimension of these families of non-small world graphs. The authors then introduce the small world phenomenon by altering the construction of the non-small world graphs with the introduction of a new node at particular steps of the iterative construction. These new nodes are then joined to a suitably chosen subset of nodes in the underlying non-small world graph to reduce the diameter of the graph in such a way that the diameter of each family is now logarithmic of order \(N\) whilst still giving the same box-counting dimension as the non-small world counterpart. This quantifies the simultaneous existence of the two properties mentioned above. Further the authors show that the newly constructed small world graphs not only have a well defined fractal dimension that is the same as their non-small world counterparts, but they also do not greatly change the overall structure of the non-small world graphs. This is quantified by showing that the number of added edges and the clustering variation are suitably small.

MSC:

28A80 Fractals
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI