Search on High Degree Graphs

1 Introduction

How does the topology of graphs met in practice differ from uniform random graphs? This is an important question since common topological structures may have a large impact on problem hardness and may be exploitable. Barab´asi and Albert have shown that graphs derived from areas as diverse as the World Wide Web, and electricity distribution contain more nodes of high degree than are likely in random graphs of the same size and edge density [Barab´asi and Albert, 1999]. As a second example, Redner has shown that the citation graph of papers in the ISI catalog contains a few nodes of very high degree [Render, 1998]. Whilst 633,391 out of the 783,339 papers receive less than 10 citations, 64 are cited more than 1000 times, and one received 8907 citations. The presence of nodes with high degree may have a significant impact on search problems. For instance, if the constraint graph of a scheduling problem has several nodes with high degree, then it may be difficult to solve as some resources are scarce. As a second example, if the adjacency graph in a Hamiltonian circuit problem has many nodes of high degree, then the problem may be easy since there are many paths into and out of these nodes, and it is hard to get stuck at a "dead-end" node. Search heuristics like Brelaz's graph coloring heuristic [Brelaz, 1979] are designed to exploit such variation in node degree.

This paper is structured as follows. We first show that nodes of high degree tend to occur infrequently in random graphs but frequently in a wide variety of real world search problems. As test cases, we use exactly the same problems studied in [Walsh, 1999]. We then study some alternative models for randomly generating graphs which give more nonuniform graphs (specifically Barab´asi and Albert's power law model, Watts and Strogatz's small world model, and Hogg's ultrametric model). Finally, we explore the impact of nodes of high degree on search and in particular, on graph coloring algorithms.

2 Random graphs

Two types of random graphs are commonly used, the a0 ✁ ✄ ✆ and the a0 ✁ ✄ ✝ models. In the a0 ✁ ✄ ✆ model, graphs with ✞ nodes and ✟ edges are generated by sampling uniformly from the ✞ ✠ ✞ ☞ ✍ ✏ ✒ ✔ possible edges. In the a0 ✁ ✄ ✝ model, graphs with ✞ nodes and an expected number of ✖ ✞ ✠ ✞ ☞ ✍ ✏ ✒ ✔ edges are generated by including each of the ✞ ✠ ✞ ☞ ✍ ✏ ✒ ✔ possible edges with fixed probability ✖ . The two models have very similar properties, including similar distributions in the degree of nodes. In a random a0 ✁ ✄ ✝ graph, the probability that a node is directly connected to exactly ✤ others, ✖ ✠ ✤ ✏ follows a Poisson distribution. More precisely,

where ✞ is the number of nodes, ✖ is the probability that any pair of nodes are connected, and ✱ is ✠ ✞ ☞ ✍ ✏ ✖ , the expected node degree. As the Poisson distribution decays exponentially, nodes of high degree are unlikely.

In this paper, we focus on the cumulative probability, ✸ ✠ ✤ ✏ which is the probability of a node being directly connected to ✤ or less nodes:

Whilst ✖ ✠ ✤ ✏ is smoothly varying for randomgraphs, it can behave more erratically on real world graphs. The cumulative probability, which is by definition monotonically increasing, tends to give a clearer picture. Figure 1 shows that the cumulative probability against the normalized degree for random graphs rapidly approaches a step function as ✞ increases. The degree of nodes therefore becomes tightly clustered around the average degree.

3 Real world graphs

We next studied the distribution in the degree of nodes found in the real world graphs studied in [Walsh, 1999].

3.1 Graph coloring

We looked at some real world graph coloring problems from the DIMACS benchmark library. We focused on the register allocation problems as these are based on real program code. Figure 2 demonstrates that these problems have a very

skewed distribution in the degree of their nodes. Other problems from the DIMACS benchmark library gave very similar cumulative probability distributions for the degree of their nodes. Compared to random graphs of the same size and edge density, these register allocation problems have a number of nodes that are of much higher and lower degree than the average. For example, the node of maximum degree in Figure 2 is directly connected to 89% of the nodes in the graph. This is more than twice the average degree, and there is less than a 1 in 4 million chance that a node in a random graph of the same size and edge density has degree as large as this. On the other hand, the node of least degree has less than half the average degree, and there is less than a 1 in 7 million chance that a node in a random graph of the same size and edge density has degree as small as this. The plateau region in the middle of the graph indicates that there are very few nodes with the average degree. Most nodes have either higher or lower degrees. By comparison, the degrees of nodes in a random graph are tightly clustered around the average. A similar plateau region around the average degree is seen in most of the register allocation problems in the DIMACS benchmark library.

3.2 Time-tabling

Time-tabling problems can be naturally modelled as graph coloring problems, with classes represented by nodes and time-slots by colors. We therefore tested some real world time-tabling problems from the Industrial Engineering archive at the University of Toronto. Figure 3 demonstrates that problems in this dataset also have a skewed distribution in the degree of their nodes. Other benchmark problems from this library gave very similar curves. Compared to random graphs with the same number of nodes and edges, these timetabling problems have a number of nodes that have much higher and lower degree than the average. For example, the node of maximum degree in Figure 3 is directly connected to 71% of the nodes in the graph. This is nearly three times the average degree, and there is less than a 1 in ✍ ❅ ❇ ❈ chance that a node in a random graph of the same size and edge density has degree as large as this. On the other hand, the node of least degree has approximately one tenth of the average degree, and there is less than a 1 in ✍ ❅ ✾ ❊ chance that a node in a random graph of the same size and edge density has degree as small as this. [Walsh, 1999] suggests that sparse problems in this dataset have more clustering of nodes than the dense problems. However, there was no obvious indication of this in the distribution of node degrees.

3.3 Quasigroups

A quasigroup is a Latin square, a ✟ by ✟ multiplication table in which each entry appears just once in each row or column. Quasigroups can model a variety of practical problems like sports tournament scheduling and the design of factorial experiments. A number of open questions in finite mathematics about the existence (or non-existence) of quasigroups with particular properties have been answered using model finding and constraint satisfaction programs [Fujita et al., 1993]. Recently, a class of quasigroup problems have been proposed as a benchmark for generating hard and satisfiable problem instances for local search methods [Achlioptas et al., 2000].

An order ✟ quasigroup problemcan be represented as a binary constraint satisfaction problem with ✟ ❇ variables, each with a domain of size ✟ . The constraint graph for such a problem consists of ✔ ✟ cliques, one for each row and column, with each clique being of size ✟ . Each node in the constraint graph is connected to ✔ ✠ ✟ ☞ ✍ ✏ other nodes. Hence, ✖ ✠ ✤ ✏ ✪ ✍ if ✤ ✪ ✔ ✠ ✟ ☞ ✍ ✏ and 0 otherwise, and the cumulative probability ✸ ✠ ✤ ✏ is a step function at ✤ ✪ ✔ ✠ ✟ ☞ ✍ ✏ . As all nodes in the constraint graph of a quasigroup have the same degree, quasigroups may suffer from limitations as a benchmark. For example, the Brelaz heuristic [Brelaz, 1979] (which tries to exploit variations in the degree of nodes in the constraint graph) may perform less well on quasigroup problems than on more realistic benchmarks in which there is a variability in the degree of nodes.

4 Non-uniform randommodels

As the a0 ✁ a80 ✆ and a0 ✁ ✄ ✝ models tend to give graphs with a narrow distribution in the degree of nodes, are there any better models for randomly generating graphs? In this section, we look at three different random models, all proposed by their authors to give more realistic graphs.

4.1 Small world model

Watts and Strogatz showed that 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, 1998]. Such graphs tend to occur frequently in real world search problems [Walsh, 1999]. To generate graphs with a small world topology, we randomly rewire a regular graph like a ring lattice [Watts and Strogatz, 1998; Gent et al., 1999]. The ring lattice provides nodes that are highly clustering, whilst the random rewiring introduces short cuts which rapidly reduces the average path length. Unfortunately, graphs constructed in this manner tend not to have a wide distribution in the degree of nodes, and in particular are unlikely to contain any nodes of high degree. For small amounts of rewiring, ✖ ✠ ✤ ✏ peaks around the lattice degree, and converges on the Poisson distribution found in random graphs for more extensive rewiring.

