Preferential Attachment in Constraint Networks
David Devlin, Barry O’Sullivan · 2009
Many complex real-world systems can be modeled using a graphical structure such as a constraint network. If the properties of such a structure can be exploited, many challenging computational tasks can have good typical-case runtimes even if they are theoretically intractable in general. In this paper we show that many real-world constraint networks induce binary networks that share a common underlying structural characterisation; namely, that their degree distributions exhibit preferential attachment. We report on a novel constraint network generator for random constraint networks that have a scale-free macrostructure. This scale-free generator is based on the well known Barabasi-Albert preferential attachment model. Using this model we demonstrate that real-world constraint networks exhibit degree distributions that are more like those found in scale-free graphs. We also show that the effect of standard degree-based search heuristics on real-world problems exhibiting power-law degree distributions is greater than problems with a uniform random structure. We also show that the backdoor sizes for preferentially attached constraint networks are smaller than those of uniform random problems. This paper provides a novel basis for studying realistic constraint models.