text:
# 1 Introduction

## 1 Introduction

The $`SU(5)`$ model unifies the strong, weak, and electromagnetic interactions in the smallest simple group. It has many other attractive features which are well recognized. But it suffers from the following two major difficulties which are actually generic to the idea of grand unification itself. (i) Because quarks and leptons reside in unified multiplets and there are B- and L-violating interactions, gauge boson exchanges can result in proton decay. If these gauge bosons are appropriately heavy, the decay rate will be very small. Their masses, in the usual formulation, are, however, not arbitrary but rather determined by the scale where the different gauge couplings unify. The proton decay lifetime is therefore a robust prediction of the model. No experimental signature of proton decay has been found yet and the model is disfavoured. More complicated unification models involving several intermediate mass-scales can evade this problem. (ii) The low energy Higgs doublet, responsible for electroweak breaking, is embedded in a 5 representation of $`SU(5)`$. The other members of this multiplet are color triplet scalars which must have a mass near the unification scale – since no such scalars have been observed at the electroweak scale. This leads to an unnatural mass splitting among the members of the same $`SU(5)`$ multiplet. This is termed the double-triplet splitting problem.

These two unwelcome features of the $`SU(5)`$ model can be tackled in an elegant way if unified $`SU(5)`$ symmetry exists in a 5-D world. Low energy 4-D $`SU(3)_c\times SU(2)_L\times U(1)_Y`$ symmetry is recovered when the extra dimension is compactified on a $`S^1/(Z_2\times Z_2^{})`$ orbifold. This situation is realized when space-time is considered to be factorized into a product of 4D Minkowski space-time $`M^4`$ and the orbifold $`S^1/(Z_2\times Z_2^{})`$. The coordinate system consists of $`x^\mu =(x^0,x^1,x^2,x^3)`$ and $`y=x^5`$. There are two distinct 4-D branes; one at $`y=0`$ and another at $`y=\pi R/2`$. On the $`S^1`$, $`y`$=0 is identified with $`y=\pi R`$ ($`Z_2^{}`$ symmetry) while $`y=\pm \pi R`$/2 are identified with each other ($`Z_2`$ symmetry).

As is common in models of this type, we assume that the fermions are located in the 4-D brane at $`y=0`$ while the gauge bosons and the scalars are allowed to travel in the bulk. The discrete $`Z_2`$ and $`Z_2^{}`$ symmetries, which we refer to as $`P`$ and $`P^{}`$, permit the expansion of any 5-D field $`\varphi `$ in the following mode expansions according to whether they are even or odd under ($`P,P^{}`$):

$$\begin{array}{cccc}\varphi _{++}(y)& =& \sqrt{\frac{2}{\pi R}}_{n=0}^{\mathrm{}}\varphi _{++}^{(2n)}\mathrm{cos}\frac{2ny}{R};& M_n=\frac{2n}{R}\\ \varphi _+(y)& =& \sqrt{\frac{2}{\pi R}}_{n=0}^{\mathrm{}}\varphi _+^{(2n+1)}\mathrm{sin}\frac{(2n+1)y}{R};& M_n=\frac{2n+1}{R}\\ \varphi _+(y)& =& \sqrt{\frac{2}{\pi R}}_{n=0}^{\mathrm{}}\varphi _+^{(2n+1)}\mathrm{cos}\frac{(2n+1)y}{R};& M_n=\frac{2n+1}{R}\\ \varphi _{}(y)& =& \sqrt{\frac{2}{\pi R}}_{n=0}^{\mathrm{}}\varphi _{}^{(2n+2)}\mathrm{sin}\frac{(2n+2)y}{R};& M_n=\frac{2n+2}{R}\end{array}$$

Here $`n=0,1,2,\mathrm{}`$ and we have suppressed the $`x^\mu `$ dependence. The behaviour of the fields under $`P`$ and $`P^{}`$ can be read off from the subscripts in the left hand side above. For example, $`\varphi _+`$ is odd under $`P`$ and even under $`P^{}`$. We have also listed the masses of the different modes. Notice that only the $`\varphi _{++}`$ field can have a massless mode. One of the prime motivations of these higher dimensional $`SU(5)`$ models is to ensure doublet-triplet splitting within the 5 scalar multiplet of $`SU(5)`$ and to ensure that from within the adjoint representation (24) of the gauge bosons only the $`SU(3)_c\times SU(2)_L\times U(1)_Y`$ gauge bosons remain massless. Both can be achieved by ascribing $`P,P^{}`$ parities of $`++`$ to the (1,2,1/2) submultiplet in the 5 while the remaining (3,1,–1/3) states carries $`+`$ parity111Here we are using the decomposition of the $`SU(5)`$ multiplets under $`SU(3)_c\times SU(2)_L\times U(1)_Y`$.. For the sake of completeness, the decomposition of the $`SU(5)`$ representations upto 75 are listed in Table (1) . Since $`P,P^{}`$ commute with the Standard Model (SM) gauge symmetry $`SU(3)_c\times SU(2)_L\times U(1)_Y`$, the $`Z_2\times Z_2^{}`$ parities for the members of the higher $`SU(5)`$ multiplets can be built up from this assignment for the scalars in the fundamental representation222In principle, one can assign arbitrary $`Z_2\times Z_2^{}`$ parities to the submultiplets of the higher SU(5) representations. However, to reduce adhocness, here we work with the ansatz that once we assign the parities for the fundamental representation, those for the submultiplets of higher $`SU(5)`$ representations are determined by group theoretic relationships.. These parities have been indicated in Table (1). In this way we can also assure that the (1,1,1)+(1,3,0)+(8,1,0) multiplets of $`\mathrm{𝟐𝟒}`$ remain massless, breaking $`SU(5)`$ symmetry below the compactification scale $`1/RM_X`$.

Above $`M_X`$, the mass scale of the non-SM gauge bosons, $`X,Y`$, and that of the colour triplet scalars in the 5 representation, $`SU(5)`$ symmetry is unbroken. This scale is determined in our analysis by the unification of the three SM gauge couplings. We assume one intermediate scale, $`M_I`$, such that all scalars which are permitted to have a zero mode, excepting the SM scalar doublet, pick up a mass at this scale. We include their contributions to the beta functions of the one loop renormalization group equations (RGE) and solve for both the intermediate scale $`M_I`$ and the unification scale $`M_X`$. The beta function coefficients are given by:

$`b_i`$ $`=`$ $`\left(\begin{array}{c}0\\ 22/3\\ 11\end{array}\right)+n_f\left(\begin{array}{c}4/3\\ 4/3\\ 4/3\end{array}\right)+T_s^i/3`$ (1)
We take $`n_f=3`$. The above expression assumes that the scalar fields are complex. For real scalar fields one has to use $`T_s^i/6`$ in Eqn. (1). The $`T_s^i`$ for the light scalar submultiplets of the different $`SU(5)`$ representations upto 75 are listed in Table (2).

Defining $`m_{k,l}=\mathrm{ln}(m_k/m_l)`$ and $`b_{k,l}^i`$ to be the $`\beta `$ coefficients governing evolution in the range $`m_km_l`$, we get the following three solutions of the RGE.

$$2\pi \alpha _i^1(M_Z)=2\pi \alpha _X^1+b_{X,I}^im_{X,I}+b_{I,Z}^im_{I,Z}$$
(2)
Using the values of couplings at the low energy scale $`M_Z`$

$$\alpha _1(M_Z)=0.01688,\alpha _2(M_Z)=0.03322,\alpha _3(M_Z)=0.117$$
(3)
we solve the three equations in Eqn. (2). First, we present a simple illustrative example below.

## 2 Simple example