In Figure 4, we plot the cumulative probability for the node degrees of graphs generated to have a small world topology by randomly rewiring a ring lattice. Small world graphs have a distribution of node degrees that is narrower than that for random graphs with the same number of nodes and edges. Due to the lack of variability in the degree of nodes, these small world graphs may have limitations as a model of real world graphs. The absence of nodes of high degree is likely to impact on search performance. For instance, heuristics like Brelaz which try to exploit variations in node degree are likely to find these graphs harder to color than graphs with a wider variability in node degree. Can we find a model with a variability in the node degree that is similar to that seen in the real world graphs studied in the previous section?

4.2 Ultrametric model

To generate graphs with more realistic structures, Hogg has proposed a model based on grouping the nodes into a tree-like structure [Hogg, 1996]. In this model, an ultrametric distance between the ✞ nodes is defined by grouping them into a binary tree and measuring the distance up this tree to a common ancestor. A pair of nodes at ultrametric distance ❘ is joined by an edge with relative probability ✖ ❙ . If ✖ ✪ ✍ , graphs are purely random. If ✖ ❲ ✍ , graphs have a hierarchical clustering as edges are more likely between nearby nodes. Figure 5 gives the cumulative probability distribution for the node degrees in a graph generated with an ultrametric distance using the model from [Hogg, 1996]. There is a definite broadening of the distribution in node degrees compared to random graphs. Nodes of degree higher and lower than the average occur more frequently in these ultrametric graphs than in random graphs. For example, one node in the ultrametric graph is connected to all the other nodes. This node has more than twice the average degree, and there is less than a 1 in 3 million chance that a node in a random graph of the same size and edge density has degree as large as this. On the other hand, the node of least degree has just over half the average degree, and there is less than a 1 in 500 chance that a node in a random graph of the same size and edge density has degree as small as this. Ultrametric graphs thus provide a better model of the distribution of node degrees. However, they lack a small world topology as nodes are not highly clustered [Walsh, 1999]. Can we find a model which has both a small world topology (which has shown to be common in real world graphs) and a large variability in the node degree (which has also been shown to be common)?

