搜档网
当前位置:搜档网 › Optical Bistability in Colloidal Crystals

Optical Bistability in Colloidal Crystals

Optical Bistability in Colloidal Crystals
Optical Bistability in Colloidal Crystals

a r X i v :c o n d -m a t /9704078v 1 9 A p r 1997

Optical Bistability in Colloidal Crystals

E.Lidorikis,Qiming Li,and C.M.Soukoulis

Ames Laboratory and Department of Physics and Astronomy,

Iowa State University,Ames,IA 50011

We present a one dimensional model for the nonlinear response of a colloidal crystal to intense light illumination along a high symmetry direction.The strong coupling between light and the colloidal lattice,via the electric gradient force acting upon the particles,induces a novel large optical non-linearity.We obtain bistable behavior when the incident frequency is inside the stopband of the periodic structure,with decreasing switching intensity as the frequency increases.The transmission characteristics and the magnitude of the switching threshold intensity are also in good agreement with a recent experiment.

PACS numbers:42.65.Pc 82.70.Dd 42.70.Qs 78.66.-w

I.INTRODUCTION

Photonic band gap (PBG)materials [1]do not allow propagation of electromagnetic waves within a certain frequency range,thereby opening the possibility of study-ing new physics within the gap.In addition,many novel applications of these PBG crystals have been proposed,with operating frequencies ranging from microwaves to the optical regime [1,2].Structures exhibiting full pho-tonic band gaps in the microwave [3],millimeter [4]and submillimeter [5]regimes have already been fabricated,but scaling these structures down to the optical regime has remained a challenge.One way to construct PBG crystals in the optical regime is by growing polystyrene colloidal crystals [6–9],which have lattice spacing com-parable to the wavelength of light.Such colloidal crystals do not exhibit a complete PBG,because the concentra-tion and the index of refraction of the polystyrene spheres relative to water are not yet su?ciently high.However,they are very useful in studying PBG e?ects seen only in particular directions.In addition,they can be used in nonlinear optical studies.It is expected that the PBG ef-fects can be strongly a?ected by nonlinear optical e?ects.In particular,it has been shown that intensity-dependent index of refraction can cause a shift in the locations of the band gap [10].That is,if the index of refraction of either the suspended polystyrene spheres or water is intensity-dependent,then the width and the position of the stopband (or gap)will change under intense illumina-tion.For example,a decrease of the index of refraction in water upon illumination will widen the gap,and,there-fore,inhibits the propagation of the probe beam.Such an optical switching for light control is of great interest to the optics community.

In a recent experiment [7],optical switching and op-tical bistability were observed,when intense light was transmitted through a colloidal crystal.Simple switch-ing was observed near the low-frequency end of the stop-band,whereas bistability and multistability occurred at the center or near the high frequency end.The switching threshold was found to decrease as the incident frequency

increased.These aspects are inconsistent with the re-sponse of a material with the conventional intensity-dependent nonlinearity [7].The measured nonlinear coef-?cient n ′

inside the transmission band,4×10?10cm 2/W ,is also several orders of magnitude larger than the elec-tronic nonlinearity of both materials.

In this paper,we present a one dimensional model for the nonlinear response of a colloidal crystal to intense light incident along a high symmetry direction,based on the electrostriction mechanism [7].Light is strongly scat-tered by the periodic arrangement of the colloidal parti-cles inside the crystal,thus creating a spatially varying ?eld.The polystyrene spheres,polarized by the elec-tric ?eld,will move in response to the electric gradient force.Such a structure change in turn will alter the propagation of light.The optical response is thus con-trolled by the the stationary con?guration that results from the balance between the elastic and the electric gra-dient forces.We assume that the electric gradient forces are not strong enough to destroy the polystyrene spheres’crystalline structure and furthermore,that the changes in interparticle separation are small compared to the mean interparticle separation.Assuming the incident wave can be approximated as plane waves due to the large beam spot size,the structural change induced by light incident along a high symmetry direction will be primarily in the propagating direction.We neglect possible transverse ef-fects and describe the three dimensional lattice by a one dimensional harmonic lattice model.Numerical calcula-tions of the transmission characteristics,based on known physical properties of the colloidal crystal and a sim-pli?cation to a layered structure,show good agreement with experiment.In particular,we ?nd bistable behav-ior inside the stopband at intensities comparable to the observed switching threshold.The switching threshold is found to decrease as the incident frequency increases.We need to emphasize that such a nonlinearity necessar-ily depends on the exact stationary con?guration of the lattice and therefore cannot be described with a simple e?ective intensity-and/or frequency-dependent dielectric constant.