Because the GUT symmetry is broken via orbifolding, let us consider the case where there are only 5-plets of $`SU(5)`$ Higgs scalars at the unification scale and assume that there are $`n_5`$ of them. Then compactification allows only doublets to be light and not their triplet partners. In this case the $`\beta `$ coefficients are given by,

$`b_{X,I}^i=\left(\begin{array}{c}41/10\\ 19/6\\ 7\end{array}\right)+{\displaystyle \frac{n_5}{3}}\left(\begin{array}{c}3/10\\ 1/2\\ 0\end{array}\right)`$ (4)
Solving Eqn. (2) we obtain

$$\alpha _X^1=38.53,m_{I,Z}=26.98194.75/n_5,m_{X,I}=194.75/n_5$$
(5)
Because $`m_{I,Z}0`$ we obtain $`n_58`$. For the case of $`n_5=8`$ we get,

$$M_I=1.39\mathrm{TeV},M_X=5.0\times 10^{10}\mathrm{TeV}.$$
(6)
The GUT scale $`M_X`$ is rather low but it is consistent with proton decay because of the existence of $`Z_2\times Z_2^{}`$ parity. Note that the intermediate scale is in a very attractive region phenomenologically. Eight Higgs doublets can be degenerate at this scale of 1.3-1.4 TeV. They may play an important role in the fermion mass puzzle. Further, the scale $`M_X10^{10}`$ TeV is interesting from the point of view of the see-saw mechanism. The unification pattern is shown in Fig. (1).

## 3 More general cases

We now turn to the more general possibility where scalars in higher representations of $`SU(5)`$ are present. The light scalars of all $`SU(5)`$ multiplets upto 75 and their contributions to the beta coefficients are listed in Table (2).

### 3.1 Small number of representations and low intermediate scales

We consider upto the 75 dimensional representation of $`SU(5)`$ and demand that the threshold scale, $`M_I`$, be less than 10 TeV. For the sake of economy, we also consider only those solutions where for every representation $`R`$, the number $`n_R`$ is either 0 or 1. If we do not put any restriction on the number of representations, but maintain that $`n_R`$ be zero or unity only, then we get 43 different solutions. In Table (3) we list those solutions for which not more than two $`n_R`$ are non-zero.

Though the intermediate scales, $`M_I`$, and the unification scales, $`M_X`$, in the last two cases are the same, the value of $`\alpha _X`$ turns out to be 0.037 and 0.710, respectively.

Let us explain one case in more detail. Let there be only 35-plets of $`SU(5)`$ at the unification scale and assume that there are $`n_{35}`$ of them. Then compactification allows only (1,4,–3/2) \+ ($`\overline{6}`$,2,1/6) fields at low energy. In this case the $`\beta _i`$ coefficients are given by,

$$b_{X,I}^i=\left(\begin{array}{c}41/10\\ 19/6\\ 7\end{array}\right)+\frac{n_{35}}{3}\left(\begin{array}{c}28/5\\ 8\\ 5\end{array}\right)$$
(7)
Solving the RGE we obtain

$$\alpha _X^1=32.72,m_{I,Z}=28.2027.3073/n_{35},m_{X,I}=27.3073/n_{35}$$
(8)
Because $`m_{I,Z}0`$ we obtain $`n_{35}1`$. For the case of $`n_{35}=1`$ we get,

$$M_I=0.223\mathrm{TeV},M_X=1.6\times 10^{11}\mathrm{TeV}.$$
(9)
### 3.2 Low dimensional representations only

Another alternative which we examine is by restricting to $`SU(5)`$ representations upto 24 subject further to the requirements $`n_5<8,n_{10}<5,n_{15}<5,n_{24}<5`$. Then we get the results given in Table (4) when we impose $`M_I<70`$ TeV. The unification patterns of the gauge couplings for a few sample cases are shown in Fig. (1).

## 4 Remarks about $`SO(10)`$

It might be of interest to extend this analysis to grand unification groups of higher rank. It is readily seen that the solutions will become more difficult to come by. For example, we give in Table (5) the $`SU(5)`$ contents of the $`SO(10)`$ representations upto 126. Notice, that the inclusion of a single 126 of $`SO(10)`$ is equivalent to the simultaneous presence of $`\overline{\mathrm{𝟓}}`$, 10, $`\overline{\mathrm{𝟏𝟓}}`$, 45, $`\overline{\mathrm{𝟓𝟎}}`$ repesentations of $`SU(5)`$ and there is no flexibility of including the $`SU(5)`$ representations individually.

If we permit all SO(10) representations upto 126 and consider no more than upto 8 of any single representation then we find just two allowed solutions:

1) $`n_{10}=8`$, other $`n_i=0M_I`$ = 1.68 TeV, $`M_X`$ = 4.67 $`\times 10^{10}`$ TeV

2) $`n_{10}=6`$, $`n_{16}=1`$, other $`n_i=0M_I`$ = 295 TeV, $`M_X`$ = 7.99 $`\times 10^9`$ TeV

## 5 Conclusions and Discussion

In this work, we have examined the light scalar modes that survive when a 5-dimensional $`SU(5)`$ model reduces to the 4-dimensional SM through the orbifold compactification route. The scalars which are permitted to have zero modes are assumed to pick up a mass at some scale $`M_I`$ intermediate between the electroweak and Planck scales. They contribute to the beta coefficients in the $`M_I<\mu <M_X`$ regime. The compactification scale, $`M_X`$, above which $`SU(5)`$ is unbroken, is determined by the unification of the gauge couplings. This analysis also determines $`M_I`$. We identify solutions for which $`M_I`$ is in an interesting phenomenological range and can be probed at the next generation colliders. This analysis is somewhat similar in spirit to the approach chosen for supersymmetric-GUTs where the SUSY scale is fixed by gauge unification.

It is seen from Table (2) that $`P`$ is (+) for all the multiplets. Thus it does not play any role in the present analysis. However, we would like to keep the option of generalizing this method to the supersymmetric case where $`P`$ has a non-trivial role.

The scale of degenerate scalars, $`M_I`$, should be treated as an approximate one in the sense that in reality some spread in the masses around it can be expected. The standard model doublet has a mass at the electroweak scale. This should not be viewed as an unnatural fine tuning as some relevant Yukawa couplings can be of order $`10^210^3`$.

When the unification symmetry is assumed to be of higher rank, then the number of acceptable solutions reduces dramatically. For $`SO(10)`$ just two solutions can be obtained, so long as we stick to the low dimensional representations of the symmetry group.

At first sight it might seem that we are introducing too many scalar degrees of freedom. However, this appears less dramatic when we compare it to the Minimal Supersymmetric Standard Model where too a large number of scalars are required.

Acknowledgements: This work was done while both authors were visiting the Abdus Salam International Centre for Theoretical Physics, Italy. They are grateful to the High Energy Section and the Associateship Office of the Centre for hospitality. The research of AR is supported by CSIR, India.


format: text

text:
# Aging and Energy Landscapes: Application to Liquids and Glasses

Present address: \] Laboratoire de Physique Theorique des Liquides, Universite Pierre et Marie Curie , 4 place Jussieu, Paris 75005, France

## Abstract

The equation of state for a liquid in equilibrium, written in the potential energy landscape formalism, is generalized to describe out-of-equilibrium conditions. The hypothesis that during aging the system explores basins associated to equilibrium configurations is the key ingredient in the derivation. Theoretical predictions are successfully compared with data from molecular dynamics simulations of different aging processes, such as temperature and pressure jumps.

