Shortcut model

﻿
Shortcut model

An important question in statistical mechanics is the dependence of model behaviour on the dimension of the system. The shortcut modelcite journal|author=Shanker, O.|year=2007|title=Graph Zeta Function and Dimension of Complex Network|journal=Modern Physics Letters B|volume= 21(11)|pages=639–644|doi=10.1142/S0217984907013146] cite journal|author=Shanker, O.|year=2007|title=Defining Dimension of a Complex Network |journal=Modern Physics Letters B|volume= 21(6)|pages=321–326|doi=10.1142/S0217984907012773] was introduced in the course of studying this dependence. The model interpolates between discrete regular lattices of integer dimension.

Introduction

The behaviour of different processes on discrete regular lattices have been studied quite extensively. They show a rich diversity of behaviour, including a non-trivial dependence on the dimension of the regular lattice O. Shanker, "Mod. Phys. Lett." B20, 649 (2006).

] D. Ruelle, "Commun. Math. Phys." 9, 267 (1968).

] F. J. Dyson, "Commun. Math. Phys." 12, 91 (1969).

] J. Frohlich and T. Spencer, "Commun. Math. Phys." 84, 87 (1982).

] M. Aizenman, J. T. Chayes, L. Chayes and C. M. Newman, "J. Stat. Phys." 50, 1 (1988).

] J. Z. Imbrie and C. M. Newman, "Commun. Math. Phys." 118, 303 (1988).

] E. Luijten and H. W. J. Blote, "Int. J. Mod. Phys." C6, 359 (1995).

] R. H. Swendson and J.-S. Wang, "Phys. Rev. Lett." 58, 86 (1987).

] U. Wolff, "Phys. Rev. Lett." 62, 361 (1989).

] . In recent years the study has been extended from regular lattices to complex networks. The shortcut model has been used in studying several processes and their dependence on dimension.

Dimension of complex network

Usually, dimension is defined based on the scaling exponent of some property in the appropriate limit. One property one could use is the scaling of volume with distance. For regular lattices $extstyle mathbf Z^d$ the number of nodes $extstyle j$ within a distance $extstyle r\left(i,j\right)$ of node $extstyle i$ scales as $extstyle r\left(i,j\right)^d$.

For systems which arise in physical problems one usually can identify some physical space relations among the vertices. Nodes which are linked directly will have more influence on each other than nodes which are separated by several links. Thus, one could define the distance $extstyle r\left(i,j\right)$ between nodes $extstyle i$ and $extstyle j$ as the length of the shortest path connecting the nodes.

For complex networks one can define the volume as the number of nodes $extstyle j$ within a distance $extstyle r\left(i,j\right)$ of node $extstyle i$, averaged over $extstyle i$, and the dimension may be defined as the exponent which determines the scaling behaviour of the volume with distance. For a vector $extstyle vec\left\{n\right\}=\left(n_1,dots, n_d\right)in mathbf Z^d$, where $extstyle d$ is a positive integer, the Euclidean norm $extstyle |vec\left\{n\right\}|$ is defined as the Euclidean distance from the origin to $extstyle vec\left\{n\right\}$, i.e.,

:$|vec\left\{n\right\}|=sqrt\left\{n_1^2+cdots + n_d^2\right\}.$

However, the definition which generalises to complex networks is the $extstyle L^1$ norm,

:$|vec\left\{n\right\}|_1=|n_1|+cdots +|n_d|.$

The scaling properties hold for both the Euclidean norm and the $extstyle L^1$ norm. The scaling relation is

:$V\left(r\right) = kr^d,$

where d is not necessarily an integer for comlex networks. $extstyle k$ is a geometric constant which depends on the complex network. If the scaling relation Eqn. holds, then one can also define the surface area $extstyle S\left(r\right)$ as the number of nodes which are exactly at a distance $extstyle r$ from a given node, and $extstyle S\left(r\right)$ scales as

:$S\left(r\right) = kdr^\left\{d-1\right\}.$

A definition based on the complex network zeta functioncite journal|author=Shanker, O.|year=2007|title=Graph Zeta Function and Dimension of Complex Network|journal=Modern Physics Letters B|volume= 21(11)|pages=639–644|doi=10.1142/S0217984907013146] generalises the definition based on the scaling property of the volume with distancecite journal|author=Shanker, O.|year=2007|title=Defining Dimension of a Complex Network |journal=Modern Physics Letters B|volume= 21(6)|pages=321–326|doi=10.1142/S0217984907012773] and puts it on a mathematically robust footing.

hortcut model

The shortcut model starts with a network built on a one-dimensional regular lattice. One then adds edges to create shortcuts that join remote parts of the lattice to one another. The starting network is a one-dimensional lattice of $extstyle N$ vertices with periodic boundary conditions. Each vertex is joined to its neighbors on either side, which results in a system with $extstyle N$ edges. The network is extended by taking each node in turn and, with probability $extstyle p$, adding an edge to a new location $extstyle m$ nodes distant.

