Google应用PageRank算法给每个网站分配了一个从0～10的数字，它代表了一个网站的重要性。PageRank根据网页之间的超链接来确定一个页面的等级。大家在我博客的右边栏中搜索框的下方可以看到我博客的PageRank，也可以在一些信息查询网站上查询任意网站的PageRank。那么，这个数值是如何计算出来的呢？
其实，PageRank算法的计算过程可以形象的看作“投票”过程。比如我的网站上挂了Wikipedia的超链接，那么我就给Wikepedia投了一票，那么他的PageRank值就会升高。粗略的说，每个网站的PageRank值就是其他各个网站给它“投票”的总和。如果简单的把每一个网站所投的票都看成相同的，这样又会不公平。因为重要的网站所投的票应该有较大的分量。那么，如何确定哪个网站重要，哪个网站不重要呢？还是要根据PageRank。这就产生了一个看似矛盾的过程，我们需要用PageRank值来衡量一个网站的重要性，而它本身的计算中又需要用到PageRank值！
这听起来很像递归，或迭代。PageRank的算法正是基于这种思考产生的。
我们定义PR(A)为A网站的PageRank。为了叙述方便，我们不再使用google的0~10度量，而是使用0~1度量。这和概率的取值范围是一致的。事实上，PageRank就是一个概率(它反映了一个人在网络中不同的页面上随机点击链接会到达某个特定网站的概率)。只不过因为人们不太喜欢看小数，google才更改了度量。
在计算的开始，我们假设考虑的所有网站的PageRank是均匀分布的。这意味着，如果互联网上共有N个网站，那么每个网站的PageRank都是1/N。现在，假设我们仅仅考虑4个网站A,B,C,D组成的一个小网络。初始时，它们的PageRank都是1/4。假如B,C,D的网站上都有且仅有A的链接，那么它们每个人都为A贡献了0.25的PageRank。
（图1）
定义

则PR(A)=0.75
现在假设B网站上还有C的链接，网站D上有其它三个网站的链接。如下图所示：
（图2）
此时，对于B来讲，他把自己的总价值分散投给了两个网站A和C，那么每个网站就应该得到一半的PageRank，即0.125。只有1/3的PR(D)给了A。在这种情况下，

所以，按如此定义，一个网站X上有网站Y的链接，那么它给Y贡献的PageRank等于它的PageRank除以它网站的所有外部链接。（在这里我们做了一个假定，即X网站上对Y站的多个链接不重复计算。不难发现，这样的假定是很合理的。否则像http://worlds-highest-website.com/这样的一个网站上从头到尾全是www.charlesgao.com的链接，那我博客的PageRank就不会这么惨了。—–当然，这是不公平的。）
一个网站u的PageRank的普遍表达式为：

其中B_u是所有链接到u的网站的集合。v为相应网站所链接到的网站总数。
有一点值得注意的是：所有PageRank的计算是同时的。即在计算之前，类似上面的一个有向图已经确定了。然后所有网站的PageRank同时用上面这个公式计算。迭代过程如下：
初始：所有网站的PageRank均等
第一次迭代：每个网站得到了一个新的PageRank
第二次迭代：用这组新的PageRank再按上述公式迭代形成另一组新的PageRank
…
我们最关心的问题是：
如此迭代下去，这些网站的PageRank值最终会收敛么？
大家再回头看我们一开始提到的两个例子。对于图1所示的例子来说，很显然第二次迭代所有的PageRank就都是0了。过程如下：

图2所示的情况也将导致最后所有网站的PageRank变为0。因为没有网站链接到D，那么第一次迭代后PR(D)=0。这将导致PR(B)=0，继而导致PR(C)=0,and then PR(A)=0:

咦？如果PageRank算法是这样的话，那岂不是每个网站的PR都是0了？
为了讨论上面情况发生的条件，我们暂时抛开网站，把问题抽象出来——研究有向图。
首先说明一点，对于如下这种不连通的图：

我们可以分别研究每一部分，而并不影响各个部分的收敛性。 Read the rest of this entry »

　　在动力系统理论中，系统的基本情况称为状态。状态随时间而变化的规律称为动态特性。这个变化的过程可用状态空间（相空间）形象地表示出来，状态空间中的每一个点代表系统一种可能的状态。在状态空间中，动力系统在某一瞬间的全部性态都集中于一点上，而系统演变的情形可以通过状态空间中移动的点来描绘。动力系统随时间演变，其相点在状态空间中将描绘出一个轨迹，我们称之为相空间中的轨道。若时间连续则称之为流；若时间是离散的则称之为映射。
　　状态空间法（相空间法）是现代科学研究中的有用工具，它提供了一种将数字转化为图形的方法。引入状态空间方法最大的优点是便于在研究中观察系统的演化规律。例如单摆，它由两个变量（位移和速度）确定其运动状态，在状态空间中用平面上的点表示其状态的变化过程。
　　耗散系统是指一个远离平衡态的开放系统通过不断地与外界交换物质和能量，在外界条件的变化达到一定阈值时，就有可能从原有的混沌无序状态过渡到一种在时间上、空间上或功能上有序的规范状态，这样的新结构就是耗散结构，或称为耗散系统。
　　耗散系统具有时间单向性。时间变成了不可逆的矢量，单向流逝，一去不返。行为与时间不可分割地熔铸在一起，一起构成了不可逆转的单向过程。我们所遇到的大部分过程都是不可逆转的，比如说热力学第二定律中热传导的不可逆性。我们生存的宇宙是一个我们现在能感知的最大的耗散系统，所以在宇宙中的万事万物都被打上了时间的烙印，不可能再重现历史。
　　吸引子是一种用以刻划状态空间中的长期行为的几何形式，是耗散系统长时间演化的最终归宿。比如说，两杯温度不同的水混合在一起，最终它们将具有相同的温度。这最终的状态对应于状态空间(相空间)中便是吸引子。从数学上讲，吸引子描写了运动的收敛类型，它存在于相平面。简言之，吸引子是指这样的一个集合，当时间趋于无穷大时，在任何一个有界集上出发的非定常流的所有轨道都趋于它，这样的集合有很复杂的几何结构。吸引子可分为定常吸引子、周期吸引子、拟周期吸引子和奇异吸引子四类。

　　定常吸引子(图a)，具有这种吸引子的系统在状态空间中其轨道趋于一个固定点，不管系统从什么初始状态出发，其长期演化的归宿是恒定不变的，总是停在相空间中的一个固定点上。这是最简单的一类吸引子。 Read the rest of this entry »