This paper is organized as follows.In section II,we introduce our one-dimensional lattice model for the op-tical nonlinearity in colloidal crystal.In section III,we present results of calculations on the optical bistability and compare them with experiments.Conclusions and discussions are presented in section IV.

II.ONE DIMENSIONAL MODEL OF OPTICAL

NONLINEARITY

In general,wave propagation in periodic structures is a complex phenomenon.Three dimensional scattering of light plays an important role in determining the nonlin-ear optical response of a colloidal crystal to incident light. However,simpli?cation is possible if,a)the incident wave is plane-wave-like;b)the light is normally incident upon a high symmetry plane of the crystal lattice,and c)no transverse instability exits.Under these conditions,the structure can be viewed as a layered system.One di-mensional modeling of the optical response is expected to be appropriate with correctly calculated physical pa-rameters.The?rst condition ensures all spheres within one layer are equivalent,hence there should be no lateral lattice displacement,as required by symmetry.The sec-ond condition makes the layered structure more distinct since the distance between the layers is large.The third condition essentially requires that the structure is stable under illumination.

The colloidal crystal used in experiment[7]had a face-centered-cubic structure formed by polystyrene spheres (n1=1.59)of approximately d1=120nm in diameter,at concentration f around7%,dispersed in water(n2=1.33). Light was normally incident upon the[111]plane which was parallel to the surfaces of the container.Due to the relatively large spot size,we approximate the incident wave as plane-waves.To a low intensity incident wave from the[111]direction,the fcc colloidal crystal acts es-sentially as a Bragg re?ector(linear regime).The system is naturally simpli?ed as a one dimensional bilayer struc-ture consistent of alternating segments of polystyrene sphere layers(a mixture of polystyrene spheres and water with total thickness d1)and pure water layers. With sphere concentration of6.9%,the distance between the polystyrene sphere layers[11]is R0=216nm.The thickness of the water layer is then d2=R0-d1=96nm. The average index of refraction of the polystyrene layer is estimated[12]to be1.36.Since the sample thick-ness is L=100μm,the total number of bilayer units is N=L/R0=463.The linear(zero intensity limit)trans-mission coe?cient versus the wavelength in the[111]di-rection is shown in Fig.1,calculated with the parameters mentioned above.Notice that there is excellent agree-ment[13]between our theoretical results of Fig.1and the experimental results of Fig.2in Ref.7.This shows our model parameters describe very well the linear trans-mission of the colloidal crystal.

To illustrate that the nonlinear response of the col-

loidal crystal cannot be described by a one dimensional layered model with the conventional Kerr type nonlinear-

ity(intensity-dependent dielectric constant),we show in Fig.2the nonlinear response of such a system,assuming

that the e?ective index of refraction n2of the“water”has the form,n2=n o2+n′|E|2.n o2=1.33is the linear index of refraction of the medium and the nonlinear coe?cient is taken to be the experimentally measured nonlinearity,

n′=4×10?10cm2/W.Taking the propagation direction to be the z direction,we can solve the propagation of light governed by the following wave equation

d2E

c2

E=0,(1)

where n(z)is the index of refraction of our model which consists of alternating layers of linear and nonlinear medium,as speci?ed above.Indeed,bistable behavior is obtained,as can be clearly seen in Fig.2.The exis-tence of such bistability phenomena in distributed feed-back structures with intensity-dependent dielectric con-stants were predicted[14]theoretically and their prop-erties have been investigated intensively[15].Similar bistable behavior has been seen[16–18]in the discrete case of the electronic version of Eq.(2).However,the threshold intensity for the onset of the bistable behav-ior is in the order of10MW/cm2,at least three orders of magnitude larger than the experimentally measured value of about5kW/cm2.We see that a simple so-lution of Eq.(1)with an e?ective intensity-dependent nonlinearity indeed produces bistable behavior,but its predictions for the incident intensity threshold are un-realistically high.Clearly,a novel form of nonlinearity must be in action.

