关于《社交网络》中Facemash网站算法(转载)

copy from http://www.douban.com/note/122191956/

《社交网络》中,Eduardo在玻璃上写下了两个式子,Mark以此算法,建立了www.facemash.com,从学校内的网站抓取大部分女生的照片上传。男生们在凌晨四点钟疯狂浏览此网站,在随机跳出的两副女生照片中,选择两者较“美”者,一举出名,导致哈佛网络瘫痪。

不过,那两个貌似很帅气的式子写得有点问题,分数线下方是1+10的幂次,而非10的倍数。
否则两者等级分差距过大的话,会造成分母为负数,从而期望为负……(王八翻不了身)

根据Wiki的介绍,此排名系统出自于匈牙利裔美国物理学家Arpad Elo,最初应用于国际象棋排名,现在也广泛应该于足球、篮球等运动。中文称为等级分排名。

Elo假设:
1.参赛选手在每次比赛中的表现成正态分布;后来普遍认为Logistic分布更为合理

2.在一局比赛中,赢的一方被认为表现较好,输的一方被认为表现较差;若平局,则双方表现大致相当。虽然这个假设貌似很稀松平常

算法如图:


Ea为选手A的期望表现,Ra为选手A当前的等级分排名。
当选手A和B进行比赛时,可根据公式算出两选手的期望表现。
Ea+Eb=1
胜方得1分,负方得0分。(在电影中,不会出现平局)

如果选手的表现比期望要好,那么此选手的排名应该上升。相反,若表现不如期望,则排名会下降。

Sa为选手A本局的得分(1或0),Ea为选手A的期望表现。K为常数,在大师级象棋赛中通常取16。得到的Ra’为选手本局比赛后的等级分排名。

初始可认为每个人的等级分排名为0。

第一局是A和B进行比赛。此时Ra=Rb=0,Ea=Eb=0.5。
假设本局A胜B负,则A的得分为1,B的得分为0。
Ra’=0+16*(1-0.5)=8
Rb’=0+16*(0-0.5)=-8

所以每进行一次比赛,就会有新的等级分排名产生。4小时内巨大的参加人数与点击量,让这个游戏格外邪恶也好玩儿。毕竟都是自己周围的女生XD

参考文献http://en.wikipedia.org/wiki/Elo_rating_system
=======================

若有错误的地方,请提出,便于改正。

本身不懂国际象棋排名制度,也不懂博弈论。连Logistic模型神马的,也忘得差不多了……

Related posts:

Leave a Reply

Your email address will not be published.