Many complex real-world systems can be modeled using a graphical representation such as a constraint network. If structure can be exploited, many challenging computational tasks can have good typical-case runtimes even if they are theoretically intractable in general. This paper reports on some early experiments in a PhD-level research agenda. 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. We show that scale-free constraint networks exhibit interesting phase transition behaviours which have not been seen for other problem classes studied so far.