4.3 Power lawmodel

Barab´asi and Albert have shown that real world graphs containing nodes of high degree often follow a power law in which the probability ✖ ✠ ✤ ✏ that a node is connected to ✤ others is proportional to ✤ ✭ ❪ where ❫ is some constant (typically around 3) [Barab´asi and Albert, 1999]. Redner has shown that highly cited papers tend to follow a Zipf power law with exponent approximately -1/2 [Render, 1998]. It follows from this result that the degree of nodes in the citation graph for highly cited papers follows a power law with ✖ ✠ ✤ ✏ proportional to ✤ ✭ ❴ . Such power law decay compares to the exponential decay in ✖ ✠ ✤ ✏ seen in random graphs.

To generate power law graphs, Barab´asi and Albert propose a model in which, starting with a small number of nodes (✞ ❈ ), they repeatedly add newnodes with ✟ (✟ ❵ ✞ ❈ ) edges. These edges are preferentially attached to nodes with high degree. They suggest a linear model in which the probability that an edge is attached to a node ✿ is ✤ ✼ ✒ ❛ ❝ ✤ ❝ where ✤ ❝ is the degree of node ❞ . Using a mean-field theory [Barab´asi et al., 1999], they show that such a graph with ✞ nodes has:

That is, ✖ ✠ ✤ ✏ is proportional to ✤ ✭ ❪ where ❫ ✪ ❢ . Note that ✖ ✠ ✤ ✏ is also proportional to ✟ ❇ , the square of the average degree of the graph. In the limit of large ✞ , ✖ ✠ ✤ ✏ ❤❥ ❇ ✆ ❦ ✲ ♠ . The presence of non-linear terms in the preferential attachment probability will change the nature of this power law scaling and may be a route to power laws in which the scaling exponent is different to 3.

We propose a minor modification to this model to tackle the problem that the average degree ✟ is bounded by the size of the initial graph ✞ ❈ . This will hinder the construction of high density graphs (which were not uncommon in the previous section). We suggest connecting an edge to a node ✿ with probability ♣ a113 a115 ✠ ✍ ✉ ✟ ✤ ✼ ✒ ❛ ✼ ✤ ✼ ✏ . Each new node is then connected to the graph by approximately ✟ edges on average. This modification is similar to moving from the a0 ✁ a80 ✆ to the a0 ✁ a80 ✝ model of random graphs.

In Figure 6, we plot the cumulative probability for the degree of nodes in graphs generated by this modified model. As with the ultrametric graphs, we observe a definite broadening of the distribution in node degrees compared to random graphs. Nodes of degree higher and lower than the average occur more frequently in these power law graphs than in random graphs. For example, the node of maximum degree is directly connected to 70% of the nodes in the graph. This is more than three times the average degree, and there is less than a 1 in ✍ ❅ ✾ ✈ chance that a node in a random graph of the same size and edge density has degree as large as this. On the other hand, the node of least degree has nearly one fifth of the average degree, and there is less than a 1 in ✍ ❅ ✇ chance that a node in a random graph of the same size and edge density has degree as small as this. Unlike random graphs in which the distrib ① ution sharpens as we increase the size of graphs, we see a similar spread in the distribution of node degrees as these graphs are increased in size.

Ideally, we want like a method for generating graphs that gives graphs with both nodes of high degree and a small world topology. The nodes of high degree generated by the (modified) Barab´asi and Albert model are likely to keep the average path length short. But are the nodes likely to be tightly clustered? Table 1 demonstrates that these graphs tend to have a small world topology as the graph size is increased.

5 Search

Graphs generated by the modified Barab´asi and Albert model have both a broad distribution in degree of their nodes and a small world topology. These are both features which are common in real world graphs but rare in random graphs. These graphs may therefore be good benchmarks for testing graph coloring algorithms. They may also be useful for benchmarking other search problems involving graphs (e.g. for generating the constraint graph in constraint satisfaction problems, the adjacency graph in Hamiltonian circuit problems, ...)

