Exploring the assortativity-clustering space of a network’s degree sequence

Petter Holme and Jing Zhao
Phys. Rev. E 75, 046111 – Published 19 April 2007

Abstract

Nowadays there is a multitude of measures designed to capture different aspects of network structure. To be able to say if a measured value is expected or not, one needs to compare it with a reference model (null model). One frequently used null model is the ensemble of graphs with the same set of degrees as the original network. Here, we argue that this ensemble can give more information about the original network than effective values of network structural quantities. By mapping out this ensemble in the space of some low-level network structure—in our case, those measured by the assortativity and clustering coefficients—one can, for example, study where in the valid region of the parameter space the observed networks are. Such analysis suggests which quantities (or combination of quantities) are actively optimized during the evolution of the network. We use four very different biological networks to exemplify our method. Among other things, we find that high clustering might be a force in the evolution of protein interaction networks. We also find that all four networks are conspicuously robust to both random errors and targeted attacks.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
1 More
  • Received 6 November 2006

DOI:https://doi.org/10.1103/PhysRevE.75.046111

©2007 American Physical Society

Authors & Affiliations

Petter Holme

  • Department of Computer Science, University of New Mexico, Albuquerque, New Mexico 87131, USA

Jing Zhao

  • School of Life Sciences & Technology, Shanghai Jiao Tong University, Shanghai 200240, China; Shanghai Center for Bioinformation and Technology, Shanghai 200235, China; and Department of Mathematics, Logistical Engineering University, Chongqing 400016, China

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 75, Iss. 4 — April 2007

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×