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:
To appear in Proc. 2009 International Conference on Foundations of Computer Science (FCS'09), 13-16 July 2009, Las Vegas, USA.