An interesting mechanism due to electrostriction was proposed[7]to be responsible for the nonlinear behavior in the colloidal crystal.In the absence of light illumi-nation,the short-range screened electrostatic repulsive forces[19]between the spheres balances the weak long-range attractive force of Van der Waals type and pro-duces an equilibrium con?guration for the polystyrene spheres,with nearest neighbor separation S0=α/

dimensional lattice model that can be solved straightfor-wardly but still contains the essential physics to account for the optical bistability observed in experiment.We have argued that under the experimental condition,a one dimensional layered model is appropriate to describe the transmission of wave along the propagation direction. The linear transmission property of this one dimensional lattice,consisting of alternating layers of polystyrene and water,has already been described(Fig.1).To model the nonlinear response,we need knowledge of the lattice dynamics which is governed by the elastic and electric gradient forces.

We assume that for small?uctuations around the equi-librium con?guration,the harmonic approximation is correct.We can then describe the motion of polystyrene spheres as if they were connected with each other with ideal springs.The force constant k of the springs can be roughly estimated by linearizing the screened electro-static repulsive force[22],

F el=(Ze)2

1+κa

exp[?κ(R?a)],(2)

at the layer equilibrium position R=R0.This leads to

an expression F el=F harm=k?R,where?R=R?R0 is the displacement from the equilibrium position.Z is

the number of charges on the particle,κis the inverse screening length,and a is the radius of the https://www.sodocs.net/doc/d96438537.html,-

ing?=1.33?0,a=60nm,R0=216nm,and assuming typical values[19]of Z=1000e?andκ=5×107m?1,

we obtain k=1.8×10?4N/m.This corresponds to a bulk moduli B~k/R0~1000N/M2,a reasonable value for colloidal crystals[19].As we will see later,the elec-

trostriction nonlinearity is inversely proportional to k. Only the order of the magnitude of k is relevant for our

purpose.For de?niteness,we take k=1.8×10?4N/m in the following calculations.

The gradient force on a sphere F gr along the propaga-tion direction z,can be calculated by taking the spa-tial derivative of it’s polarization energy,i.e.,F gr=?d(U p)/dz.A crude estimate of this force is

F gr?4πn21?0m2?12?|E|2

2

comes from averaging over a

time period.?|E|2is the?eld intensity di?erence across a sphere’s diameter.For our model’s parameters this gives F gr?C?|E|2,C=2.2×10?26Nm2/V2.

The optical response of the colloidal crystal is deter-mined by the steady state con?guration.In our one di-mensional model,this is re?ected as the steady state lat-tice con?guration representing the con?guration of the layers.Taking nearest neighbor interactions only and denoting by?R n the change from the equilibrium sep-aration of particles n and n+1,we have for the steady state that

F gr=?F harm=?k(?R n??R n?1).(4) The gradient force F gr on each polystyrene layer has to be calculated from the electric?eld distribution via Eq.(3) for the given lattice con?guration{R n}.

The transmission characteristics are obtained by solv-ing Eqs.(1)and(4)self-consistently through iteration, for a given input.In actual calculations,however,this is done for a given output because the presence of bistable or multistable behavior.In a nonlinear one-dimensional model,each output corresponds to exactly one solution, while a given input may correspond to more than one output solutions(bistability).The input intensity can be reconstructed once the transmission coe?cient is cal-culated after solving Eq.(1).We start with the equi-librium con?guration in the absence of light in which all the layers is equally spaced with distance R0.The wave ?eld E(z)is then calculated from Eq.(1),with n(z)given by the exact one-dimensional lattice con?guration{R n}. n(z)equals to1.36if z is in the polystyrene layer and 1.33otherwise.The gradient force and the elastic force is then calculated and R n is increased or decreased depend-ing the direction of the total force.The wave?eld is then recalculated and accordingly{R n}readjusted.This iter-ation procedure continues until the total force vanishes on each polystyrene layer.The?nal con?guration will be the steady state con?guration,and the corresponding ?eld represents the actual optical response of the system. Twenty iterations are usually required before a steady state self-consistent con?guration is achieved.