Unfortunately coloring graphs generated by the (modified) Barab´asi and Albert model is typically easy. Most heuristics based on node degree can quickly (in many cases, immediately) find a ✟ ❸ ✍ -coloring. In addition, a ✟ -clique can be quickly found within the nodes of high degree showing that a ✟ ❸ ✍ -coloring is optimal. A simple fix to this problem is to start with an initial graph which is not a clique. This initial graph could be a ring lattice as in [Watts and Strogatz, 1998; Walsh, 1999], or the inter-linking constraint graph of a quasigroup as in [Gent et al., 1999]. In both cases, we observe similar results. The choice of the initial graph has little effect on the evolution of nodes of high degree. In addition, starting from a ring lattice or the constraint graph of a quasigroup promotes the appearance of a small world topology. As in [Achlioptas et al., 2000; Gent et al., 1999], we generate problems with a mixture of regular structure (from the initial graph) and randomness (from the addition of new nodes).

In Figure 7, we plot the distribution in search costs for coloring graphs with either a power law scaling in their node degree, a small world topology or a purely random topology. To find optimal colorings, we use an algorithm due to Mike Trick which is based upon Brelaz's DSATUR algorithm [Brelaz, 1979]. Unlike small world graphs, power law graphs do not display a long tail in the distribution of search costs. Whilst power law graphs are easier to color than random graphs, there is a larger spread in search costs for power law graphs than for random graphs. The absence of a long tail means that there are less benefits with these power law graphs for a randomization and rapid restart strategy [Gomes et al., 1997; 1998] compared to small world graphs [Walsh, 1999].

5.1 Backbones

Recent efforts to understand the hardness of satisfiability problems has focused on "backbone" variables that are frozen to a particular value in all solutions [Monasson et al., 1998]. It has been shown, for example, that hard random 3-SAT problems from the phase transition have a very large backbone [Parkes, 1997]. Backbone variables may lead to thrashing behaviour since search algorithms can branch incorrectly on them. If these branching mistakes occur high in the search tree, they can be very costly to undo. The idea of backbone variable has been generalized to graph coloring [Culberson and Gent, 2000]. Since any permutation of the colors is also a valid coloring, we cannot look at nodes which must take a given color. Instead, we look at nodes that cannot be colored differently. As in [Culberson and Gent, 2000], two nodes are frozen in a ✤ -colorable graph if they have the same color in all valid ✤ -colorings. No edge can occur between two nodes that are frozen. The backbone is simply the set of frozen pairs.

The power law graphs generated by the modified Barab´asi and Albert model in Figure 7 had very small backbones. Indeed, in many cases, there are only one or two pairs of nodes in the backbone. At the start of search, it is therefore hard to color incorrectly any of the nodes in one of these power law graphs. This helps explain the lack of a long tail in the distribution of search costs. By comparison, the small world graphs had backbones with between fifty and one hundred pairs of nodes in them. At the start of search, it is therefore easy to color incorrectly one of nodes. This gives rise to a long tail in the distribution of search costs for backtracking algorithms like Brelaz's DSATUR algorithm.

6 Conclusions

We have shown that nodes of high degree tend to occur infrequently in random graphs but frequently in a wide variety of real world search problems. As test cases, we used exactly the problem studied in [Walsh, 1999]. We then studied some alternative models for randomly generating nonuniform graphs. Watts and Strogatz's small world model gives graphs with a very narrow distribution in node degree, whilst Hogg's ultrametric model gives graphs containing nodes of high degree but lacks a small world topology. Barab´asi and Albert's power law model combines the best of both models, giving graphs with nodes of high degree and with a small world topology. Such graphs may be useful for benchmarking graph coloring, constraint satisfaction and other search problems involving graphs. We measured the impact of both nodes of high degree and a small world topology on a graph coloring algorithm. The long tail in search costs observed with small world graphs disappears when these graphs are also constructed to contain nodes of high degree. This may be connected to the small size of their "backbone", pairs of edges frozen with the same color.

What general lessons can be learnt from this research? First, search problems met in practice may be neither completely structured nor completely random. Since algorithms optimized 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 introduce both structure and randomness. Second, in addition to a small world topology, many real world graphs display a wide variation in the degree of their nodes. In particular, nodes of high degree occur much more frequently than in purely random graphs. Third, these simple topological features can have a major impact on the cost of solving search problems. We conjecture that graph coloring heuristics like Brelaz are often able to exploit the distribution in node degree, preventing much of thrashing behaviour seen in more uniform graphs.

Acknowledgements

The author is an EPSRC advanced research fellow and wishes to thank the other members of the APES research group.