NeTS - NR: Topology Models for Decentralized Random Graphs

国家科学基金会网络技术和系统研究CISE/CNSABSTRACT提案编号：0434940主要研究者：Loguinov，Dmitri机构：得克萨斯工程实验站提案标题：NetS-NR：分散随机图的拓扑模型在真实的世界中发现的许多网络表现出与经典随机图截然不同的特征。例子从社交网络和ISP级互联网到各种蜂窝级图表。除了众所周知的重尾度分布之外，许多自然自演化图还表现出高聚类性和每对节点之间的短平均距离。这是一个长期存在的问题，在科学界使用的算法构造的合成图与真实的网络的属性相似的图形建模。虽然许多不同的拓扑generators和替代理论解释现实世界的图的结构目前共存，其主要缺点在于在图形进化过程中的节点合作的要求，并拥有整个图形在每个时间步的全局知识。为了克服这一局限性，本项目进行了分布式，非合作的图形构造的研究，并提供了一个新的ap-proach建模的许多小世界网络在实践中观察到的。使用随机游走作为主要设计元素，分布式图构造可以自然地导致高水平的聚类和重尾度分布。在这项工作中获得的结果，预计将推进我们的理解的自配置图的性质，并创建可用的模型，将允许各种合成结构，以实现所需的拓扑特性，通过分布式行动的个人用户。Admela Jukan博士项目主任，CISE/CN 2004年8月4日。

National Science FoundationNETS- Research in Network Technologies and Systems CISE/CNSABSTRACTProposal Number: 0434940Principal Investigator: Loguinov, DmitriInstitution: Texas Engineering Experiment StationProposal Title: NeTS - NR: Topology Models for Decentralized Random GraphsMany networks found in the real world exhibit characteristics drastically differ-ent from those of classical random graphs. Examples range from social net-works and ISP-level Internet to various cellular-level graphs. In addition to the well-known heavy-tailed degree distribution, many naturally self-evolving graphs demonstrate high clustering and short average distances between every pair of nodes. It has been a long-standing problem in the scientific community to model such graphs using algorithmic construction of synthetic graphs with properties similar to those of real networks. While many different topology gen-erators and alternative theories explaining the structure of real-world graphs currently co-exist, their main drawback lies in the requirement for the nodes to cooperate during graph evolution and to possess global knowledge of the entire graph at every time step. To overcome this limitation, this project undertakes a study of distributed, non-cooperative graph construction and offers a novel ap-proach to modeling the numerous small-world networks observed in practice. Using random walks as the main design element, the distributed graph con-struction can naturally lead to high levels of clustering and heavy-tailed degree distributions. Results obtained in this work are expected to advance our under-standing of self-configuring graphs in nature and create usable models that will allow various synthetic structures to achieve desired topological properties through distributed actions of individual users. Dr. Admela JukanProgram Director, CISE/CNSAugust 4, 2004..