Deterministic Small-World Graphs
F. Comellas
Departament de Matemàtica Aplicada IV; Universitat Politècnica
de Catalunya
Int. Conf. on Dynamical Networks in Complex Systems in Kiel/Germany
(July 25-27).
Europhysics Conference Abstracts, vol 25F pp. 18 (2001) .
A small-world graph has a relatively low diameter, with respect to
a regular graph with the same number of vertices and
edges, and a large clustering (vertices have many mutual neighbors)
in relation to a random graph also with the same number of vertices and
edges. Small-world graphs are of considerable interest because they model
important real life networks as
the WWW, transportation and communication networks, or even the neural
system of the worm {\it C. Elegans} and social networks like the graph
associated to the Erd\H{o}s number [D.J. Watts and S.H. Strogatz, Nature
393, 440 (1998)].
While most of the work for these graphs is based on random graphs and
computer simulations, this approach has shown to be quite limited for describing
the accumulation of new results and the emergence of unexpected phenomena.
We show that standard graph theory concepts provide simple
models for an exact determination of characteristic parameters of small-world
graphs. Graph compounding, domination theory or algebraic graph theory
give a deep mathematical insight to better understand these structures.
With these approaches we obtain deterministic small-world graphs (including
regular graphs), that match former simulations [F. Comellas, J. Oz\'on
and J.G. Peters, Inf. Proc. Lett., 76, 83 (2000)]and we show that it is
always possible to obtain a small-world graph, starting from any
graph with a relatively large diameter, by interconnecting a certain subset
of vertices [F. Comellas, J. Oz\'on, submitted]. We have also obtained
deterministic small-world models which support any degree distribution
[F. Comellas and M. Sampels, submitted] and we have easily shown,
for example, that the power law distribution for the eigenvalues of the
WWW [M. Faloutsos et al., Comput. Comm. Rev. 29, 251 (1999)] is a simple
consequence of the degree distribution [F. Comellas, in preparation].
Finally, the introduction of a deterministic parameterized model allows
us to study variants of broadcasting in small-world graphs and model the
propagation of computer viruses and cascaded network failures [F. Comellas,
M. Mitjana and J.G. Peters, submitted]. The results derived are similar
to previous probabilistic results about the spread of contagious
diseases in populations.
Load PDF