Google搜索引擎的数学模型及其应用20

发布时间：2016-11-30 10:44

本文关键词：Google搜索引擎的数学模型及其应用，由笔耕文化传播整理发布。

例如，表中T3与T8比赛了两场，各胜一场，故T3；注意到被战胜球队的等级分应该平均分配给各个获胜球；??00.250.16670.250.20.33；??0.20.500.08330.20.3333；现设每个队Ti的等级分xi，这些等级分应由被Ti；∑s；j=1；T12ijxj=λxi（1）其中λ为归一化因子；Sx=λx；即各个队的等级分的计算,转化求这个转

例如，表中T3与T8比赛了两场，各胜一场，故T38=1，T83=1。同理，T14=3表明T1曾3次战胜T4。

注意到被战胜球队的等级分应该平均分配给各个获胜球队，将权重矩阵的各个列向量向量进行归一化处理，得转移概率矩阵S=(sij)为

?? 0 0.25 0.1667 0.25 0.2 0.3333 0 0.125 0.25 0 0 0???? 0.2 0 0.1667 0.0833 0 0.3333 0 0 0.125 0 0 0

?? 0.2 0.5 0 0.0833 0.2 0.3333 1 0.125 0.125 0.1667 0 0?? 0 0 0 0 0 0 0 0.125 0 0 0 0???? 0 0 0 0.0833 0 0 0 0 0 0 0.1667 0? ??? 0 0 0 0.0833 0.2 0 0 0 0 0 0 0?? 0.4 0 0.1667 0.1667 0 0 0 0.25 0.375 0.3333 0.1667 0.3333???? 0.2 0 0.1667 0.0833 0 0 0 0 0.125 0.1667 0.1667 0??? 0 0 0.1667 0.0833 0 0 0 0.25 0 0.3333 0.1667 0.3333?? 0 0.25 0.1667 0.0833 0 0 0 0.125 0 0 0.1667 0.3333??? 0 0 0 0 0.2 0 0 0 0 0 0 0???? 0 0 0 0 0.2 0 0 0 0 0 0.1667 0??S=

现设每个队Ti的等级分xi，这些等级分应由被Ti战胜的那些队的等级分确定，即

∑s

j=1

T12ijxj=λxi （1）其中λ为归一化因子。令x=(x1,L,x12)，则由矩阵乘法（1）可以写成

Sx=λx

即各个队的等级分的计算, 转化求这个转移概率矩阵S的最大正特征值λ所属的正特征向量。直接利用Matlab软件计算得λ=1，相应等级分为

( 0.2731, 0.2085, 0.7144, 0.0302, 0.0026, 0.003, 0.456,0.2416, 0.2503, 0.2042,0.0005, 0.0006)由此可以确定只算获胜局的情况下各队的排名为

T3 , T7, T1,T 9,T8 ,T2,T10,T4,T6,T5,T12,T11

2.2 加权等级分

在实际中，平局也会队双方的排名产生影响，因此也有必要考虑平局对等级分的贡献。因为平局是相互的，所以可以利用无向赋权图的权重矩阵来表达出各队之间的平局关系，即

P=? 0 1 1 0 0 0 0 0 0 2 0 0???? 1 0 0 2 1 0 2 2 1 1 0 0?? 1 0 0 1 0 0 0 0 0 0 0 0??? 0 2 1 0 0 0 0 0 1 1 0 0??? 0 1 0 0 0 0 0 0 0 0 0 2?? ?? 0 0 0 0 0 0 0 0 0 0 0 0??? 0 2 0 0 0 0 0 1 0 1 0 0??? 0 2 0 0 0 0 1 0 0 1 0 1???? 0 1 0 1 0 0 0 0 0 1 0 0?? 2 1 0 1 0 0 1 1 1 0 0 0??? 0 0 0 0 0 0 0 0 0 0 0 2??? 0 0 0 0 2 0 0 1 0 0 2 0???

