Computational Science Technical Note CSTN-003

CSTN Home

Circuits as a Classifier for Small-World Network Models

A. Leist and K. A. Hawick

Archived March 2004, Revised February 2009

Abstract

The number and length distribution of circuits or loops in a graph or network give important insights into its key characteristics. We discuss the circuit properties of various small-world or scale-free network models generated with different small-world probability parameter values. The small-world properties usually manifest themselves in terms of reduced path-length properties or the set of inter-node distances present in a graph. We show how the number of circuits present can increase or decrease with a larger probability of small-world shortcut links applied, depending upon which model is used. Circuit properties are computationally expensive and we consider counting only a partial circuit distribution and thus being able to use circuits as a classifier for these models in practical cases.

Keywords: circuits; graphs; small-world; scale-free networks

Full Document Text: PDF version.

Citation Information: BiBTeX database for CSTN Notes.

BiBTeX reference:

@INPROCEEDINGS{CSTN-003,
  author = {A. Leist and K. A. Hawick},
  title = {Circuits as a Classifier for Small-World Network Models},
  booktitle = {Proc. WORLDCOMP 2009 International Conference on Foundations of Computer
	Science (FSC 09) Las Vegas, USA.},
  year = {2009},
  number = {CSTN-003},
  month = {13-16 July},
  institution = {Massey University},
  url = {http://www.massey.ac.nz/~kahawick/cstn/003/cstn-003.html}
}


[ CSTN Index | CSTN BiBTeX ]