技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 数学之美:《社交网络》中Facemash算法分析

数学之美:《社交网络》中Facemash算法分析

浏览:5780次  出处信息

    在电影《社交网络》的开始有这么一段,扎克博格由于被女友甩了,所以需要做一个网站(www.facemash.com),用来推选哈佛最漂亮的女生。网站的逻辑非常的简单,就是系统从照片库中随机挑出两幅女生照片,选择两者较“美”者。就是这么一个网站在上线两小时(周末凌晨两点到四点)内点击量达到了2万2千次,从而导致了哈佛网络的瘫痪。(备注:最近华中科技大学女生的照片也被类似的放到了网上评比,并且使用山寨的域名www.hust-facemash.com)

    信息的关注应该注意到,上述功能中涉及到一个排名规则,是由扎克博格那位同学提供的,他把公式写在了窗户上,如下截图:

    

    上面的公式主要作用作用是用来对进行女生的分数进行评比,从而确定哪些是最优质女生。不过让人遗憾的是电影中给出的这个公式是错误的公式,真正的公式应该如下:

    

    即分数线下方是1+10的幂次,而非10的倍数。上诉的排名公式并非扎克博格等人原创,而是出自匈牙利裔美国物理学家Arpad Elo,这算法叫作: Elo Rating ,最初应用于国际象棋排名,现在也广泛应该于足球、篮球等运动。中文称为等级分排名。

    下面就来对算法进行解读,Arpad Elo认为:

  • 参赛选手在每次比赛中的表现成正态分布;后来普遍认为Logistic(逻辑斯蒂)分布更为合理。
  • 在一局比赛中,赢的一方被认为表现较好,输的一方被认为表现较差;若平局,则双方表现大致相当。
  •     公式中出现的

        Ea/Eb为选手A/B的期望值,即A/B选手获胜的概率。当选手A和B进行比赛时,可根据公式算出两选手的期望表现。

        Ra/Rb为选手A/B当前的等级分排名。

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

        

        Sa为选手A本局的得分(1或0),K为常数,数值越大比分变动越快,在大师级象棋赛中通常取16。用这个公式来计算出选手A本局比赛后的等级分排名。

        另外关于Logistic的分布图如下:

        

    建议继续学习:

    1. 社交网络学习笔记――微博篇    (阅读:2203)
    2. 社交网络语法:关于“Checkin”    (阅读:2055)
    3. 基于知识链结构的社交网络    (阅读:1755)
    4. 基于WEB2.0的社交网络浅析    (阅读:1639)
    5. 社会化媒体的社交网络之路    (阅读:1563)
    6. 社交网络的自我实现及社交要素    (阅读:1165)
    QQ技术交流群:445447336,欢迎加入!
    扫一扫订阅我的微信号:IT技术博客大学习
    © 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

    京ICP备15002552号-1