A Caltech Library Service

Diversity of graphs with highly variable connectivity

Alderson, David L. and Li, Lun (2007) Diversity of graphs with highly variable connectivity. Physical Review E, 75 (4). Art. No. 046102. ISSN 1539-3755. doi:10.1103/PhysRevE.75.046102.

See Usage Policy.


Use this Persistent URL to link to this item:


A popular approach for describing the structure of many complex networks focuses on graph theoretic properties that characterize their large-scale connectivity. While it is generally recognized that such descriptions based on aggregate statistics do not uniquely characterize a particular graph and also that many such statistical features are interdependent, the relationship between competing descriptions is not entirely understood. This paper lends perspective on this problem by showing how the degree sequence and other constraints (e.g., connectedness, no self-loops or parallel edges) on a particular graph play a primary role in dictating many features, including its correlation structure. Building on recent work, we show how a simple structural metric characterizes key differences between graphs having the same degree sequence. More broadly, we show how the (often implicit) choice of a background set against which to measure graph features has serious implications for the interpretation and comparability of graph theoretic descriptions.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:©2007 The American Physical Society (Received 24 August 2006; published 3 April 2007) The authors thank Daniel Whitney for the use of his implementation of a rewiring algorithm to obtain smin values. The authors gratefully acknowledge John Doyle, Walter Willinger, and Daniel Whitney for many stimulating and insightful discussions. They also thank Aaron Clauset and two anonymous referees for comments that helped to improve the presentation of this work. Both authors were supported at Caltech by Boeing, AFOSR Grant No. URI 49620-01-1-0365 “Architectures for Secure and Robust Distributed Infrastructures,” the Army Institute for Collaborative Biotechnologies, AFOSR Grant No. FA9550-05-1-0032 “Bio Inspired Networks,” and Caltech’s Lee Center for Advanced Networking. D.A.’s work at NPS was supported by Grant No. NIFR-RIPBORYB.
Subject Keywords:complex networks; graph theory; statistics
Issue or Number:4
Record Number:CaltechAUTHORS:ALDpre07
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:8553
Deposited By: Archive Administrator
Deposited On:20 Aug 2007
Last Modified:08 Nov 2021 20:51

Repository Staff Only: item control page