ITR/SY Algorithmic Issues in Large Scale Dynamic Networks

大规模动态网络中的算法问题哈佛大学的Michael Mitzenmacher布朗大学的Eli Upfal我们建议开发一个理论上有充分基础的框架来设计和分析大规模动态网络的算法，特别是对于Web和相关的动态网络，例如底层的Internet拓扑和基于Internet的对等自组织网络。我们计划开发严格的数学模型来捕捉这些网络的关键特征，并能够对这些网络的连通性、信息量和动态性等特征做出可靠的预测。我们计划将这个框架应用于测试现有的算法并构建改进的新算法。开发Web结构和动力学的数学模型的主要好处将是改进的理论基础，用于设计、分析和测试在Web环境中运行的算法。因此，这项工作的具体结果将是可以进行实验验证的模型、基于这些模型的算法分析、从这些分析中受益的新算法，以及最后是概念验证演示和对这些算法的实验评估。

Algorithmic Issues in Large Scale Dynamic NetworksMichael Mitzenmacher, Harvard UniversityEli Upfal, Brown UniversityWe propose to develop a theoretically well-founded framework for thedesign and analysis of algorithms for large scale dynamic networks.In particular, for the Web and related dynamic networks, such as the underlying Internet topology andInternet-based peer to peer ad hoc networks. We plan to develop rigorous mathematical models that capture keycharacteristics and can make reliable predictions about features suchas connectivity, information content, and dynamic of these networks.We plan to apply this framework to test existingalgorithms and construct improved new algorithms.The mail benefits of developing the mathematical models of the Web structure and dynamics will bethe improved theoretical foundation for the design, analysis, andtesting of algorithms that operate in the web environment. The tangible results of this work will therefore be models that can besubjected to experimental verification, analyses of algorithms basedupon these models, new algorithms that benefit from these analyses,and, finally, proof-of-concept demonstrations and experimentalevaluations of such algorithms.