Glasses are out-of-equilibrium (OOE) systems, characterized by slow dynamical evolution (aging) and history dependent properties. Their thermodynamic and dynamic properties depend on the preparation method (cooling or compression schedules) as well as the time spent in the glass phase pablobook . The extremely slow aging dynamics has often been considered an indication that a thermodynamic description of the glass state can be achieved by adding one or more history-dependent parameters to the equation of state (EOS) tool ; davies ; kovacs ; McKenna ; speedy ; kurchan ; teo ; angellmckenna ; franz ; leuzzi . Recent theoretical work — mostly based on mean field models of structural glasses, where analytic solutions of the OOE dynamics can be explicitly worked out cugliandolo  — supports such possibility.

In this Letter we derive an EOS for OOE conditions, based on a generalization of the potential energy landscape (PEL) thermodynamic approach sw ; debenedetti01 ; sastry2001 . The EOS is derived under the hypothesis that during aging the system explores basins associated with equilibrium configurations, a condition which, as shown later, is simple to implement in the PEL context. The proposed EOS for OOE conditions depends on one additional parameter, which for example can be chosen to be the average depth of the explored local minima of the PEL (the so-called inherent structures (IS) sw ; debenedetti01 ). The EOS allows for the first time a detailed comparison between predictions and “exact results” from out-of-equilibrium molecular dynamics simulations. We report such a comparison for a realistic model of the fragile liquid orthoterphenyl, one of the most studied glass forming liquids toelle .

The PEL formalism sw ; debenedetti01  allows for a clear separation of vibrational and configurational contributions in thermodynamical quantities. Indeed, the equilibrium liquid free energy $`F(T,V)`$ at temperature $`T`$ and volume $`V`$ is expressed as a sum of a vibrational contribution $`f_{vib}`$, representing the intra-basin free energy sw , and a configurational contribution ($`TS_{conf}+e_{IS}`$). Here the configurational entropy $`S_{conf}`$ accounts for the number of explored basins of the PEL of average energy depth $`e_{IS}`$. $`f_{vib}`$, for a system of $`N`$ atoms, depends on the curvature of the potential energy surface, i.e., on the $`3N`$ eigenvalues $`\omega _i^2`$ of the Hessian matrix evaluated at the IS. Recently, calculating the $`V`$ derivative of $`F(T,V)`$, an analytic EOS has been derived, based only on the statistical properties of the landscape lanave02 ; deben .

The separation in vibrational and configurational parts can be carried out for several properties. In our case, it is particularly useful to separate the instantaneous pressure as sum of two contributions: the pressure felt by the system in the inherent structure configuration ($`P_{IS}`$), and an additional contribution related to the finite temperature, which we refer to as the vibrational contribution ($`P_{vib}`$clarification

$$P(T,V,e_{IS})=P_{IS}(e_{IS},V)+P_{vib}(T,V,e_{IS}).$$
(1)
In equilibrium $`e_{IS}`$ is a well defined function of $`T`$ and $`V`$ and, as well known, $`P`$ depends only on $`T`$ and $`V`$. Note that $`P_{IS}`$, being the pressure experienced by the liquid in the IS, depends only on the basin’s depth and on $`V`$. Instead, $`P_{vib}`$ depends on the basin’s depth as well as on $`T`$ and $`V`$ precisazione .

For models for which the statistical properties of the PEL, i.e., the distribution of shapes and numbers of $`IS`$ lanave02 ; deben  are known, $`P_{IS}`$ and $`P_{vib}`$ can be calculated theoretically. In other cases, $`P_{IS}`$ and $`P_{vib}`$ can be calculated numerically. In all cases, an landscape-based EOS based on Eq. (1) can be derived.

The separation of the pressure in two contributions is crucial for the possibility of extending the equilibrium EOS to OOE conditions, since it provides a direct way to rebuild the pressure once $`T`$, $`V`$ and $`e_{IS}`$ are known. In the PEL formalism, the hypothesis that the system explores basins associated with typical equilibrium configurations, i.e., configurations sampled in equilibrium conditions, is equivalent to assuming that the relations — calculated in equilibrium — linking $`P_{IS}`$ and $`P_{vib}`$ to $`e_{IS}`$ and $`V`$ are valid also in OOE conditions. If this is the case, the knowledge of $`e_{IS}`$, $`T`$ and $`V`$ is sufficient to calculate both $`P_{IS}`$, $`P_{vib}`$ and their sum $`P`$ according to Eq. (1).

Similarly, the values of $`P`$, $`T`$ and $`e_{IS}`$ are sufficient to predict $`V`$, since both $`P_{IS}(e_{IS},V)`$ and $`P_{vib}(e_{IS},T,V)`$ can be estimated as a function of $`V`$. The predicted $`V`$ is the value for which $`P_{IS}(e_{IS},V)+P_{vib}(e_{IS},T,V)`$ matches the external pressure.

Next we apply the ideas discussed above to a system of $`N=343`$ molecules interacting via the Lewis and Wanström (LW) model for the fragile molecular liquid orthoterphenyl (OTP) mossa02 ; lewis . The LW model is a rigid three-site model, with intermolecular site-site interactions modeled by the Lennard-Jones (LJ) potential lewis . We refer to Ref. mossa02  for all numerical details. An equilibrium EOS, based on the assumption of a Gaussian landscape, has been recently presented for this model lanave02 , and successfully compared with the “exact” EOS calculated from molecular dynamics simulations.

Fig. 1 shows the relation between $`P_{IS}`$ and $`e_{IS}`$ in equilibrium along different isochores and $`P_{vib}`$ as a function of $`T`$ for the LW model. Both quantities can be parameterized in a quite accurate way. Indeed, for this model, $`P_{vib}`$ is weakly dependent on $`V`$ and $`e_{IS}`$ and it is well represented by a linear $`T`$-dependence. The parameterization of $`P_{IS}`$ and $`P_{vib}`$ offers the possibility of estimating the system pressure once $`T`$, $`V`$ and $`e_{IS}`$ are known.

We study four different OOE protocols via computer simulation. The imposed external conditions are illustrated in Fig. 2. We study i) a $`T`$-jump at constant $`V`$; ii) a $`P`$-jump at constant $`T`$; iii) a $`P`$-jump at constant $`T`$ in the glass phase and iv) an isobaric heating of a glass. For the cases i) and ii), conditions are chosen in such a way that within the simulation time window (50 $`ns`$) the system reaches the equilibrium state. In all studied cases, averages over 50 independent simulations have been performed.

Case (i). — Fig. 3 shows the comparison between the theoretical predictions and the numerical results for the constant-$`V`$ $`T`$-jump case. The $`e_{IS}`$ values, calculated from the simulation (Fig. 3(a)), are used together with the values of $`T`$ and $`V`$ as input to predict the evolution of $`P`$ (Fig. 3(b)). Figs. 3(c) and (d) also show the comparison for $`P_{IS}`$ and $`𝒲`$. $`𝒲(e_{IS})`$, defined as $`_{i=1}^{3N}\mathrm{ln}(\omega _i(e_{IS}))`$, provides an indication of the similarity in basin shape (at the level of the harmonic approximation) between basins explored in equilibrium and in OOE conditions. The quality of the predictions indeed supports the validity of the EOS and the hypothesis that the basins sampled during aging have the same relationship $`𝒲(e_{IS})`$ as in equilibrium.

Case (ii). — Fig. 4 shows the evolution of the system after a constant-$`T`$ pressure jump. In this case, the $`e_{IS}`$ values calculated from the simulation are used together with the values of $`T`$ and $`P`$ as input to successfully predict the evolution of $`V`$. For times shorter than $`20ps`$, the barostat time constant, the fast increasing external pressure forces the system to change the volume with a solid-like response. In this time window, the initial basins in configuration space are continuously deformed by the rapid volume change, in agreement with the findings of Ref. lacks . For time longer than $`20ps`$, when the external pressure has reached the equilibrium value, the system starts to explore basins different from the (deformed) original ones, and the time evolution becomes controlled by the aging kinetics. To support this interpretation we show in Fig. 4(e) the actual path in the $`e_{IS}`$-$`P_{IS}`$ plane, where the change around $`20ps`$ is clearly evidenced.