We point out that the present situation is analogous to the problem of an electron moving in a one-dimensional harmonic lattice with electron-lattice interactions.Such an analogy may help to understand the nonlinear opti-cal response when the frequency is inside the stopband. We comment that neither in the polystyrene spheres nor in the water have we assumed any intrinsic nonlinearity. The nonlinear response of the colloidal crystal is entirely due to the coupling between the light and the lattice.In principle,such coupling exists in all materials.But the extreme softness of colloidal lattices relative to conven-tional crystals,re?ected in the small value of the e?ective spring constant k,makes the observation of nonlinear ef-fects possible in these materials.

III.OPTICAL BISTABILITY

As a?rst check of our model,we have numerically calculated the sign and the strength of the e?ective non-linearity for a frequency(λ=514nm)inside the transmis-sion band.We found that the colloidal crystal linearly expands with the incident intensity of the EM wave,with a slope of about1nm per30kW/cm2.This corresponds to a relative linear expansion of the order?L/L?10?5, which is quite small as required by our harmonic assump-tion.The resulted phase shift in the transmitted wave

can be related to an e?ective positive nonlinear index of refraction by

ω

c

n′|E0|2L(5)

where|E0|is the incident intensity.For our system we es-timate n′?10?10cm2/W.This is in excellent agreement with the experimental value[7]of n′?4×10?10cm2/W, considering that the value of the force constant is only estimated with typical values of physical properties for colloidal crystals.We?nd that within the transmission band,the nonlinearity n′scales almost linearly with1/k, but with no appreciable frequency dependence.The ex-perimentally observed nonlinearity can be matched with the choice k?4.4×10?5N/m and a corresponding bulk moduli B~250N/m2.For de?niteness we continue to use the initial estimated value of k.Changing value of k amounts to rescale the light intensities,since the actual contraction or expansion is controlled by the ratio of the elastic force and the gradient force,ie,only the ratio of the k and light intensity matters.

