Flexible Models For Complex Networks

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Complex networks, including communication, economic and social networks, have long been studied due to their fundamental technological, financial and societal significance. Over the last ten years, the dramatic growth of the Internet, the WWW and their applications, has intensified the study of complex networks more than ever. This work isolates parameters, including semantics and incentives, that differentiate the structure and function of distinct applications. This work also develops models capturing features of dynamic and evolving networks, such as online communities. Otbaining accurate models for complex networks is of fundamental significance in simulation, prediction and information retrieval. All the above enhance performance and range of applications. The first generation of models for complex networks involved topologies with skewed statistics and the small world phenomenon. However, in several applications, these features are not adequate. This work develops "flexible models" which generate graphs with a wide variety of further characteristics. In particular, the work develops: (a) Topologies with very low assortativity, such as the ones observed in routing and biological networks. This is accomplished by an extension of the classical Erdos-Gallai and Havel-Hakimi graph algorithms. (b) Networks whose nodes and links capture semantics. In particular, nodes are associated with vectors (one dimension for each relevant attribute), and links are added with probabilities proportional to some vector similarity function (such as the inner product). This is a vast generalization of classical Erdos-Renyi random graphs. (c) Networks formed by selfish agents, which evolve according to incentive-based dynamics. The work also develops algorithms which exploit the special features and structure of the network.