The rewiring process allows the model to interpolate between a one-dimensional regular lattice and a two-dimensional regular lattice. When the rewiring probability $extstyle p=0$, we have a one-dimensional regular lattice of size $extstyle N$. When $extstyle p=1$, every node is connected to a new location and the graph is essentially a two-dimensional lattice with $extstyle m$ and $extstyle N/m$ nodes in each direction. For $extstyle p$ between $extstyle 0$ and $extstyle 1$, we have a graph which interpolates between the one and two dimensional regular lattices. The graphs we study are parametrized by

:$ext\left\{size\right\} = N,,$:$ext\left\{shortcut distance\right\} = m,,$:$ext\left\{rewiring probability\right\} = p.,$

Application to extensiveness of power law potential

One application using the above definition of dimension was to the extensiveness of statistical mechanics systems with a power law potential where the interaction varies with the distance $extstyle r$ as $extstyle 1/r^alpha$. In one dimension the system properties like the free energy do not behave extensively when $extstyle 0leqalphaleq1$, i.e., they increase faster than N as $extstyle N ightarrowinfty$, where N is the number of spins in the system.

Consider the Ising model with the Hamiltonian (with N spins)

:$H=-frac\left\{1\right\}\left\{2\right\}sum_\left\{i,j\right\}J\left(r\left(i,j\right)\right)s_\left\{i\right\}s_\left\{j\right\}$

where $extstyle s_\left\{i\right\}$ are the spin variables, $extstyle r\left(i,j\right)$ is the distance between node $extstyle i$ and node $extstyle j$, and $extstyle J\left(r\left(i,j\right)\right)$ are the couplings between the spins. When the $extstyle J\left(r\left(i,j\right)\right)$ have the behaviour $extstyle 1/r^alpha$, we have the power law potential. For a general complex network the condition on the exponent $extstyle alpha$ which preserves extensivity of the Hamiltonian was studied. At zero temperature, the energy per spin is proportional to

:$ho=sum_\left\{i,j\right\}J\left(r\left(i,j\right)\right),$

and hence extensivity requires that $extstyle ho$ be finite. For a general complex network $extstyle ho$ is proportional to the Riemann zeta function $extstyle zeta \left( alpha - d + 1\right)$. Thus, for the potential to be extensive, one requires

:$alpha > d.,$

Other processes which have been studied are self-avoiding random walks, and the scaling of the mean path length with the network size. These studies lead to the interesting result that the dimension transitions sharply as the shortcut probability increases from zerocite journal|author=O. Shanker, |year=2008|title=Algorithms for Fractal Dimension Calculation|journal=Modern Physics Letters B|volume= 22|pages=459–466|doi=10.1142/S0217984908015048] . The sharp transition in the dimension has been explained in terms of the combinatorially large number of available paths for points separated by distances large compared to 1.

Conclusion

The shortcut model is useful for studying the dimension dependence of different processes. The processes studied include the behaviour of the power law potential as a function of the dimension, the behaviour of self-avoiding random walks, and the scaling of the mean path length. It may be useful to compare the shortcut model with the small-world network, since the definitions have a lot of similarity. In the small-world network also one starts with a regular latticeand adds shortcuts with probability $extstyle p$. However, the shortcuts are not constrained to connect to a node a fixed distance ahead.Instead, the other end of the shortcut can connect to any randomlychosen node. As a result, the small world model tends to a randomgraph rather than a two-dimensional graph as the shortcut probabilityis increased.

References

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Elaboration likelihood model — The elaboration likelihood model (ELM) of persuasion (Petty Cacioppo, 1986) is a model of how attitudes are formed and changed (see also attitude change). Central to this model is the elaboration continuum , which ranges from low elaboration (low …   Wikipedia

• List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

• Complex network zeta function — Different definitions have been given for the dimension of a complex network or graph. For example, metric dimension is defined in terms of the resolving set for a graph. Dimension has also been defined based on the box covering method applied to …   Wikipedia

• Wikipedia:Articles for creation — Shortcut: WP:AFC For the WikiProject, see Wikipedia:WikiProject Articles for creation. Welcome to Wikipedia s page for Articles for Creation. If you do not have a Wikipedia user account but have an idea and sources for a new article, you can… …   Wikipedia

• Portal:Speculative fiction — Shortcut: P:SF …   Wikipedia

• Portal:Star — Shortcut: P:STR The Star Portal Wikipedia portals: Culture Geography Health History …   Wikipedia

• Shear Genius (season 1) — The first season of Shear Genius aired on Bravo from April to May 2007. Contestants*Anthony, 40, from Manhattan Beach, California (originally from Hertfordshire, England) *Ben, 32, from Chicago, Illinois *Daisy, 31, from Hialeah, Florida *Danna,… …   Wikipedia

• iOS version history — Contents 1 Overview 2 Versions 2.1 Unreleased versions …   Wikipedia

• Visual Basic for Applications — (VBA) Paradigm(s) Multi paradigm Appeared in 1993 Developer Microsoft …   Wikipedia

• Wubi method — The Wubizixing input method (zh stpl|s=五笔字型输入法|t=五筆字型輸入法|p=wǔbǐ zìxíng shūrùfǎ|l=five stroke character model input method), often abbreviated to simply Wubi or Wubi Xing [This is the name used in Mac OS X] , is a Chinese character input method… …   Wikipedia