Cases (iii) and (iv). — The last two cases are respectively a constant $`T`$ $`P`$-jump and a heating at constant $`P`$ (with an heating rate of $`1K/ps`$), both starting from glass configurations. These initial configurations are generated by rapid constant-$`V`$ quenches of equilibrium configurations, as shown schematically in Fig. 2. Fig. 5 shows the comparison between the theoretical predictions and the numerical calculations for $`V`$, using $`e_{IS}`$ as input. In the case of a $`P`$-jump (Fig. 5-Top), again two different dynamical behaviors are observed: a fast dynamics process describing the mechanical response of the glass to the external pressure change, followed by an extremely slow aging dynamics, during which basin changes are taking place. In both cases and for all times, the out-of-equilibrium EOS is able to predict quantitatively the $`V`$ changes.

In summary, we have derived an extension of the PEL equation of state to model the thermodynamic properties of liquids under out-of-equilibrium conditions. Such an extension — based on the hypothesis that an aging system evolves through regions of configuration space which are typically sampled in equilibrium — requires an additional thermodynamic parameter which, for convenience, we have associated with the IS energy of the explored basins.

The results reported in this Letter (Figs. 3-5) show that the proposed generalization of the PEL equation of state is successful in predicting out-of-equilibrium thermodynamics, at least under the conditions and time scales probed by state-of-the-art numerical simulations. Larger $`T`$ or $`P`$ jumps and/or longer aging time could require a more detailed thermodynamic description, with more than one additional parameter. Despite such a possibility, the energy landscape approach developed in this Letter is a promising starting point for looking into more complex problems in the physics of OOE liquids and glasses.

We thank A. Angell, P. Debenedetti, T. Keyes, L. Leuzzi, G. McKenna, G. Ruocco, S. Sastry, A. Scala, and M. Yamada for discussions and comments. We acknowledge support from MIUR-COFIN 2000, INFM-PRA and INFM Initiative Parallel Computing.


text:
# The favoured cluster structures of model glass formers

## I Introduction

There is still much to learn about the nature of the glass transition,Angell (2000) and so it is an area of intense current interest. One of the increasingly prominent avenues of research in this field is the computational study of model supercooled liquids and glasses,Debenedetti and Stillinger (2001) driven by the increase in computational power that has allowed larger systems to be studied over longer time scales. The advantage of the computational approach is that the configuration of the liquid or glass is directly available, potentially making it possible to understand the basis of the changes that occur as the glass transition is approached in terms of the structure and energy landscape. Indeed, this mode of research has led to an increasing number of new insights, for example, into the relationship between the energy landscape and the properties of supercooled liquidsSastry et al. (1998); Sciortino et al. (1999) (in particular the fragilitySastry (2001)), the mechanisms of cooperative motion,Donati et al. (1998) the growing length scale of correlated motion as the temperature is decreasedBennemann et al. (1999) and whether a thermodynamic transition underlies the glass transition.Santen and Krauth (2000)

One of the basic requirements of a model system to study supercooled liquids and glasses is that it will not crystallize on the relevant time scales. This constraint precludes the use of a monatomic system interacting with simple pair potentials, such as the Lennard-Jones potential, because crystallization can occur relatively easily. Instead, the most commonly used model glass former is a binary Lennard-Jones system developed by Kob and Andersen,Kob  However, one drawback of using a binary system is that it is much harder to identify the structural changes that occur on approaching the glass transition. Indeed the nature of the preferred local order in this system has not been systematically studied. Furthermore, a crystalline ground state has recently been discovered for this system.Middleton et al. (2001) In monatomic Lennard-Jones systems it is relatively easy to detect the presence of any close-packed crystallinity in a sample, but incipient crystallization is much less obvious in a binary system with a complex crystal structure, where the growth rate of any crystalline nuclei is expected to be slow. It is therefore unclear whether incipient crystallization could have contaminated any of the previous studies of the supercooled liquid of the binary Lennard-Jones system. In one case, at least, a low-energy configuration has been generated that shows signs of demixing and crystalline layering.Middleton and Wales (2001)

An alternative approach is to use a monatomic system, but one that has been tailored to prevent crystallization. There have been two notable ways in which this goal has been achieved. In the first, a small term is added to the potential (in this case a Lennard-Jones potential) that is a function of the static structure factor and inhibits ordering.Di Leonardo et al. (2000) However, under some conditions this method is not completely effective at preventing crystallization.Angelani et al. (2002) The second approach involves designing a potential that disfavours the close-packed order that is usually favoured by monatomic systems with isotropic pair potentials. Dzugutov achieved this by introducing a maximum in the potential at approximately $`\sqrt{2}`$ times the equilibrium pair distance (see Figure 1),Dzugutov (1992, 1993a) which is the distance between opposite vertices of the octahedra that are intrinsic to close-packing. This maximum causes the preferred local order in the system to be polytetrahedral and icosahedral. Thus, systems bound by this Dzugutov potential are good glass-formers, and exhibit a first sharp diffraction peak and a split second peak in the structure factor,Sadigh et al. (1999) which are common features of metallic glasses. One other interesting feature of this potential is that under certain conditions it can produce a dodecagonal quasicrystal.Dzugutov (1993b)

It is well known that there is an increasing tendency for local polytetrahedral and icosahedral order in simple liquids as the temperature is decreased.Jonsson and Andersen (1988); Nelson and Spaepen (1989); Yonezawa (1991) Recent results for Dzugutov liquids have shown how this change in local order affects the overall structure of the liquid, and is responsible for the changes in properties as the glass transition is approached. There is low-dimensional growth of icosahedral clusters, which eventually percolate through the system leading to a dramatic increase in the structural relaxation time.Zetterling et al. (2001); Dzugutov et al. (cond-mat/0109057) The described cluster growth leads to two interesting dynamical effects: a pronounced spatial variation of atomic mobility and a breakdown of the Stokes-Einstein relation.

An understanding of this intriguing behaviour can be obtained by examining the structures of isolated clusters.Doye et al. (2001) The lowest-energy structures of the clusters can all be considered as aggregates of linked 13-atom icosahedra. However, these aggregates are not compact and as the size increases they change from chains to rings to porous three-dimensional network structures. Therefore, the clusters show the same tendency for low-dimensional aggregation of icosahedra.

One additional advantage of using a monatomic system to study supercooled liquids is that it is much easier to understand the effect of changing the form of the potential. We can therefore systematically study how properties, such as the glass-forming ability and fragility, depend on the potential. This is the approach we use here.

One justification for the form of the Dzugutov potential is that the maximum resembles the first of the Friedel oscillations that occur for metal potentials. However, further maxima occur in the latter case. Here we investigate two potentials that have two maxima. The crystallization behaviour of one of these potentials (Z1) has already been studied by molecular dynamics simulationsDzu (a)—the $`\gamma `$-brassBrandon et al. (1970) structure resulted—and crystallization patterns of the other pair potential (Z2) will be explored elsewhere.Dzu (b) In this paper, we focus on the lowest-energy structures exhibited by clusters bound by these potentials, paying particular attention to the relationship between the observed structures and the form of the potential.

Complementary to these studies of isolated clusters, we also explore the bulk liquids for the two potentials with molecular dynamics. One particular purpose of these simulations is to investigate the liquids’ behaviour upon supercooling and their glass-forming abilities. We also compare the lowest-energy structures for the isolated clusters with the coherently structured domains with predominantly icosahedral local order that develop upon supercooling of the bulk liquids. The results we present here will be particularly helpful in rationalizing the role of the pair potential and the related local order in the development of extended transient structures in the supercooled liquids as the glass transition is approached.

