In the ANNE project, we hope to identify and classify structural properties of typical real-world networks and use this structural information to design algorithms that are especially constructed to perform well on particular, application-motivated classes of problem instances.

As discussed above, such an approach is useful for example in routing traffic in communication networks; optimising a protocol according to the characteristics of the network on which it operates provides speedup and reduces computational load. Current industrial systems often resort to extemporaneous solutions, as the analytically justified algorithms are designed to perform well on a (uniform) random instance rather than the actual problem instances. Thus far only very few articles have appeared discussing e.g. shortest path problems that take the network structure into account. Practical algorithmic work based on the recent advances in network modelling still seems rare. We expect that observations on the structure of natural networks will help to design better algorithms, approximations and heuristics for computationally demanding network problems.

In order to measure properties of massive natural networks, research efforts are necessary in the area of random sampling. Of special interest is to efficiently sample a large network with some known structural properties efficiently according to distributions of interest. Uniform random sampling is important in the study of massive or extremely dense networks for which complete examination is infeasible by means of raw computation. This line of research is intimately connected to theoretical questions concerning the mixing rates of random walks on various types of graphs.

Another application area for nonuniform network research as well as sampling is the study of the robustness of networks, i.e., how many nodes may be disabled either randomly or by a malicious adversary without significantly affecting the structure of the network. For example, random breakdowns of routers in a communication network may have different effects on a routing algorithm depending on the structural properties of the original communication network. This line of research is also related to issues of epidemic spreading, particularly the design of vaccination algorithms limiting the spreading of an epidemic as effectively as possible under limited resources.

Our current research is concerned with clustering in large networks, aiming to design methods that correctly and efficiently identify semantically meaningful subsystems in massive and possibly largely unknown networks such as the World Wide Web. For the Web, applications of clustering are numerous, including improvements to indexing and searching methods.

During 2004, some results of the clustering research will be published, and the sampling research will be strengthened. The direction of our further algorithmic studies may be adjusted according to ideas obtained from discussions with more application-oriented research groups. Collaboration is already initiating in relation to modelling ad-hoc wireless networks, and employing clustering algorithms in designing efficient routing algorithms in this setting.

The research methodology in the project will include not only mathematical analysis of networks and algorithms, but also experimental work. We shall implement the software necessary to generate test networks according to given models and parameters, analyse natural data, and simulate and measure algorithmic behavior. The software and the data sets will be put at the disposal of other researchers.