Incompatibility networks as models of scale-free small-world graphs
Department of Computer Science and Engineering, Fudan University, Shanghai, 200433, P.R. China
2 Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai, 200433, P.R. China
3 Department of Computer Science and Technology, Tongji University, 4800 Cao'an Road, Shanghai, 201804, P.R. China
Published online: 8 December 2007
We make a mapping from Sierpinski fractals to a new class of networks, the incompatibility networks, which are scale-free, small-world, disassortative, and maximal planar graphs. Some relevant characteristics of the networks such as degree distribution, clustering coefficient, average path length, and degree correlations are computed analytically and found to be peculiarly rich. The method of network representation can be applied to some real-life systems making it possible to study the complexity of real networked systems within the framework of complex network theory.
PACS: 89.75.Hc – Networks and genealogical trees / 05.45.Df – Fractals / 02.10.Ox – Combinatorics; graph theory / 89.75.Da – Systems obeying scaling laws
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2007