NeTS - NR: Topology Models for Decentralized Random Graphs

NeTS - NR：去中心化随机图的拓扑模型

• 批准号: 0434940
• 负责人: Dmitri Loguinov
• 金额: --
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0434940&HistoricalAwards=false
• 关键词: NeTS; NR; Topology; Models; Decentralized

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..

国家科学基金会NETS-网络技术和系统研究CEISE/CNSABSTRACT建议编号：0434940主要调查者：Loguinov，DmitriInstitution：德克萨斯工程实验站建议标题：NETS-NR：分散随机图的拓扑模型现实世界中发现的许多网络表现出与经典随机图截然不同的特征。示例范围从社交网络和isp级别的互联网到各种蜂窝级别的图表。除了众所周知的重尾度分布外，许多自然进化图还表现出高聚集度和每对节点之间的短平均距离。使用具有与真实网络相似的属性的合成图的算法构造来对这样的图进行建模一直是科学界的一个长期问题。虽然目前存在许多不同的拓扑生成器和解释现实世界图结构的替代理论，但它们的主要缺点在于要求图的节点在图的进化过程中进行协作，并在每个时间步拥有整个图的全局知识。为了克服这一局限性，本项目开展了分布式、非协作图构造的研究，并提供了一种新的方法来对实际观察到的大量小世界网络进行建模。以随机游走为主要设计元素的分布式图结构，自然会产生高水平的聚类性和重尾度分布。这项工作的结果有望加深我们对自然界中自配置图的理解，并创建有用的模型，允许各种合成结构通过个体用户的分布式操作来获得所需的拓扑性质。Admela Jukan博士，项目主任，CEISE/CNS2004年8月4日