注意平局的权重矩阵P是对称的。同时注意到被战平球队的等级分也应该平均分配给各个与之战平的球队，故将权重矩阵的各个列向量向量进行归一化处理，得转移概率矩阵 ? 0 0.1 0.5 0 0 0 0 0 0 0.2857 0 0???? 0.25 0 0 0.4 0.3333 0 0.5 0.4 0.3333 0.1429 0 0?? 0.25 0 0 0.2 0 0 0 0 0 0 0 0???? 0 0.2 0.5 0 0 0 0 0 0.3333 0.1429 0 0?? 0 0.1 0 0 0 0 0 0 0 0 0 0.4??? ? 0 0 0 0 0 0 0 0 0 0 0 0??? 0 0.2 0 0 0 0 0 0.2 0 0.1429 0 0??? 0 0.2 0 0 0 0 0.25 0 0 0.1429 0 0.2???? 0 0.1 0 0.2 0 0 0 0 0 0.1429 0 0?? 0.5 0.1 0 0.2 0 0 0.25 0.2 0.3333 0 0 0???? 0 0 0 0 0 0 0 0 0 0 0 0.4?? 0 0 0 0 0.6667 0 0 0.2 0 0 1 0???P=

根据常识，在一场比赛中平局出现的概率为1。同时，考虑到通常平局和获胜局的得3

分比为1:3，我们可以对平局和获胜局的转移概率矩阵进行加权处理，得到下面的加权权重矩阵

W=12×1×P+×3×S=33

? 0 0.5333 0.5 0.5 0.4 0.6667 0 0.25 0.5 0.0952 0 0???? 0.4833 0 0.3333 0.3 0.1111 0.6667 0.1667 0.1333 0.3611 0.0476 0 0?? 0.4833 1 0 0.2333 0.4 0.6667 2 0.25 0.25 0.3333 0 0???? 0 0.0667 0.1667 0 0 0 0 0.25 0.1111 0.0476 0 0 ?? 0 0.0333 0 0.1667 0 0 0 0 0 0 0.3333 0.1333??? ? 0 0 0 0.1667 0.4 0 0 0 0 0 0 0???? 0.8 0.0667 0.3333 0.3333 0 0 0 0.5667 0.75 0.7143 0.3333 0.6667?? 0.4 0.0667 0.3333 0.1667 0 0 0.0833 0 0.25 0.3810 0.3333 0.0667???? 0 0.0333 0.3333 0.2333 0 0 0 0.5 0 0.7143 0.3333 0.6667?? 0.1667 0.5333 0.3333 0.2333 0 0 0.0833 0.3167 0.1111 0 0.3333 0.6667??? 0 0 0 0 0.4 0 0 0 0 0 0 0.1333??? 0 0 0 0 0.6222 0 0 0.0667 0 0 0.6667 0???同样，被战胜或胜战平球队的等级分也应该平均分配给各个获胜队和与之战平的球队，故将

权重矩阵的各个列向量向量进行归一化，得转移概率矩阵W=(wij)为

????? 0 0.2286 0.2143 0.2143 0.1714 0.3333 0 0.1071 0.2143 0.0408 0 0?? 0.2071 0 0.1429 0.1286 0.0476 0.3333 0.0714 0.0571 0.1548 0.0204 0 0???? 0.2071 0.4286 0 0.1 0.1714 0.3333 0.8571 0.1071 0.1071 0.1429 0 0? ? 0 0.0286 0.0714 0 0 0 0 0.1071 0.0476 0.0204 0 0???? 0 0.0143 0 0.0714 0 0 0 0 0 0 0.1429 0.0571???? 0 0 0 0.0714 0.1714 0 0 0 0 0 0 0?? 0.3429 0.0286 0.1429 0.1429 0 0 0 0.2429 0.3214 0.3061 0.1429 0.2857???? 0.1714 0.0286 0.1429 0.0714 0 0 0.0357 0 0.1071 0.1633 0.1429 0.0286?? 0 0.0143 0.1429 0.1 0 0 0 0.2143 0 0.3061 0.1429 0.2857???? 0.0714 0.2286 0.1429 0.1 0 0 0.0357 0.1357 0.0476 0 0.1429 0.2857?? 0 0 0 0 0.1714 0 0 0 0 0 0 0.0571???? 0 0 0 0 0.2667 0 0 0.0286 0 0 0.2857 0???W=

