In recent years various complex networks have been identified as having a scale-free structure [1].
Scale-free networks are abundant in nature and society, describing such diverse systems as
the Internet, a network of routers connected by various physical connections, the chemical network of a cell,etc. Not all nodes in a network have the same number of edges. The spread in the node degrees is characterized by a distribution
function P(k), which gives the probability that a randomly selected node has exactly k edges.
One of the most interesting developments in our understanding of complex networks was the discovery that for most of the large networks the degree
distribution significantly deviates from a Poisson distribution. In particular, for a large number of networks,
including the World Wide Web, the Internet or metabolic networks the degree
distribution follows a power-law for a large number of nodes [1].
Such networks are called scale free [1].
A scale-free network is characterized by a power-law degree distribution as follows:

where k is the degree and g is the exponent that depends on each network structure. Scale-free networks have no scale because there is no typical number of links. The random network models assume that the probability that two nodes are connected is random and uniform. In contrast, most real networks exhibit some preferential connectivity.
The Java program developed by Sun Microsystems Laboratories is used as a scale-free
network formation tool [2]. This program can generate scale-free networks being given the number of nodes and
the minimal degree of each agent. We implemented and generated in NetLogo both solvable and unsolvable problems that have a structure of scale-free networks (using scale-free networks from [2]). The constraint graph has a structure of the scale-free network type.
These are scale-free network instance generator for DisCSP in NetLogo.
A instance DisCSP that has a structure of the scale-free network type has a number of variables with a fixed domain and is characterised by the 5-tuple (n, m, t, md, γ), where:
- n is the number of variables;
-m is domain size of each variable;
- t - the constraint
tightness -is the portion of the m*m value pairs in each constraint - determining the proportion of value combinations forbidden by each constraint.
-md= the minimal degree of each nodes and γ is the exponent that depends on each network structure.
[1]. A.~L. Barabasi and A.~L Albert. Emergence of scaling in random networks, Science,
286 (1999), pp.~ 509-512.
[2]. Densmore, O.: An exploration of power-law networks. (2009) http://backspaces.net/sun/PLaw/index.html. |