Volume 77, Number 1, January 2007
Article Number 18004
Number of page(s) 5
Section Interdisciplinary Physics and Related Areas of Science and Technology
Published online 03 January 2007
EPL, 77 (2007) 18004
DOI: 10.1209/0295-5075/77/18004

$\mth{K}$-scaffold subgraphs of complex networks

B. Corominas-Murtra1, S. Valverde1, C. Rodríguez-Caso1 and R. V. Solé1, 2

1  ICREA-Complex Systems Lab, Universitat Pompeu Fabra - Dr. Aiguader 80, 08003 Barcelona, Spain
2  Santa Fe Institute - 1399 Hyde Park Road, NM 87501, USA

received 4 August 2006; accepted in final form 9 November 2006; published January 2007
published online 3 January 2007

Complex networks with high numbers of nodes or links are often difficult to analyse. However, not all elements contribute equally to their structural patterns. A small number of elements (the hubs) seem to play a particularly relevant role in organizing the overall structure around them. But other parts of the architecture (such as hub-hub connecting elements) are also important. In this letter we present a new type of substructure, to be named the K-scaffold subgraph, able to capture all the essential network components. Their key features, including the so-called critical scaffold graph, are analytically derived.

89.75.Fb - Structures and organization in complex systems .
05.70.Jk - Critical point phenomena .
64.60.Ak - Renormalization-group, fractal, and percolation studies of phase transitions .

© Europhysics Letters Association 2007