## II Methods

The two potentials both have the form

$$V(r)=a\frac{e^{\alpha r}}{r^3}\mathrm{cos}(2k_Fr)+b\left(\frac{\sigma }{r}\right)^n+V_0$$
(1)
for $`r<r_c`$ and 0 otherwise. We use the position of the third minimum in the function as our cutoff distance, $`r_c`$, and $`V_0`$ is defined through the equation $`V(r_c)=0`$, i.e. $`V_0`$ acts to shift the potential so that it vanishes at the third minimum, thus making the function and its first derivative continuous at the cutoff. The values of the parameters for the two potentials are given in Table 1, and they are plotted in Fig. 1 together with the Dzugutov potential. We denote the two potentials as Z1 and Z2.

The form of the new potentials has a more physical basis than the original Dzugutov potential. The first term has a form similar to that expected for the effective interaction between metal ions when screened by electrons. Friedel oscillations are present with wave-vector, $`2k_F`$, where $`k_F`$ corresponds to the wave-vector at the Fermi level. The second term adds a repulsive interaction that suppresses the oscillations at small $`r`$. The potentials look similar to the effective pair potentials often derived for metallic systems,Hafner (1998); Moriarty and Widom (1997) however in the latter case the potentials are density dependent.

The total potential energy of a cluster interacting with this potential is simply $`E=_{i<j}V(r_{ij})`$. A cluster structure that has a low energy must have pair distances that lie close to the minima in the potential and that avoid the maxima. The first maximum occurs at $`r=1.320r_{\mathrm{eq}}`$ and $`1.318r_{\mathrm{eq}}`$ for Z1 and Z2 respectively, where $`r_{\mathrm{eq}}`$ is the appropriate equilibrium pair separation. The potential still has a large positive value at $`\sqrt{2}r_{\mathrm{eq}}`$, thus the possibility of close-packed structures is ruled out, as for the Dzugutov potential. Instead the potential favours polytetrahedral structures that can avoid this maximum; if the tetrahedra are regular, the first next-nearest neighbour distances occur at $`r=\sqrt{2/3}r_{\mathrm{eq}}=1.633r_{\mathrm{eq}}`$, close to the second minimum at $`r=1.663r_{\mathrm{eq}}`$ (Z1) or $`1.659r_{\mathrm{eq}}`$ (Z2).

As a packing of regular tetrahedra is not achievable in Euclidean space, polytetrahedral structures inevitably involve nearest-neighbour distances that deviate from the ideal value. The energetic penalty for this strain depends sensitively on the width of the potential well. As the first minima of the Z1 and Z2 potentials are somewhat narrower than the Dzugutov potential well (Figure 1), one expects the lowest-energy structures to be non-compact, as for the Dzugutov clusters.Doye et al. (2001) This allows the strain energy inherent to compact polytetrahedral forms to be avoided, whilst maintaining polytetrahedral order. This effect can be quantified by matching the curvatures of the potential at $`r=r_{\mathrm{eq}}`$ to that for the Morse potential, which has a single parameter $`\rho `$ that determines the width of the potential well. $`\rho _{\mathrm{eff}}^{Z1}=8.63`$ and $`\rho _{\mathrm{eff}}^{Z2}=8.89`$, which are somewhat larger than the value for the Dzugutov potential ($`\rho _{\mathrm{eff}}^{Dz}=7.52`$)Doye et al. (2001) and much larger than the values of $`\rho `$ for which the Morse potential has compact polytetrahedral global minima.Doye and Wales (1997)

We attempted to locate the cluster global minima using the basin-hopping global optimization algorithm.Wales and Doye (1997); Li and Scheraga (1987) Since the Z1 and Z2 potentials vanish beyond a distance $`r_c`$, precautions were needed to maintain efficiency. The cluster is placed in a spherical container to prevent atoms evaporating. However, for the structures considered in the present work there can still be a significant amount of empty space in the container. We therefore checked periodically whether the pair energy of any atoms was identically zero. Such atoms were reconnected with the cluster by moving them within the attractive range of their nearest neighbour.

The global minima of these clusters are particularly hard to locate because the oscillations in the potential lead to a rough energy landscape with huge numbers of minima and large energy barriers between different structural forms.Doye et al. (2001) Furthermore, the non-compact nature of the global minima means that the volume of configuration space that needs to be searched is much larger than for compact clusters. Due to these difficulties, it would be no surprise if some of the lowest-energy minima that we found at larger sizes are not the true global minima. Indeed, for some sizes we were able to construct lower-energy structures using the physical principles deduced from the structures that we were able to find. However, as we are more interested in the general structural evolution of the global minima with size, rather than the specifics of individual cluster sizes, this is not a serious problem.

## III Results

### III.1 Isolated Clusters

The energies and point groups of the putative global minima for all clusters up to $`N=80`$ that we have located for the two potentials are given in Table 2. The points files will also be made available online at the Cambridge Cluster Database.Web  In Figure 2 we plot the energies of the global minima in a way that causes particularly stable sizes to stand out. The structures of a selection of these “magic” sizes, and other sizes where interesting high symmetry structures were observed, are depicted in Figures 3 and 4.

As expected, for both potentials the structures exhibited are non-compact arrangements of connected 13-atom icosahedra. For all the particularly stable sizes evident in Figure 2 these icosahedra are complete.

There are three ways in which the icosahedra are linked: (i) two icosahedra can interpenetrate sharing a common fivefold axis, as in the 19-atom double icosahedron; (ii) two icosahedra can share a face as in the 23-atom structure that is the global minimum for both potentials; (iii) two separated icosahedra can be joined by a tetrahedron whose opposite edges are shared with the two icosahedra, as in the 26-atom structure that is the Z2 global minimum. All these ways of linking icosahedra are common in metallic alloys.Shoemaker and Shoemaker (1988)

These three different modes of linkage leads to a large number of possible icosahedral aggregates, especially at larger sizes. For example, the 55-atom Z1 global minimum involves all three possibilities: there is one pair of interpenetrating icosahedra, one pair of face-sharing icosahedra and three pairs of icosahedra that are bridged by tetrahedra.

For both potentials, beyond $`N=13`$ the global minima initially develop into chains of linked icosahedra. For the Z1 potential these chains involve a mixture of both interpenetrating and face-sharing icosahedra, but no icosahedra linked by tetrahedra. Such structures with complete icosahedra are only possible at odd sizes, leading to the odd-even oscillations seen in Figure 2(a) for $`N=2949`$. The only global minimum in this size range that is not chain-like occurs at $`N=38`$. It is a disk-like fragment of the Z-phase (one of the Frank-Kasper phasesFrank and Kasper (1958, 1959)), which was particularly stable for the Dzugutov potential.Doye et al. (2001) Beyond $`N=50`$ the Z1 global minima start to exhibit ring-like structures, and at the largest sizes that we consider they become double rings.

The 52-atom Z1 global minimum is particularly interesting. It is a square array of icosahedra linked through tetrahedra, and it is easy to see how this motif can be repeated to form extended two- and three-dimensional networks of icosahedra. For example, the 78-atom double ring structure is simply formed by the addition of two further icosahedra. Furthermore, two of the 52-atom structures can be placed on top of each other to produce a cubic array of icosahedra at $`N=104`$. Although we have not attempted any global optimization at this size, a comparison of the energy of this cluster ($`296.947505`$) with an extrapolation of $`E_{\mathrm{ave}}`$ (a fit to the energies of the putative global minima) suggests that it is extremely stable. This result has two implications. Firstly, the transition to three-dimensional structures is likely to occur for the Z1 potential just beyond the size range we consider. Indeed, the 91-atom structure formed by removal of an icosahedron at one corner of the cube also appears to be particularly stable ($`E=253.432268`$). Secondly, it seems plausible that at zero pressure the crystal structure formed by repeating this cubic unit could also be most stable. This crystal would be the same as the NaZn13 crystalShoemaker and Shoemaker (1988) but with vacancies at the Na sites. This possibility contrasts somewhat with the results of constant volume simulations (corresponding to higher densities) where crystallization to a $`\gamma `$-brass structureBrandon et al. (1970) was observed.Dzu (a)

