Search in a Small World

1 Introduction

Graphs that occur in many biological, social and man-made systems are often neither completely regular nor completely random, but have instead a "small world" topology in which nodes are highly clustered yet the path length between them is small [Watts and Strogatz, 19981 By comparison, random graphs with a similar number of nodes and edges have short path lengths but little clustering, whilst regular graphs like lattices tend to have high clustering but large path lengths. A small world topology can have a significant impact on prop­ erties of the graph. For instance, if you are introduced to someone at a party in a small world, you can usually find a short chain of mutual acquaintances connecting you together.

One reason for the occurrence of small world graphs is that it only takes a few short cuts between neighbourhood cliques to turn a large world (in which the average path length be­ tween nodes is large) to a small world (in which the average path length is small). Watts and Strogatz have shown that a social graph (the collaboration graph of actors in feature films), a biological graph (the neural network of the nema­ tode worm C. elegans) and a man-made graph (the electri­ cal power grid of the western United States) all have a small world topology. In a simple model of an infectious disea<>e. they demonstrate that disease spreads much more easily and quickly in a small world. A small world topology may there­ fore have a significant impact on the behavior of dynamical systems. How do they affect search problems?

2 Testing for a small world

To formalize the notion of a small world, Watts and Strogatz define the clustering coefficient and the characteristic path length. The path length is the number of edges in the shortest path between two nodes. The characteristic path length, L is the path length averaged over all pairs of nodes. The clus­ tering coefficient is a measure of the cliqueness of the local neighbourhoods. For a node with k neighbours, then at most k(k- 1)/2 edges can exist between them (this occurs if they form a k-clique). The clustering of a node is the fraction of these allowable edges that occur. The clustering coefficient, G is the average clustering over all the nodes in the graph.

Watts and Strogatz define a small world graph a<> one in which L 2: Lrand (or L ~ Lrand) and G » Grand where Lrand and Grand are the characteristic path length and clus­ tering coefficient of a random graph with the same number of nodes n and edges e. Rather than this simple qualita­ tive test, it might be useful to have a quantitative mea<>ure of "small worldliness". We can then compare the topology of different graphs. To this end, we define the proximity ratio f.l­ as the ratio of GIL normalized by Grand/ Lrand· In graphs with a small world topology, the proximity ratio J1- » 1. By comparison, the proximity ratio J1- is unity in random graphs, and small in regular graphs like lattices. In table 1, we show that the proximity ratio, f.1- is large in those graphs studied in [Watts and Strogatz, 1998] with a small world topology.

3 Modeling a small world

Watts and Strogatz propose a model for small world graphs. Starting from a regular graph, they introduce disorder into the graph by randomly rewiring each edge with proba­ bility p. If p = 0 then the graph is completely regular and ordered. If p = 1 then the graph is completely random and disordered. Intermediate values of p give graphs that are nei­ ther completely regular nor completely disordered. Watts and Strogatz start from a ring lattice with n nodes and k nearest neighbours. They observe similar qualitative behavior with other initial regular graphs and with other mechanisms for in­ troducing disorder. A rewired edge is reconnected to a node chosen uniformly at random from the lattice. If rewiring an edge would create a duplicate edge, they leave it unchanged.

To focus on large, sparse graphs, they demand that n » k » ln(n) » 1, where k » ln(n) ensures that the graphs remain connected. For such graphs, C :::d 3/4 and L :::d n/2k » 1 for p = 0, and C :::d k/n « 1 and L :::d ln(n)/ ln(k) for p = 1. Note that the proximity ratio 1-L :::d 3ln(n)/2ln(k) forp = O(andthisissmallask » ln(n) and hence ln(k) :::d ln(n)) and 1-L = 1 by definition for p = 1. That is, graphs do not have a small world topology for p = 0 and p = 1. As p increac;es from 0, the characteristic path length drops sharply since a few long-range edges introduce short cuts into the graph. These short cuts have little effect on the clustering coefficient. As a consequence the proximity ratio rises rapidly and the graph develops a small world topol­ ogy. As p approaches 1, the neighbourhood clustering start to break down, and the short cuts no longer have a dramatic ef­ fect at linking up nodes. The clustering coefficient and the proximity ratio therefore drop, and the graph loses its small world topology. These topological changes are clearly visible in Figure2.

4 Search problems

There are many search problems in AI that involve graphs (for example, the constraint graph in a constraint satisfaction problem, and the adjacency graph in a Hamiltonian circuit problem). Do such graphs have a small world topology? Does this have an impact on the hardness of solving problems? If so, can we design algorithms to take advantage of the topol­ ogy?

4.1 Graph coloring

One search problem directly affected by the structure of an underlying graph is graph coloring. We therefore tested the topology of some graph coloring problems from the DIMACS benchmark library. We focused on the register allocation problems as these are based on real code. Table 2 demon­ strates that these problems have large clustering coefficients like regular graphs, yet small characteristic path lengths like random graphs .. They therefore have a small world topology.

We observed similar results with other problems from the Dl­ MACS benchmark library.

4.2 Time tabling

Many time-tabling problems can be naturally modelled ac; graph coloring problems. We therefore tested some real world time-tabling problems from the Industrial Engineer­ ing archive at the University of Toronto. Table 3 demon­ strates that sparse problems in this datac;et have large clus­ tering coefficients like regular graphs, but small characteristic path lengths like random graphs. They therefore have a small world topology. By comparison, dense problems from this data<>et have nodes of large degree which are less clus­ tered. Such graphs therefore have less of a small world topol­ ogy. We conjecture that graphs will often start with a sparse small world topology but will become more like dense ran­ dom graphs a<> edges added "saturate" the structure.

4.3 Quasigroup problems

A qua<>igroup is a Latin square, am by m multiplication table in which each entry appears just once in each row or column. Quasi groups model a variety of practical problems like tour­ nament scheduling and designing drug tests. A1 search tech­ niques have been used to answer some open questions in finite mathematics about the existence (or non-existence) of qua<>i­ groups with particular properties [Fujita et al., 19931 More recently, Gomes and Selman have proposed a cla<>s of qua<>i­ group problems a<> a challenging benchmark for constraint satisfaction algorithms [Gomes and Selman, 19971

An order m qua<>igroup problem can be represented as a constraint satisfaction problem with m 2 variables, each with a domain of size m. The constraint graph for such a problem (see figure 3) consists of 2m cliques, one for each row and column, with each clique being of size m. Calculation shows that, for large m, such constraint graphs have a small world topology. As any pair of entries in a qua<>igroup either directly

constrain each other or indirectly through at most one inter­ mediate entry, the characteristic path length, L ~ 2 is small.

A random graph with the same number of edges and nodes also ha<> a characteristic path length Lrand ~ 2. As each vari­ able ha<> 2m - 1 neighbours and these form 2 m-cliques, the clustering coefficient, G ~ 1 /?.is large. A random graph with the same number of edges and nodes ha<> a smaller clustering coefficient Grand ~ 2/m. As L ~ Lrand and G » Grand for large m, the constraint graph has a small world topology, with a proximity ratio 1-L ~ m/ 4. Computation confirms these calculations (see table 4).

5 Search cost

Graphs with a small world topology demonstrate that local properties (i.e. clustering) can be bad predictors for global property (i.e. characteristic path length). Unfortunately, heuristics often use local properties to guide the search for a (global) solution. For example, the Brelaz heuristic colors the node with the least available colors which is connected to the most uncolored nodes. Because of this mismatch be­ tween local and global properties, a small world topology may mislead heuristics and make search problems hard to solve. To test this thesis, we colored graphs generated accord­ ing to Watts and Strogatz' s model using an algorithm due to Mike Trick. which is bac;ed upon Brelaz' s DSATUR algorithm [Brelaz, 19791 To ensure that problems were of a manage­ able size for this algorithm, we used graphs with n = 100 and k = 8. For these graphs, the proximity ratio peaks around log2(p) ~ -4 similar to Figure 2. Whilst most graphs of this size can be colored without too much search, one graph wa<> not solved in 10 10 nodes and more than a week of CPU time. We therefore imposed a search cutoff at 10 8 nodes. On a 133 MHz Pentium, this is approximately 1 hour of com­ putation. As we distributed our experiments over a variety of networked computers, we do not report runtimes but use nodes visited in the backtracking search tree. On any given machine, runtimes are roughly proportional to the number of nodes searched.

In Figure 4, we plot the search cost against the rewiring probability, p. Asp increases from 0 and graphs develop a small world topology, the search cost in the higher percentiles rises rapidly. However, a<> p approaches 1 and graphs lose their small world topology, the search cost in the higher per­ centiles falls back. For graphs with a small world topology, most problems took less than 10 5 nodes to color. However, 1% took more than 10 8 nodes. We suspect that problems with a small world topology can be difficult to color since local de­ cisions quickly propagate globally.

6 Heavy-tailed distributions

Exceptionally hard problems like this have been observed in other search problems, though usually with less frequency. For example, Gent and Walsh found that a few satisfiabil­ ity problems from the constant probability model were or­ ders of magnitude harder than the median [Gent and Walsh 19941 Grant and Smith also found a few exceptionally hard problems in a random model of binary constraint satisfaction problems [Grant and Smith, 19951 More recently, Gomes and Sel?Jan have observed similar behavior in quasigroup completiOn problems (whose constraint graph, we recall, has a small world topology) [Gomes et al., 1997] and in tour­ nament scheduling, planning and circuit synthesis problems [Gomes et al., 19981 They show that such behavior can of­ ten be modeled by a "heavy-tailed" distribution of the Pareto­ Levy form. In such a distribution, the tail has the form,

where Pr(X > x) is the probability that the variable X ex­ ceeds some value x, and a > 0 is a constant called the "index of stability". If a < 2 then any moment of X of order less than a is finite but higher orders are infinite 1 · For example, if a = 1.4, then X has finite mean but infinite variance.

To test for such heavy-tails in the distribution of search costs, we plot the nodes searched against the probability that the search takes more than this number of nodes using log scales. A heavy-tailed distribution of the Pareto-Levy form gives a straight line with gradient -a. In Figure 5, we plot the distribution of search costs at a variety of different values of log2 (p). This figure shows that for graphs with a small world topology (i.e. log2 (p) = -4), we can model the dis­ tribution of search costs by a heavy-tailed distribution of the Pareto-Levy form. The gradient suggests that the index of stability, a < -1/2. That is, the model of the distribution of search costs has infinite mean and variance. By comparison, for random graphs (i.e. log 2(p) = 0) and more structured graphs (i.e. log2 (p) = -8), search costs in the tail of the distribution drop more rapidly.

1 Backtracking algorithms like DSATUR have an upper bound on their running time that is exponential in the problem size. The mean or variance in their running time cannot therefore be infinite. How­ ever,_ for large problem instances, the upper bound may be so astro­ norrucally large that we can model it as if it were infinite.

As in [Gomes et al., 1997; 1998], we observe similar heavy-tail behavior even when solving a single problem in­ stance. We picked the first problem from the sample gener­ ated at log 2 (p) ~ -4 which took more than 10 8 nodes to solve. We re-solved this problem 1000 times, randomizing the order of the nodes in the graph so that the Brelaz heuris­ tic makes different branching decisions. We again observe heavy-~led behavior, with 77% of presentations of this prob­ lem taking less than 300 nodes to solve, but the rest taking more than 10 7 nodes.

. A s~all world topology appears therefore to have a signif­ ICant Impact on the cost to solve graph problems. In partic­ ular, it often introduces a heavy-tail into the distribution of search ~os~s. We conjecture that a small world topology will have a surular effect on other types of search problems involv­ ing graphs. For example, we predict that the distribution of costs for finding a Hamiltonian circuit in a graph with a small world topology will often display heavy-tailed behavior. As a second ~xample, we anticipate that exceptionally hard prob­ lems will be more common in constraint satisfaction prob­ lems whose constraint graph ha<; a small world topology than those with a purely random topology. Gomes, Selman and Kautz's state that "Further studies are needed to determine what characteristics of combinatorial search problems lead to heavy-tailed behavior" page 435, [Gomes et al., 19981 Our experiments suggest that a small world topology may be one answer to this question.

7 Randomization and restarts

To combat heavy-tailed distributions like this, Gomes, Sel­ man and Kautz propose the RRR strategy of randomization and rapid restart [Gomes et al. , 1998]. This strategy pre­ vents a_search proced":fe from being trapped in the long tail to the nght of the median, and exploits any heavy-tail to the lef~ of the distribution (i.e. occa<;ional runs that succeed very qmckly). Does such a strategy help when searching graphs with a small world topology? Does it eliminate this heavy­ tailed behavior? In Figure 6, we plot the search cost using the RRR strategy against the cuttoff parameter on the problem at log 2 (p) = -4 mentioned in the previous section. This prob­ lem ha<> a small world topology and took the chronological backtracldng search procedure over 10 8 nodes to solve. With a cutoff limit of between 200 to 400 nodes, the RRR strategy eliminates the heavy-tail in the search cost distribution.

To determine a good cutoff value for the restart strategy, Gomes et al. suggest" ... a trial-and-error process, where one experiments with various cutoff values, starting at relatively low values ... " [Gomes et al., 19981 To help automate this process, we suggest the RGR strategy of randomization and geometric restarts. Each new trial has a cutoff value which is a constant factor, r larger than the previous. This strat­ egy profits from the success rate being high when the cutoff value is close to optimal. Increa<>ing the cutoff value geomet­ rically ensures that we get close to the optimal value within a few restarts. We then hope to solve the problem within a few more restarts, before the cutoff value has increased too far from optimum. Figure 7 shows that the RGR strategy is even better at reducing search than the RRR strategy on this problem instance. The RGR strategy was also less sensitive to the setting of the cutoff parameters than the RRR strategy. We obtained similar improvements on other problem instances. It would be interesting to see if the RGR strategy is effective on other search problems like planning and scheduling.

8 Approximate entropy

Hogg notes that real constraint satisfaction problems often have variables that are more clustered than in random prob­ lems [Hogg, 19981 He uses a notion of "approximate en­ tropy" to distinguish between problems drawn from a clus­ tered ensemble and those from a random ensemble. Can ap­ proximate entropy act a<> a replacement measure for the clus­ tering coefficient?

The approximate entropy is a mea<>ure of the similarity be­ tween substructures in a problem. It therefore depends on the representation used. As in [Hogg, 1998], we consider the substructures of a graph to be subgraphs, and compare them up to isomorphism. Consider the d distinct subgraphs of size m. If /; is the frequency of the ith distinct subgraph, d . and <l>m = - L:;i=l /; log/; then the appro~mate entropy for subgraphs of size m is defined by, ~

This measures the log-likelihood that two subgraphs of size m + 1 are isomorphic given that they contain subgraphs of size m that are isomorphic.

As there are only two distinct subgraphs of size 2 up to isomorphism (the 2 node subgraph with an edge, and the one without) S 1 = <1> 2 = -flog(!) - (1 -f) log(1 -f) where f = 2e/n(n- 1). Hence, S 1 depends only on nand e, and not on the topology of the graph. We will need to consider sm for m 2:: 2 to distinguish random graphs from clustered ones. Fortunately, the number of non-isomorphic subgraphs grows rapidly with m, so it is usually adequate to consider S 2 or S 3 . In Figure 8, we plot S 1 , S 2 and S 3 for randomly rewired ring lattices generated by Watts and Strogatz' s model. As we take logarithms to ba<>e 2, the approximate entropy is measured in bits. The approximate entropy for subgraphs up to size 3 shows no obvious correlation with the rewiring probability, p (and therefore the clustering coefficient). Unfortunately, computing the approximate entropy for larger subgraphs is not computationally practical as it involves considering all subgraphs of size 5 (or, at least, a representitive sample of them).

9 Related work

Grant and Smith studied binary constraint satisfaction prob­ lems with a "braided" constraint graph similar to a ring lattice [Grant and Smith, 19951 In this problem class, exceptionally hard problems occur more frequently and with greater vigor than in a purely random ensemble. They suggest that, as prob­ lems met in practice are likely to have constraint graphs with this sort of structure, such problems deserve further investi­ gation. Our research supports and refines these observations.

To generate graphs with more realistic structures, Hogg has proposed a clustered ensemble based on grouping the nodes into a tree-like structure [Hogg, 19961 In a random ensem­ ble, each graph with n nodes and e edges is equally likely. In Hogg' s clustered ensemble, an ultrametric distance between the n nodes is defined by grouping them into a binary tree and measuring the distance up this tree to a common ances­ tor. A pair of nodes at ultrametric distance d is joined by an edge with relative probability pd. If p = 1, graphs are purely random. If p < 1, graphs have a hierarchical clustering as edges are more likely between nearby nodes. These graphs tend to have characteristic path lengths and clustering coeffi­ cients similar to random graphs. Although nodes at the top of the tree tend to be more clustered than in random graphs, nodes lower down tend to be less clustered. We therefore need a more refined notion than the clustering coefficient to distinguish their topology from that of random graphs.

10 Conclusions

In a graph with a small world topology, nodes are highly clustered yet the path length between them is small. Such a topology can make search problems very difficult since local decisions quickly propagate globally. To provide a quantita­ tive measure of the extent to which a graph ha'i this topol­ ogy, we have proposed the proximity ratio, J-l· This is the ratio of the clustering coefficient and the characteristic path length, normalized by the values for a random graph with the same number of edges and numbers. Using this measure, we have shown that many graphs a<;sociated with search prob­ lems have a small world topology, and that the cost of solving such search problems can have a heavy-tailed distribution. As in other studies, randomization and restarts appear to elimi­ nate these heavy tails.

What general lessons can be learnt from this study? First, search problems met in practice may be neither completely structured nor completely random. Since algorithms opti­ mized for purely random problems may perform poorly on problems that contain both structure and randomness, it may be useful to benchmark with problem generators that intro­ duce both structure and randomness. Second, simple topo­ logical features can have a large impact on the cost of solv­ ing search problems. In particular, search problems involv­ ing graphs with a small world topology can sometimes be very difficult to solve. It may therefore be useful to optimize algorithm performance for such topological features. Third, randomization and restarts is again an effective strategy to tackle heavy-tailed distributions. The RGR strategy in which the cutoff value increases geometrically shows considerable promise. And finally, it really does seem that we live in a small world.