Eur. Phys. J. B 60, 259-264 (2007)
https://doi.org/10.1140/epjb/e2007-00344-7

Incompatibility networks as models of scale-free small-world graphs

¹ Department of Computer Science and Engineering, Fudan University, Shanghai, 200433, P.R. China
² Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai, 200433, P.R. China
³ Department of Computer Science and Technology, Tongji University, 4800 Cao'an Road, Shanghai, 201804, P.R. China

Corresponding authors: ^a zhangzz@fudan.edu.cn - ^b sgzhou@fudan.edu.cn

Received: 11 August 2007
Published online: 8 December 2007

Abstract

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.