For the Z2 potential, by contrast, there is a definite preference for icosahedra linked by tetrahedra. Hence, there is a series of stable chain structures that occur at $`N=13n`$ (Fig. 2). Furthermore, these are the most stable structures over the whole size range that we study. There is no crossover to two- or three-dimensional networks of icosahedra. When we add a third icosahedron to the 26-atom global minimum, there are five possible positions for it. In fact neither the linear nor the L-shaped configurations are lowest in energy. Instead, the angle between the central atoms of the three icosahedra in the 39-atom global minimum is approximately 120. This angle might lead one to think that a hexagonal ring could be formed from six icosahedra, but because the linked icosahedra are in different orientations, a flat configuration with four icosahedra is not possible. Instead, the 52-atom global minimum is a bent chain with two 120 angles between the centres, and a 90 torsion angle. It is also noteworthy that the extra linkage between icosahedra in the ring of the Z1 52-atom global minimum is not enough to stabilize this structure, because the Z2 potential so disfavours 90 angles between the icosahedral centres. However, in constant volume bulk simulations for the Z2 potential, the system has been observed to crystallize into a NaZn13-like structure with most of the Na sites vacant.Dzu (b)

When comparing the behaviour of the structures for the Z1 and Z2 potentials with the Dzugutov clusters, it is clear that the Z1 clusters are the most similar to the Dzugutov clusters. However, the crossovers to two- and to three-dimensional icosahedral aggregates occur at larger sizes for the Z1 potential, and the Dzugutov potential has a greater preference for face-sharing linkages.Doye et al. (2001) Therefore, there is an increasing tendency for the clusters to exhibit non-compact, low-dimensional icosahedral aggregates on going from the Dzugutov, to the Z1 and then to the Z2 potential. One can say that these systems become more frustrated,Sadoc and Mosseri (1999) i.e. it becomes increasingly hard to propagate the locally preferred polytetrahedral order freely through space. There is also a modified version of the Dzugutov potential that has been designed to exhibit compact polytetrahedral clusters by giving the potential a wider well that can sustain the inherent strain in these clusters.Doye and Wales (2001) The effective range parameter for this potential, $`\rho _{\mathrm{eff}}^{\mathrm{m}\mathrm{Dz}}`$, is 5.16.

The above series of four potentials therefore provides an ideal opportunity to correlate the properties of the supercooled liquid with the local structure seen in the clusters and the form of the potential. As the potential becomes more frustrated, one would expect a percolating network of icosahedral clusters to develop more rapidly as the temperature is decreased, thus leading to more fragile behaviour,Angell (1995) i.e. the structural relaxation time has a super-Arrhenius temperature dependence. Similarly, rearrangements of these icosahedral aggregates are also likely to be especially slow, and thus they inhibit crystallization. So one also expects the more frustrated potentials to be better glass-formers.

It is relatively easy to relate the differences between the structures observed for the different types of cluster back to the form of the potential. First, we shall examine the variations in the tendency to form low-dimensional aggregates. The second maximum in the Z1 and Z2 potentials places an additional constraint on the system, as it is harder to avoid than the first maximum. Distances at roughly $`2r_{\mathrm{eq}}`$ in polytetrahedral clusters (e.g. opposite vertices of an icosahedron) occur near the centre of this maximum (Fig. 5) and so are significantly penalized. The number of such distances is of course larger for a compact compact cluster, so the Z1 and Z2 potentials have an extra force driving them towards non-compact geometries over and above that for the Dzugutov potential. This effect is more pronounced for the Z2 clusters, simply because of the larger size of the maximum (Figure 1).

It is also possible to rationalize the preferred types of linkage between the icosahedra. To aid this analysis we have decomposed the potential into five terms

$$E=n_{\mathrm{nn}}ϵ+E_{\mathrm{strain}}+E_{\mathrm{max1}}+E_{\mathrm{min2}}+E_{\mathrm{max2}},$$
(2)
where $`n_{\mathrm{nn}}`$ is the number of nearest neighbours, $`E_{\mathrm{strain}}`$ is the energetic penalty for nearest-neighbour distances that deviate from the equilibrium pair separation,Doye and Wales (1997) and $`E_{\mathrm{max1}}`$, $`E_{\mathrm{min2}}`$ and $`E_{\mathrm{max2}}`$ are the energies associated with pair distances near to the first maximum, second minimum and second maximum, respectively. The distance criteria used to separate these different contributions are simply the distances for which $`V(r)=0`$.

We report the above contributions to the energy for the icosahedron and the three ways of linking two icosahedra in Table 3. We also show the pair distribution functions for these structures in Fig. 5. For a given size, the number of nearest neighbours is largest for the interpenetrating icosahedra and smallest for the icosahedra linked by tetrahedra, as would be expected from the relative compactness of the resulting structures.nnc  However, to compensate for this effect the interpenetrating icosahedra have the largest strain energy and $`E_{\mathrm{max2}}`$ for a given size and the tetrahedra-bridged icosahedra the smallest.

When comparing the contributions to the energy for the same structure, but for the two potentials, it is clear from Table 3 that the major changes are in $`E_{\mathrm{min2}}`$ and $`E_{\mathrm{max2}}`$, due to the greater magnitude of the second maximum and minimum for the Z2 potential. Indeed, there is a greater driving force for minimizing $`E_{\mathrm{max2}}`$ for the Z2 potential, and it is this factor that leads to the icosahedra linked by an intervening tetrahedron to be dominant.

Similarly, when linking more than two icosahedra through intervening tetrahedra, 90 angles between the icosahedral centres are disfavoured for the Z2 potential because this introduces some distances between the atoms in the non-adjacent icosahedra that are near to the second maximum.

### III.2 Bulk liquids

The properties of the bulk liquids for the Z1 and Z2 potentials were explored by molecular dynamics simulations of a system of $`\mathrm{16\hspace{0.17em}000}`$ particles at a number density $`\rho `$=0.84. The simulations focused on the behaviour of these liquids in the supercooled domain. We take as the upper bound of this domain, not the limit of thermodynamic stability (the melting temperature $`T_m`$), but the temperature ($`T_A`$) below which the liquid begins to demonstrate a set of characteristic dynamical anomalies that are routinely associated with the notion of supercooled liquid dynamics. The most celebrated of these anomalies is the super-Arrhenius slowing down, which is commonly regarded as a defining property of the supercooled liquid state. One purpose of the present molecular dynamics simulations was to explore the glass-forming abilities of the two systems (the notion of the glass-forming ability of a liquid refers to its ability to remain in a state of metastable equilibrium within a temperature domain where it exhibits the super-Arrhenius behaviour and other characteristic features of supercooled liquids). To this end, we subjected each of the two liquids to a step-wise cooling whereby at each temperature step the system was relaxed to the state of apparent equilibrium.

The temperature variation of the diffusion coefficient for both potentials is shown in Fig.6. In both cases, $`D(T)`$ exhibits a pattern characteristic of fragile glass-formers: below the temperature $`T_A`$ a pronounced super-Arrhenius slowing down is observed. The non-Arrhenius part of the $`D(T)`$ curves extends for over two decades, thus demonstrating the pronounced glass-forming ability of the two systems simulated here. We also note that the activation energy, as estimated from the Arrhenius plot, is significantly larger in the case of the Z2 potential; this behaviour appears to be consistent with the larger amplitude of its Friedel-like oscillations.