现设每个队Ti的等级分xi，这些等级分应由与Ti战平的那些队的等级分确定，即

∑w

j=1

T12ijxj=λxi （1）其中λ为归一化因子。令x=(x1,L,x12)，则由矩阵乘法（1）可以写成

Wx=λx

即各个队的等级分的计算, 转化求平局的权重矩阵T的最大正特征值λ所属的非负特征向量。直接利用Matlab软件计算得λ=1，相应等级分为

(0.3173, 0.265,0.6627, 0.0981,0.0118,0.009, 0.4435, 0.2473,0.2419,0.2521,0.0026,0.0110) 由此可以确定在综合考虑获胜局和平局的情况下各队的排名为

T3, T7, T1,T 2,T10 ,T8,T9,T4,T5,T12,T6,T11

2.3 等级分的随机冲浪模型

在大多数时候，竞技比赛的结果都是两队之间实力的客观反映。但是，竞技比赛的结果有时具有一定的不确定性，它很容易受到某些偶然或人为因素的影响。为了消除这些不确定因素的影响，我们可以建立等级分的随机冲浪模型。

设球队的实力能确定比赛的结果的概率为d，即强队因为不确定因素输掉给任意一支球队的概率为1?d。则可得下面的转移概率矩阵

W=d*W+1?d*eeT n

其中，，e为分量全为1的n维列向量，从而eeT为全1矩阵；d∈(0,1)为权重因子，在实际中可以根据历史数据确定。同样，各个队的等级分的计算, 转化求转移概率矩阵W最大正

特征值所属的正特征向量。

下面着重分析权重因子d∈(0,1)的变化队排名的影响。为此，我们利用Matlab软件计算出了d取不同的值时的排名情况

0.95

0.85

0.4 球队排名 T3, T7, T1,T 2,T10 ,T8,T9,T4,T5,T12,T6,T11 T3, T7, T1,T 2,T10 ,T8,T9,T4,T12,T5,T6,T11 T3, T7, T1,T 2,T10 ,T9,T8,T4,T12,T5,T6,T11 T3, T7, T1,T 2,T8 ,T9,T10,T4,T12,T5,T11,T6

注意：当权重因子d以0.05为步长在表中所列值之间变化时，球队的排名不变。例如，当0.45<d<0.85时，排名均为T3, T7, T1,T 2,T10 ,T9,T8,T4,T12,T5,T6,T11。

从表中可以看出，只要权重因子d>0.5，根据等级分的排名结果具有良好的稳定性；并且，权重因子的变化只对没有比赛场数较多的球队的有较大影响。因此，等级分随机冲浪模型可以成功地处理数据缺损方面的困难。

参考文献：

[1] Sergey Brin and Lawrence Page. The anatomy of a large - scale hypertextual web search engine [C]. In: Proc

of 7th World Wide Web Conf. [C].

[2] Markus Sobek. A Survey of Google's PageRank [EB/OL].

[3] 李大潜. 中国大学生数学建模竞赛[M]. 第二版. 北京: 高等教育出版社, 2001

[4] 姜启源,谢金星,叶俊. 数学模型[M]. 第三版. 北京: 高等教育出版社, 2003

[5] 蔡大用. 关于足球队排名次问题的几点评注[J]. 数学的实践与认识. 1994, 2: 95－96

[6] 曾文艺,崔宝珍. 模糊聚类分析在在足球队排名中的应用[J]. 数学的实践与认识. 1999,29(2):179-183

Title

ZHAO Guo

（Department of ****, University, City ZipCode, China）

Abstract: *Abstract.*

Key words:

*key word; key word*

下载地址：Google搜索引擎的数学模型及其应用20.Doc

　　【】