Evolution, Hierarchy and Modular Organization in Complex Networks

Doctoral Dissertation

Abstract

Large systems in nature and civilization share some important organizing principles uncovered in the framework of complex network research. Here we aim to present a few advances in understanding the generic topological characteristics of these systems. We start with an introduction to basic concepts of network research, continuing with a repertoire of well studied network examples and a brief history of previous modelling efforts. Next, we present a detailed investigation of scientific collaboration networks, with special focus on the role of internal links in determining the networks’s scaling properties, and on limitations of certain measurements imposed by the database.

Many real networks in nature and society share two generic properties: they are scale free and they display a high degree of lustering.

We show that the scale free nature and high clustering of real networks are the consequence of a hierarchical organization, implying that small groups of nodes form increasingly large groups in a hierarchical manner, while maintaining a scale free topology. In hierarchical networks the clustering coefficient follows a strict scaling law, which can be used to identify the presence of a hierarchical organization in real networks. We find that several real networks, such as the World Wide Web, actor network, the Internet at the domain level and the semantic web obey this scaling law, indicating that hierarchy is a fundamental characteristic of many complex systems.

We then focus on the metabolic network of 43 distinct organisms and show that many small, highly connected topological modules combine in a hierarchical manner into larger, less cohesive units, their number and degree of clustering following a power law. Within Escherichia coli we find that the uncovered hierarchical modularity closely overlaps with known metabolic functions. We show that enzyme essentiality is not randomly distributed in the metabolic network, on the contrary, essential enzymes tend to cluster into a few small, well defined modules of the metabolism. Finally, we present an enzyme evolution-based model for metabolic network growth. This model reproduces the observed scale free and hierarchical organization of metabolic networks using local wiring rules.

Attributes

Attribute NameValues
URN
  • etd-09212004-200900

Author Erzs bet Ravasz
Advisor Albert-László Barabási
Contributor Albert-László Barabási, Committee Member
Degree Level Doctoral Dissertation
Degree Discipline Physics
Degree Name PhD
Defense Date
  • 2004-09-20

Submission Date 2004-09-21
Country
  • United States of America

Subject
  • modularity

  • co-authorship network

  • complex networks

  • hierarchical topology

Publisher
  • University of Notre Dame

Language
  • English

Record Visibility Public
Content License
  • All rights reserved

Departments and Units

Files

Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.