Another issue that we addressed in these simulations was the formation of extended domains of icosahedral structure upon supercooling. The development of such domains has previously been demonstrated in simulations of a supercooled bulk liquid using the Dzugutov potential.Zetterling et al. (2001); Dzugutov et al. (cond-mat/0109057) Moreover, these domains were found to be morphologically similar to the low-energy structures of isolated clusters for that potential.Doye et al. (2001)

Here, we analyse atomic configurations obtained by steepest descent minimization of instantaneous atomic configurations representing equilibrium liquids. In order to discern icosahedral order in the first shell of neighbours, we first identified pentagonal bipyramids—pairs of neighbours with five common neighbours forming a closed ring (any two particles separated by the distance less than 1.5 were regarded as neighbours). A 13-atom icosahedron was identified as a central atom with 12 neighbours all of which form five-fold pairs (pentagonal bipyramids) with the central atom. Furthermore, we considered two icosahedra sharing at least 3 atoms as connected.

We found that both systems also demonstrate a clear tendency for the formation of extended icosahedral clusters upon cooling. This tendency is illustrated in Fig. 7 where we present typical clusters of connected icosahedra that develop upon supercooling of the two model liquids. For both systems, it is possible to observe a close similarity between the patterns of icosahedral aggregation in these clusters and those in the respective clusters presented in Figs. 3 and 4. We remark that the Z2 system clearly demonstrates, for both the isolated clusters and the icosahedral domains identified in the liquid, a more pronounced tendency for one-dimensional aggregation of icosahedra than the Z1 system.

## IV Conclusions

Following Frank,Frank (1952) we have sought insight into the structure of supercooled liquids by analysing the structures of the corresponding clusters; the clusters can allow the identification of the ideal, local structural order. This philosophy has also been employed in cluster models of the glass transition,Fan and Fecht (2002) and has influenced theories such as the frustration-limited domain model.Kivelson et al. (1995); Kivelson and Tarjus (1998)

We have introduced two new potentials that are similar to effective potentials in metals with oscillations that lead to polytetrahedral and icosahedral order being preferred, thus making them good glass-formers. The cluster global minima generally correspond to non-compact arrangements of linked 13-atom icosahedra. For one potential (Z1) we find that two-dimensional networks of these icosahedra become preferred for the largest sizes we consider, whereas for the other potential (Z2) chains of icosahedra are only observed. Similar icosahedral aggregates were observed to form upon supercooling of the corresponding bulk liquids.

Along with the Dzugutov potentialDzugutov (1992, 1993a) and a modified version of it,Doye and Wales (2001) this series of potentials provides an ideal set of model systems to explore the relationship between the potential, the locally preferred structure, the energy landscape and the properties of supercooled liquids, such as fragility, glass-forming ability and the decoupling of diffusion and structural relaxation. Understanding these relationships has been a long-standing goal in the field of supercooled liquids, and simulations, here and in more detail elsewhere,Dzu (b) confirm some of the expected correlations with the cluster structures we observe.

###### Acknowledgements.

JPKD is grateful to the Royal Society for financial support. FHMZ and MD gratefully acknowledge support from the Swedish Research Foundation (VR).


text:
# Identity and search in social networks

## Abstract

Social networks have the surprising property of being “searchable”: ordinary people are capable of directing messages through their network of acquaintances to reach a specific but distant target person in only a few steps. We present a model that offers an explanation of social network searchability in terms of recognizable personal identities defined along a number of social dimensions. Our model defines a class of searchable networks and a method for searching them that may be applicable to many network search problems including the location of data files in peer-to-peer networks, pages on the World Wide Web, and information in distributed databases.

In the late 1960’s, Travers and Milgram Travers and Milgram (1969) conducted an experiment in which randomly selected individuals in Boston, Massachusetts, and Omaha, Nebraska, were asked to direct letters to a target person in Boston, each forwarding his or her letter to a single acquaintance whom they judged to be closer than themselves to the target. Subsequent recipients did the same. The average length of the resulting acquaintance chains for the letters that eventually reached the target (roughly $`20\%`$) was approximately six. This reveals not only that short paths exist Watts and Strogatz (1998); Strogatz (2001) between individuals in a large social network but that ordinary people can find these short paths Kleinberg (2000a). This is not a trivial statement, since people rarely have more than local knowledge about the network. People know who their friends are. They may also know who some of their friends’ friends are. But no one knows the identities of the entire chain of individuals between themselves and an arbitrary target.

The property of being able to find a target quickly, which we call searchability, has been shown to exist in certain specific classes of networks that either possess a certain fraction of hubs (highly connected nodes which, once reached, can distribute messages to all parts of the network Barabási and Albert (1999); Adamic et al. (2001); Kim et al. (2002)) or are built upon an underlying geometric lattice which acts as a proxy for “social space” Kleinberg (2000a). Neither of these network types, however, is a satisfactory model of society.

In this paper, we present a model for a social network that is based upon plausible social structures and offers an explanation for the phenomenon of searchability. Our model follows naturally from six contentions about social networks.

1. Individuals in social networks are endowed not only with network ties, but identities White (1992): sets of characteristics which they attribute to themselves and others by virtue of their association with, and participation in, social groups Simmel (1902); Nadel (1957). The term group refers to any collection of individuals with which some well-defined set of social characteristics is associated.

2. Individuals break down, or cluster, the world hierarchically into a series of layers, where the top layer accounts for the entire world and each successively deeper layer represents a cognitive division into a greater number of increasingly specific groups. In principle, this process of distinction by division can be pursued all the way down to the level of individuals, at which point each person is uniquely associated with his or her own group. For purposes of identification, however, people do not typically do this, instead terminating the process at the level where the corresponding group size $`g`$ becomes cognitively manageable. Academic departments, for example, are sometimes small enough to function as a single group, but tend to split into specialized sub-groups as they grow larger. A reasonable upper bound on group size Simmel (1902) is $`g100`$, a number which we incorporate into our model (Fig. 1A). We define the similarity $`x_{ij}`$ between individuals $`i`$ and $`j`$ as the height of their lowest common ancestor level in the resulting hierarchy, setting $`x_{ij}=1`$ if $`i`$ and $`j`$ belong to the same group. The hierarchy is fully characterized by depth $`l`$ and constant branching ratio $`b`$. The hierarchy is a purely cognitive construct for measuring social distance and not an actual network. The real network of social connections is constructed as follows.

3. Group membership, in addition to defining individual identity, is a primary basis for social interaction Nadel (1957); Breiger (1974), and therefore acquaintanceship. As such, the probability of acquaintance between individuals $`i`$ and $`j`$ decreases with decreasing similarity of the groups to which they respectively belong. We model this by choosing an individual $`i`$ at random and a link distance $`x`$ with probability $`p(x)=c\mathrm{exp}\{\alpha x\}`$, where $`\alpha `$ is a tunable parameter, and $`c`$ is a normalizing constant. We then choose a second node $`j`$ uniformly among all nodes that are distance $`x`$ from $`i`$, repeating this process until we have constructed a network in which individuals have an average number of friends $`z`$. The parameter $`\alpha `$ is therefore a measure of homophily—the tendency of like to associate with like. When $`e^\alpha 1`$, all links will be as short as possible, and individuals will only connect to those most similar to themselves (i.e., members of their own bottom-level group), yielding a completely homophilous world of isolated cliques. By contrast, when $`e^\alpha =b`$, any individual is equally likely to interact with any other, yielding a uniform random graph Bollobás (1985) in which the notion of individual similarity or dissimilarity has become irrelevant.

