Algorithms for Networks and Link-Structured Data

摘要

The research has focused on the design of algorithms for networks and the information resources that they support. Link analysis algorithms have been developed with applications to the design of World Wide Web search engines. A collection of models and algorithms, have been developed for decentralized search in so-called 'small-world' networks; this has led to applications in both social network analysis and in the design of peer-to-peer computing systems. Techniques from these small-world algorithms have been extended to form the basis of distributed gossip algorithms for the robust dissemination of information through a network. Algorithms have also been developed for network routing and design. The problem of provisioning a virtual private network has been approached through connections with multicommodity flow, leading to approximation algorithms with strong provable performance guarantees. The notion of fairness in resource allocation has been formalized, leading to algorithms that approximate the fairest allocations for a range of network problems. Algorithms have also been designed that deal with input continuously over time, in an event-driven fashion, for the problems of packet routing and load balancing. Finally, combinatorial algorithms have been developed for clustering and partitioning of networks; such algorithms are useful as primitives in a variety of network analysis tasks.