Multistability and switching threshold intensities are also correctly predicted within our model for frequencies inside the band gap.The local expansions and contrac-tions of the lattice under illumination are the origin of the bistable behavior.Normally,transmission is forbid-den in the gap of a periodic system.However,lattice distortion allows the existence of localized modes in the gap.Under appropriate conditions,the coupling of these localized modes with the radiation can produce resonant transmission.This is clearly seen in Fig.3,where the local lattice expansion(a),the?eld intensity averaged in each sphere(b),and the intensity gradient(c),are shown as a function of the lattice plane,exactly at a transmission resonance for a frequency inside the stop-band.Notice that there is a strong lattice deforma-tion(solid curve in Fig.3a)at the middle of the crys-tal,sustained by the strong?eld intensities(solid curve in Fig.3b)and the intensity gradient.Similar behav-ior is seen for the case of the second transmission reso-nance(dotted lines in Fig.3).This work clearly shows that there exists a strong light-lattice interaction,giving rise to lattice deformations which in turn produces lo-calized solutions as“soliton-like”objects[20,21].When these“soliton-like”objects appear symmetrically in the crystal,a transmission resonance is expected.Also,the longer the wavelength and the higher the multistabil-ity order are,the larger the maximum values of these deformations become.The bistable behavior originates from these?eld-distribution-speci?c structure changes. We point out that the total expansion of the lattice is still relatively small,generally in the order of80to200 nm for each”soliton-like”object present in the structure. The transmission characteristics are shown in Fig.4, for four di?erent wavelengths as were indicated in Fig.1. We see that our model captures the most essential fea-tures of the nonlinear response of the colloidal crystal, as compared with the experimental results presented in Fig.3of Ref.7.Notice that this model correctly pre-dicts the magnitude of the switching threshold intensi-ties,they are of the order of(20-40)kW/cm2and not of the order of104kW/cm2that the simple model with an intensity-dependent dielectric constant predicts(see Fig.2).The switching threshold intensities get smaller as we move from the long to the short wavelength side of the stopband,in agreement with experiment[7].Bista-bility is observed when the lattice is distorted enough so to sustain a localized mode.This will happen if the local expansion is large enough to locally shift the e?ective gap to longer wavelengths[22].Thus,the closer the incident frequency is to the small wavelength side of the gap,the smaller the lattice distortion needed to onset bistability, and thus the smaller the switching powers are. Discrepancy with the experimental data is found for large incident intensities and in the low frequency side of the gap.Multistability was observed only in the high frequency side while for midgap frequencies the crystal is bistable and for low frequencies it is non bistable[7]. Also,at high intensities only instabilities were observed experimentally,in contrast to our model that predicts multistable behavior for all gap frequencies and all in-tensities.However,it is for the long wavelengths and the high intensities that the required lattice expansions get unrealistically large.The total lattice expansion versus the transmitted intensity are shown in Fig.5,for the four wavelengths indicated in Fig.1.Every local maximum in these curves corresponds to a transmission resonance. Since the crystal can not expand more than a certain maximum limit,an external pressure must be inserted into our model to limit its expansion.Numerical stud-ies incorporating an external pressure show that while multistability is still predicted for all frequencies,the required local expansions and contractions,(with total expansion being constant and limited),and light inten-sities are much larger,making the starting assumption of a slightly perturbed harmonic lattice invalid.With large lattice distortions,approximation to a one dimen-sional structure also becomes questionable,and this may be the main reason for the discrepancy.The neglect of light absorption in water may also be a contributed fac-tor to the discrepancy.Absorption reduces the light in-tensity nonuniformly,and thus may a?ect the nonlinear response.

IV.DISCUSSIONS AND CONCLUSIONS

We have shown that several essential features of the nonlinear response in colloidal crystals can be accounted for by a simple one dimensional model that incorporates the lattice distortions under intense light illumination.In this one dimensional model,the colloidal crystal is sim-pli?ed as a one-dimensional layered system consisting of alternating layers of polystyrene spheres and water.The polystyrene layers represent high symmetry planes of the

colloidal crystal normal to the propagating direction and are modeled as elastic media deforming under the act of the gradient force from the electric?eld.Based on physical properties of the colloidal crystal,we are able to estimate the e?ective elastic spring constant.The wave equation of the electric?eld and the lattice dy-namics of this one dimensional systems is then solved simultaneously to obtain the steady state response.We are able to obtain the correct order of magnitude of the e?ective nonlinearity within the transmission band and

the switching intensity for optical bistability within the stopband.The trend that this switching intensity de-creases as the frequency increases across the stopband is also reproduced.Although it seems surprising that a sim-ple one-dimensional model works when three-dimensional scattering of light plays an important rule,detail consid-erations suggest this simpli?cation should be appropriate under the experimental condition.

In conclusion,we have established with a simple one dimensional model that the light-lattice coupling via elec-tric gradient force underlies the large optical nonlinearity observed recently in colloidal crystals.Such a coupling alone can produce bistability and multistability with switching threshold intensities and transmission charac-teristics in good agreement with experiment.Given the unique large nonlinear response,colloidal crystals may prove to be very useful for future studies of nonlinear e?ects in PBG materials in the optical regime.

ACKNOWLEDGMENTS

Ames Laboratory is operated for the U.S.Department of Energy by Iowa State University under Contract No. W-7405-Eng-82.This work was supported by the direc-tor for Energy Research,O?ce of Basic Energy Sciences, and NATO Grant No.CRG940647.

α3

.The distance between the[111]planes in an fcc lattice is R0=α/

FIG.3.Local lattice expansion(a),Field intensity aver-aged in each sphere(b),and Field intensity gradient(c),as a function of the lattice plane forλ=579nm.Solid and dashed curves correspond to the?rst and second transmission reso-nances.

