NeTS - NR: Topology Models for Decentralized Random Graphs

Texas A&M Engineering Experiment Station, College Station TX

Investigators

Abstract

National Science Foundation NETS- Research in Network Technologies and Systems CISE/CNS ABSTRACT Proposal Number: 0434940 Principal Investigator: Loguinov, Dmitri Institution: Texas Engineering Experiment Station Proposal Title: NeTS - NR: Topology Models for Decentralized Random Graphs Many 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 Jukan Program Director, CISE/CNS August 4, 2004. .