SCALE-FREE STRUCTURES: MODELS AND ALGORITHMS

Technology has helped to improve our lives, but brought us new challenges. We often deal with complex information structures which are hard to understand.For instance, the last part of the twentieth century witnessed a huge expansion of the internet and the world-wide web (WWW). The falling cost of computer hardware allows individuals to have easy access to vast quantities of data on the WWW. And yet algorithms to structure the data content of the WWW are in their infancy. Even the very nature of the web is not precisely established. The bio-informatics era has seen a major focusing of biological research on the building blocks that make up organisms. The availability of complete genomes for the first time has caused an enthusiastic embracing of reductionism (as early as 1966, Francis Crick, Nobel prize winner for discovering the structure of the DNA, claimed that an organism is essentially nothing but a collection of atoms and molecules ). This enthusiasm, however, is giving place to frustration as scientists realize that complex processes, occurring in a complex environment (the cell - the body), understood by studyingthe components of the system but ignoring their interactions.To manage such structures we may represent them as networks of related objects. A promising approach is to model such networks as outcomes of random processes often referred to as scale-free graphs. These models typically evolve by updating the existing structure using a mixture of preferential attachment, and random selection. The preferential attachment mimics the social behaviour which often tends to follow the popular option. Studies of the structure of the WWW have demonstrated that scale-free models fit such structure. Even for the web however, mathematical models are still in their infancy, and this is even more true for other disciplines such as Biology.Our main research objective is to explore new models and algorithms related to scale-free graphs. The success of the project will be evaluated by measuring how well the proposed models and algorithms fit the reality.The modelling objective will be achieved by applying relevant concepts from scale-free graphs to the real systems arising in biological processes and data mining. In particular (more details are given in the case-for-support) we believe that scale-free graphs can be used to model the peculiar protein-to-protein interaction networks present in cancer cells. Such a study may provide us with better explanations of the unusual robustness of cancer cells, and point to good pharmaceutical targets that might disrupt the wiring of the network. The evaluation of such proposal will be based of biological data made available by the Oncology Research Unit in Liverpool.We also plan to improve the present understanding of the WWW itself by developing and analysing new algorithms for finding web communities, improved resource limited web search algorithms (perhaps based on random-walk techniques), and combinatorial algorithms for various hard optimization problems in networks like the WWW. We will achieve our objectives through collaboration between the two UK investigators and by working in cooperation with R. Klasing (LaBRI, France).We also believe that an appropriate level of networking with the broader scientific community will be beneficial to the project. Therefore we have allocated a budget to attend relevant conferences.