FIG.4.Transmitted intensity versus incident intensity for four di?erent wavelengths as were indicated in Fig.1. FIG.5.Total lattice expansion versus transmitted inten-sity for the four wavelengths indicated in Fig.1.No external pressure is assumed.

570

575

580585590595

Wavelength (nm)

0.00.20.40.60.81.0T r a n s m i s s i o n C o e f f i c i e n

t

1020

5

10

T r a n s m i t t e d I n t e n s i t y

= 579 nm = 581 nm 2λ

λ

Incident Intensity (MW/cm )

100

200300400

Lattice Plane

0.0

0.20.40.60.81.0L o c a l E x p a n s i o n (n m )

λ=579 nm

501001500306050100

030600

40

80

020402040

15

30(a)

(b)

(c)

(d)

T r a n s m i t t e d I n t e n s i t y (k W /c m

)2Incident Intensity (kW/cm )

2

0102030

40

500

1000

T o t a l L a t t i c e E x p a n s i o n (n m )

(α)

(β)(γ)

(δ)

Transmitted Intensity (kW/cm 2

)

比较PageRank算法和HITS算法的优缺点

题目:请比较PageRank算法和HITS算法的优缺点,除此之外,请再介绍2种用于搜索引擎检索结果的排序算法,并举例说明。 答: 1998年,Sergey Brin和Lawrence Page[1]提出了PageRank算法。该算法基于“从许多优质的网页链接过来的网页,必定还是优质网页”的回归关系,来判定网页的重要性。该算法认为从网页A导向网页B的链接可以看作是页面A对页面B的支持投票,根据这个投票数来判断页面的重要性。当然,不仅仅只看投票数,还要对投票的页面进行重要性分析,越是重要的页面所投票的评价也就越高。根据这样的分析,得到了高评价的重要页面会被给予较高的PageRank值,在检索结果内的名次也会提高。PageRank是基于对“使用复杂的算法而得到的链接构造”的分析,从而得出的各网页本身的特性。 HITS 算法是由康奈尔大学( Cornell University ) 的JonKleinberg 博士于1998 年首先提出。Kleinberg认为既然搜索是开始于用户的检索提问,那么每个页面的重要性也就依赖于用户的检索提问。他将用户检索提问分为如下三种:特指主题检索提问(specific queries,也称窄主题检索提问)、泛指主题检索提问(Broad-topic queries,也称宽主题检索提问)和相似网页检索提问(Similar-page queries)。HITS 算法专注于改善泛指主题检索的结果。 Kleinberg将网页(或网站)分为两类,即hubs和authorities,而且每个页面也有两个级别,即hubs(中心级别)和authorities(权威级别)。Authorities 是具有较高价值的网页,依赖于指向它的页面;hubs为指向较多authorities的网页,依赖于它指向的页面。HITS算法的目标就是通过迭代计算得到针对某个检索提问的排名最高的authority的网页。 通常HITS算法是作用在一定范围的,例如一个以程序开发为主题的网页,指向另一个以程序开发为主题的网页,则另一个网页的重要性就可能比较高,但是指向另一个购物类的网页则不一定。在限定范围之后根据网页的出度和入度建立一个矩阵,通过矩阵的迭代运算和定义收敛的阈值不断对两个向量authority 和hub值进行更新直至收敛。 从上面的分析可见,PageRank算法和HITS算法都是基于链接分析的搜索引擎排序算法,并且在算法中两者都利用了特征向量作为理论基础和收敛性依据。

pagerank算法实验报告