4. Individuals hierarchically cluster the social world in more than one way (for example, by geography and by occupation). We assume that these categories are independent, in the sense that proximity in one does not imply proximity in another. For example, two people may live in the same town but not share the same profession. In our model, we represent each such social dimension by an independently partitioned hierarchy. A node’s identity is then defined as an $`H`$-dimensional coordinate vector $`\stackrel{}{v}_i`$, where $`v_i^h`$ is the position of node $`i`$ in the $`h`$th hierarchy, or dimension. Each node $`i`$ is randomly assigned a coordinate in each of $`H`$ dimensions, and is then allocated neighbors (friends) as described above, where now it randomly chooses a dimension $`h`$ (e.g. occupation) to use for each tie. When $`H=1`$ and $`e^\alpha 1`$, the density of network ties must obey the constraint $`z<g`$.

5. Based on their perceived similarity with other nodes, individuals construct a measure of “social distance” $`y_{ij}`$, which we define as the minimum ultrametric distance over all dimensions between two nodes $`i`$ and $`j`$; i.e., $`y_{ij}=\mathrm{min}_hx_{ij}^h`$. This minimum metric captures the intuitive notion that closeness in only a single dimension is sufficient to connote affiliation (for example, geographically and ethnically distant researchers who collaborate on the same project). A consequence of this minimal metric, depicted in Fig. 1B, is that social distance violates the triangle inequality—hence it is not a true metric distance—because individuals $`i`$ and $`j`$ can be close in dimension $`h_1`$, and individuals $`j`$ and $`k`$ can be close in dimension $`h_2`$, yet $`i`$ and $`k`$ can be far apart in both dimensions.

6. Individuals forward a message to a single neighbor given only local information about the network. Here, we suppose that each node $`i`$ knows only its own coordinate vector $`\stackrel{}{v}_i`$, the coordinate vectors $`\stackrel{}{v}_j`$ of its immediate network neighbors, and the coordinate vector of a given target individual $`\stackrel{}{v}_t`$, but is otherwise ignorant of the identities or network ties of nodes beyond its immediate circle of acquaintances.

Individuals therefore have two kinds of partial information: social distance, which can be measured globally but which is not a true distance and hence can yield misleading estimates; and network paths, which generate true distances but which are known only locally. Although neither kind of information alone is sufficient to perform efficient searches, here we show that a simple algorithm that combines knowledge of network ties and social identity can succeed in directing messages with efficiency. The algorithm we implement is the same greedy algorithm Milgram suggested: each member $`i`$ of a message chain forwards the message to its neighbor $`j`$ who is perceived to be closer to the target $`t`$ in terms of social distance; that is, $`y_{jt}`$ is minimized over all $`j`$ in $`i`$’s network neighborhood.

Our principal objective is to determine the conditions under which the average length $`L`$ of a message chain connecting a randomly selected sender $`s`$ to a random target $`t`$ is small. Although the term small has recently been taken to mean that $`L`$ grows slowly with the population size $`N`$ Newman and Watts (1999); Kleinberg (2000b), Travers and Milgram found only that chain lengths were short. Furthermore, these message chains had to be short in an absolute sense because at each step, they were observed to terminate with probability $`p0.25`$ Travers and Milgram (1969); White (1970). We therefore adopt a more realistic, functional notion of efficient search, defining for a given message failure probability $`p`$, a *searchable network* as any network for which $`q`$, the probability of an arbitrary message chain reaching its target, is at least a fixed value $`r`$. In terms of chain length, we formally require $`q=(1p)^Lr`$, and from this we can obtain an estimate of the maximum required $`L`$ using the approximated inequality $`L\mathrm{ln}r/\mathrm{ln}(1p)`$. For the purposes of this paper, we set $`r=0.05`$ and $`p=0.25`$ giving the stringent requirement that $`L10.4`$ independent of the population size $`N`$. Fig. 2A presents a typical phase diagram in $`H`$ and $`\alpha `$ outlining the searchable network region for several choices of $`N`$, $`g=100`$, and $`z=g1=99`$.

Our main result is that searchable networks occupy a broad region of parameter space $`(\alpha ,H)`$ which, as we argue below, corresponds to choices of the model parameters that are the most sociologically plausible. Hence our model suggests that searchability is a generic property of real-world social networks. We support this claim with some further observations, and demonstrate that our model can account for Milgram’s experimental findings.

First, we observe that almost all searchable networks display $`\alpha >0`$ and $`H>1`$, consistent with the notion that individuals are essentially homophilous (that is, they associate preferentially with like individuals), but judge similarity along more than one social dimension. Neither the precise degree to which they are homophilous, nor the exact number of dimensions they choose to use, appear to be important—almost any reasonable choice will do. The best performance, over the largest interval of $`\alpha `$, is achieved for $`H=2`$ or $`3`$—an interesting result in light of empirical evidence Bernard et al. (1988) that individuals across different cultures in small-world experiments typically utilize two or three dimensions when forwarding a message.

Second, as Fig. 2B shows, while increasing the number of independent dimensions from $`H=1`$ yields a dramatic reduction in delivery time for values of $`\alpha >0`$, this improvement is gradually lost as $`H`$ is increased further. Hence the window of searchable networks in Fig. 2A exhibits an upper boundary in $`H`$. Because ties associated with any one dimension are allocated independently with respect to ties in any other dimension, and because for fixed average degree $`z`$, larger $`H`$ necessarily implies fewer ties per dimension, the network ties become less correlated as $`H`$ increases. In the limit of large $`H`$, the network becomes essentially a random graph (regardless of $`\alpha `$) and the search algorithm becomes a random walk. Effective decentralized search therefore requires a balance (albeit a highly forgiving one) of categorical flexibility and constraint.

Finally, by introducing parameter choices that are consistent with Milgram’s experiment ($`N=10^8`$, $`p=0.25`$) Travers and Milgram (1969), as well as with subsequent empirical findings ($`z=300`$, $`H=2`$)Killworth and Bernard (1978); Bernard et al. (1988), we can compare the distribution of chain lengths in our model with those of Travers and Milgram Travers and Milgram (1969) for plausible values of $`\alpha `$ and $`b`$. As Fig. 3 shows, we obtain $`L6.7`$ for $`\alpha =1`$ and $`b=10`$, indicating that our model captures the essence of the real small-world problem.

Although sociological in origin, our model is relevant to a broad class of decentralized search problems, such as peer-to-peer networking, in which centralized servers are excluded either by design or by necessity, and where broadcast-type searches (i.e., forwarding messages to all neighbors rather than just one) are ruled out due to congestion constraints Adamic et al. (2001). In essence, our model applies to any data structure in which data elements exhibit quantifiable characteristics analogous to our notion of identity, and similarity between two elements—whether people, music files, web pages, or research reports—can be judged along more than one dimension. One of the principal difficulties with designing robust databases Manneville (1999) is the absence of a unique classification scheme which all users of the database can apply consistently to place and locate files. Two musical songs, for example, can be similar because they belong to the same genre or because they were created in the same year. Our model transforms this difficulty into an asset, allowing all such classification schemes to exist simultaneously, and connecting data elements preferentially to similar elements in multiple dimensions. Efficient decentralized searches can then be conducted utilizing simple, greedy algorithms providing only that the characteristics of the target element and the current element’s immediate neighbors are known.

###### Acknowledgements.

The authors thank Jon Kleinberg for beneficial discussions. This work was funded in part by the National Science Foundation under grant numbers SES-00-94162 and DMS–0109086, the Intel Corporation, and the Columbia University Office of Strategic Initiatives.