PageRank算法实验报告 一、算法介绍 PageRank是Google专有的算法,用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。它由Larry Page 和Sergey Brin在20世纪90年代后期发明。PageRank实现了将链接价值概念作为排名因素。 PageRank的核心思想有2点: 1.如果一个网页被很多其他网页链接到的话说明这个网页比较重要,也就是pagerank值会相对较高; 2.如果一个pagerank值很高的网页链接到一个其他的网页,那么被链接到的网页的pagerank值会相应地因此而提高。 若页面表示有向图的顶点,有向边表示链接,w(i,j)=1表示页面i存在指向页面j的超链接,否则w(i,j)=0。如果页面A存在指向其他页面的超链接,就将A 的PageRank的份额平均地分给其所指向的所有页面,一次类推。虽然PageRank 会一直传递,但总的来说PageRank的计算是收敛的。 实际应用中可以采用幂法来计算PageRank,假如总共有m个页面,计算如公式所示: r=A*x 其中A=d*P+(1-d)*(e*e'/m) r表示当前迭代后的PageRank,它是一个m行的列向量,x是所有页面的PageRank初始值。 P由有向图的邻接矩阵变化而来,P'为邻接矩阵的每个元素除以每行元素之和得到。 e是m行的元素都为1的列向量。 二、算法代码实现

三、心得体会 在完成算法的过程中,我有以下几点体会: 1、在动手实现的过程中,先将算法的思想和思路理解清楚,对于后续动手实现 有很大帮助。 2、在实现之前,对于每步要做什么要有概念,然后对于不会实现的部分代码先 查找相应的用法,在进行整体编写。 3、在实现算法后,在寻找数据验证算法的过程中比较困难。作为初学者,对于 数据量大的数据的处理存在难度,但数据量的数据很难寻找,所以难以进行实例分析。

PageRank算法的核心思想

如何理解网页和网页之间的关系,特别是怎么从这些关系中提取网页中除文字以外的其他特性。这部分的一些核心算法曾是提高搜索引擎质量的重要推进力量。另外,我们这周要分享的算法也适用于其他能够把信息用结点与结点关系来表达的信息网络。 今天,我们先看一看用图来表达网页与网页之间的关系,并且计算网页重要性的经典算法:PageRank。 PageRank 的简要历史 时至今日,谢尔盖·布林(Sergey Brin)和拉里·佩奇(Larry Page)作为Google 这一雄厚科技帝国的创始人,已经耳熟能详。但在1995 年,他们两人还都是在斯坦福大学计算机系苦读的博士生。那个年代,互联网方兴未艾。雅虎作为信息时代的第一代巨人诞生了,布林和佩奇都希望能够创立属于自己的搜索引擎。1998 年夏天,两个人都暂时离开斯坦福大学的博士生项目,转而全职投入到Google 的研发工作中。他们把整个项目的一个总结发表在了1998 年的万维网国际会议上(WWW7,the seventh international conference on World Wide Web)(见参考文献[1])。这是PageRank 算法的第一次完整表述。 PageRank 一经提出就在学术界引起了很大反响,各类变形以及对PageRank 的各种解释和分析层出不穷。在这之后很长的一段时间里,PageRank 几乎成了网页链接分析的代名词。给你推荐一篇参考文献[2],作为进一步深入了解的阅读资料。

PageRank 的基本原理 我在这里先介绍一下PageRank 的最基本形式,这也是布林和佩奇最早发表PageRank 时的思路。 首先,我们来看一下每一个网页的周边结构。每一个网页都有一个“输出链接”(Outlink)的集合。这里,输出链接指的是从当前网页出发所指向的其他页面。比如,从页面A 有一个链接到页面B。那么B 就是A 的输出链接。根据这个定义,可以同样定义“输入链接”(Inlink),指的就是指向当前页面的其他页面。比如,页面C 指向页面A,那么C 就是A 的输入链接。 有了输入链接和输出链接的概念后,下面我们来定义一个页面的PageRank。我们假定每一个页面都有一个值,叫作PageRank,来衡量这个页面的重要程度。这个值是这么定义的,当前页面I 的PageRank 值,是I 的所有输入链接PageRank 值的加权和。 那么,权重是多少呢?对于I 的某一个输入链接J,假设其有N 个输出链接,那么这个权重就是N 分之一。也就是说,J 把自己的PageRank 的N 分之一分给I。从这个意义上来看,I 的PageRank,就是其所有输入链接把他们自身的PageRank 按照他们各自输出链接的比例分配给I。谁的输出链接多,谁分配的就少一些;反之,谁的输出链接少,谁分配的就多一些。这是一个非常形象直观的定义。

相关主题