2007年02月13日

  最近,不少Blog都在谈论一个名叫“Review Me”的新型广告发布系统。

  这个广告系统只针对Blog而推出,类似付费评论的模式,并且做为入门测试,用户可以先来评论一下ReviewMe自己,ReviewMe也会为此支付一定金额。ReviewMe的主页上说,已经为这类评论分发了25000美元了。

  评论的操作很简单,先登录ReviewMe注册一个帐号,然后提交一个Blog地址(似乎只能提交独立域名的Blog,不支持托管BSP的地址),目前看来没有限制中文用户,注册完成后,点中间的图片提交评论ReviewMe的申请,这样,你需要在剩下的48小时内写一篇评论ReviewMe,内容需要满足以下条件:

  1、你必须以某种形式声明这篇文章是付费文章,比如在文章中加入“付费文章”或者“广告”等文字。

  2、评论的字数必须至少200字,文章多长是没有限制的,但必须在200字以上,这个字数指的的英文的字数,目前还不知道换算为中文应该是多少字。

  写完文章后,将文章地址提交到系统中,就可以完成一次评论。

  付费方法有两种,一种是通过支票方式支付,一种是通过PayPal支付,就速度来说使用PayPal收款速度最快,不过钱是放在PayPal中,美国用户可以将钱收回到自己银行帐号中,中国大陆的用户就比较麻烦,可以通过支票收钱,也可以通过自己的招商银行的香港一卡通将美元存入香港的帐户,这种方法会自动将美元转换为港币,有一些汇率损失。

  Review Me这种广告形式还是很独特的,相当于一种付费软文。Review Me做为一种中介,介于广告商和Blogger之间,广告商通过Review Me系统提供的Blog价格(比如200美元价格),可以提交一张需求评论的订单,这时候Blogger就需要在一定时间内写一篇评论文章,从而获得100美元的收入,而Review Me自己也获得100美元的分成。

  这种模式可以避免一些网络欺诈,Review Me做为中介商可以协调各方面的利益,然而做为中文Blogger来说,Review Me这种广告模式是不可能给Blogger带来稳定的收入。具体分析原因如下:

  首要的原因是,广告是由广告商驱动的,广告商需要选择一个最合适的Blogger来写软文,而目前这套系统是英文的,广告客户也大部分是英文客户,不太可能去选择中文的Blogger来写广告。

  其次,写这种软文对于Blogger自身来说也是一种伤害,写得越多,伤害越大,读者喜欢看的是有价值有意义的文章,没有读者喜欢整天看广告,时间是宝贵的,浪费别人的时间无异于谋财害命。

  再次是价格因素,如果我是广告商的话,我会思考这样一个问题,我通过Review Me做为中介来发布广告需要200美元,而Blogger自己会获得100美元,那么如果我直接向Blogger付款150美元不是也可以达成这笔交易吗?Blogger自己可以多得50美元,而我则可以节省50美元,这是一个双赢的结果,何乐而不为呢?

  最后是广告的效果问题,Blogger广告的效果有多少,一直是一个难以判断的问题,一般Blogger不会自己败坏自己的名誉来大量写付费软文,这和广告商的预期是恰恰相反的,广告商如果发现自己投入的资金无法获得足够的回报,那么广告商就会放弃这种广告行为,而转向类似Google Adwords这种传统广告形式,因为传统广告回报稳定且效果明显,这样循环下去的结果就是类似Review Me的这种广告形式彻底破产。

  不过话说回来,Review Me这种广告形式还是很有创意的,其前期似乎处于“烧钱”的状态,具体这种广告是否成功,我们只要拭目以待就可以了,因为一个企业不可能永远都处于“烧钱”的状态,烧到一定地步再不盈利,那就只有破产了。因此我相信,如果明年的今天,Review Me还没有倒闭的话,那么这种广告就有一定的市场认可。

最近使用FeedBurner地址订阅我的rss的用户可能看到内容后面广告了吧?(只在blog上的有,flickr和del.icio.us后面的没有)

FeedBurner的feed广告是需要经过先批复再显示的,给blog作者一个控制发布内容的机会。目前FAN以国外广告为主,按千次展现收费,收益 1-5$ 左右。

之前2轮广告投放我都拒绝了,英文的广告实在没有什么相关性可言。本期广告好像是关于一部电视剧/游戏?
* 50 impressions
* 1 clicks for 2.000% CTR
一个是关于网络硬盘的。
* 249 impressions
* 1 clicks for 0.402% CTR

目前Feed型广告的一些特点:
1 feed中的广告大部分是图片型的:可能是考虑到大部分RSS阅读器不支持JS脚本执行和iframe吧;
2 按照展现付费:当然也有点击和点击率的统计;
3 幅面固定:现在是468*60的固定图片;
4 发布轮播:目前的发布时间都是按照天来计划的;

但是从广告商的角度来看FEED广告:
优点:
FEEDBURNER可以提供一个相对集中的高质量阅读人群;
feed的主题相对固定/同阅读人群特征明显:可以基于feed来控制投放领域目标(定向有针对性);

缺点:
1 传统基于CPM结算的投放有容易作弊的弊端;
2 基于FEED的传播可能非常受到阅读器的影响:比如在GReader的阅读中,用户如果是在浏览标题模式下:仍然会向feedburner发出广告图片请求,但是仍然是看不到广告图片的。

而从发布者的角度:发布者未来可能更希望自己来控制feed的广告
1 RSS源端的内容发布:目前FEED上的广告发布是feedburner这样的feed转发商控制的,未来可能也允许作者在原始的FEED条目中增加。通过修改自身的RSS模板,将广告固定放置在FEED模板中;
2 轮播机制:由于不可能动态发布,所以发布的图片地址和点击的目标地址可能都会相对固定:然后通过在广告服务端管理来控制的图片内容和点击目标地址的轮播;

       见到KU6的CEO阎小强的时候,在他刚参加完一个战略合作伙伴的新闻发布会后,而在采访结束之后,他还要赶去参加另一场研讨会。这个自称到年底就可以实现盈利的视频网站CEO,确实异常忙碌。不过,或许是因为有了盈利的信心,阎小强一直神采飞扬,丝毫看不出疲态。

  Enet:和同类的视频网站不同,KU6好像已经有了收入不斐的广告。它的数量到底有多少?KU6是否已经实现的盈利?

  阎小强:通过和伊利的合作,我们已经拿到了几百万的资金。然后我们又和联想签了单子,不久之前又签订了海信。今后人们还可以看到有多家知名企业在KU6上投放广告。因此,我想到年底我们完全可以实现自我运转。

  

  Enet:和KU6同类型的视频网站也有很多。KU6凭什么可以在他们还入不敷出的情况下可以实现收支的平衡,可以有如此大的广告单。

  阎小强:我想这依仗的是我们率先推出完整的商业模式,并且成功得到客户的认可,这是其他网站都没有做到的。

  Enet:那是一个何样的商业模式?

  阎小强:我们的商业模式说起来很简单,就是有钱一起赚,让网友和我们一起分享收入。也就是说,我们会在视频博客作品后嵌入广告,然后根据广告展示次数与作者共同分享广告收入。我们根据人气把博客分为九段,段位越高分成比例也越高。以次来和上传作品的作者达到共赢。

  Enet:之前有磊客中国等数家网站也推出了与播客一起分享广告收入的模式,而且从创建的时间上他们都比KU6早许多。KU6凭什么就可以在短短数月中拿到如此大的单子。

  阎小强:和伊利的合作还是时机的成熟,我们先推出合适的模式,让客户能看到这种良性循环。正好这个时机他们也想在这个时间搞一个视频推广的活动。而作为广告主,很多企业都有着尝试新媒体广告投放效果的资金,这对于我们都是机会,而且我们出色的营销能力也是促成我们广告大单的主要因素。

  Enet:目前视频类网站只要是点播和直播。KU6主要是以直播为主,将来会不会设计到点播?

  阎小强:新的业务模式我们会考虑清楚后再决定。

  Enet:如果资金更加雄厚,更加庞大的门户网站进入网络视频领域,KU6认为自己是否还具备竞争力?而和同级别的对手相比,KU6的竞争力又在哪里?

  阎小强:相比传统的门户网站,视频网站可以让广告主更准确的看到流量,准确反映出广告投放的效果。而门户可能一时还不能建立起这样的模式。而和同行相比,现在中国视频互联网的大局也还没有确定,在中国,这个领域还没有第一,也就意味着谁也都有可能成为第一。

  Enet:对于视频互联网,它的广告前景,KU6如何判断?

  阎小强:除了传统的图文广告,和视频独有的在短片,片头片尾加广告外。我们KU6认为,视频网站的最大卖点就是启发网友去创作广告。充分发挥草根的智慧。这也是广告主们最期待的。我们也会推出很多的网络红人,让网络视频更加热闹起来。

  Enet:一些视频网站已经已经开始尝试一些专业化的制作,KU6在这方面又作何打算。

  阎小强:我们也在开始这方面的尝试,而且作为网络视频的发展方向,将来电视领域的大腕也会有着草根的创作。我有一个做电视的表弟,现在就是编剧本尝试着在KU6上传短片。将来草根+专业化会成为趋势。同时,网站还可以通过资金的运作吸引更多的专业制作群来加入我们,这样做会对所有的草根网友起到很好的引领、甚至是指导作用。

正值全球互联网市场封杀“弹出式”广告之际,一些新兴的广告形式却顶风而上。这些广告软件开发商表示,新一代的广告形式相对比较温和,不会令用户感到厌烦。

  本周,180solutions公司推出了一款新型、有效的广告软件,该广告软件的特点是相对比较温和,可能不会像“弹出式”广告那样激怒互联网用户。公司表示,该软件可以引导用户访问一些免费的音乐下载站点或其他内容站点,但在此期间屏幕上会闪烁数量有限的几条广告。

  180solutions此举无疑是一招险棋。目前,互联网用户对于某些广告简直达到了深恶痛绝的程度。而且,这其中就包括公司此前的“n-Case”产品。但180solutions此次新出的广告软件的确得到了不少厂商的支持,其中Spectrum投资公司对此投资了4000万美元。

  无独有偶,英国的“Vibrant媒体”公司最近也在开发一套广告系统,它主要通过互联网上的文章关键字来选提供相关的广告内容。公司表示,该系统下周将在美国市场上推出。并且,他们还有望与搜有巨擎Overture达成合作关系。

  目前,由于全球IT市场的反弹,在线广告业务也开始逐步回升。2003年第四季度,网络广告销售额经过多年的下滑后终于再次反弹,增长幅度达到了38%,收入为22亿美元。分析家预计,今年的网络广告收入将继续增长10%左右,销售额有望达到80亿美元。Forrester分析师CharleneLi对此表示道:“哪里由金钱,哪里就有创新。”

  180solutions成立于1999年,只要以开发广告软件为主。公司此次推出的新型广告软件被称为:“Zango”,是一款可下载的应用软件。它可以监视用户的互联网行为,然后用户在网上购物或使用搜索引擎时,该软件就会根据这些数据向用户提供相应的广告内容。

  例如,用户在使用雅虎或Google进行搜索时,如果您在搜索框中键入“旅馆”时,那么Zango搜索助手就会在另一浏览器窗口中打开Expedia的主页。如果键入“卡西诺(赌博游戏)”,那么就会打开888.com的主页。

  事实上,Claria和WhenU等公司以前也使用过相似的广告形式。但180solutions的软件由许多独特之处。其一,Zango打开的只是广告商的主页;其次,180solutions此次与网络出版商展开积极合作,他们可以从Zango下载中获取一定的费用。此前,网络出版商则恰恰痛恨广告影响了其网站内容。

  180solutions首席执行官KeithSmith表示:“用户的利益是他们可以在没有广告打扰的情况下浏览网站内容。我们将这个概念称之为‘时间转移’,用户只要安装我们的软件既可不受广告骚扰,只有当用户购物或在线搜索时,才会出现相关的广告内容。而且,用户每天只会遇到2-3条广告。

  目前,180solutions已经与部分互联网站点签订了合作协议。

  Vibrant的产品被称为“IntelliTxt”,主要是通过关键字提供广告内容。当读者将鼠标放在某个文字上时,此时屏幕上就会出现包含有关这些文字的更多内容的对话框,如果用户点击这些信息,就会进入广告商的网站。

  例如,如果你正在阅读一篇有关微软的游戏策略的文章,如果你把鼠标放在其中的文字“互联网接入”上面,那么用户点击文字既可访问AOL9.0的广告网页。

  此前,也有过一些企业提供过类似的服务,但因为没有得到网络发行商的支持而流产。此次,Vibrant吸取以前的失败教训,已经同Hearst、Motley及Overture等多家网站签订了合作协议。但有分析家表示,Vibrant的服务可能会使消费者感到莫名其妙,甚至会有一种被欺骗的感觉。

  正当“弹出式”广告正在成为网民的“公敌”之际,Vibrant和180solutions的举措表明新一代的互联网广告形式已经诞生。此举同时表示,面对价值40亿美元的付费搜索市场,互联网运营商绝对不会无动于衷。无论成功与否,新一轮的在线广告再次向我们袭来。

Google Adsense是Google的广告服务,也就是Google的广告联盟,据调查,Google广告联盟是在国内占据着很大的份额,因此也引出了许多的问题,下面这篇文章是最常见的问题整理,作为我个人收藏之用。 

 

  1.申请/注册

  问:如何申请Google Adsense 帐户,申请需要什么条件.

  答:在申请前请仔细阅读adsense政策 与 条款

  政策:http://www.google.com/adsense/policies

  条款:http://www.google.com/adsense/localized-terms

  申请adsense需要有自己的网站,请确保页面上的尽可能没有无法打开的链接(即使只有1页你也会通过审核).

  申请地址:http://www.google.com/adsense/?hl=zh_CN

  问:申请adsense帐户的审核周期是多久?

  答:填完申请表并提交后,请查阅adsense发送给您的电子邮件。在您确认EMail地址后,adsense将审核您的申请,并在 2 到 3 天内EMAIL通知你的申请是否通过。

  2.投放问题

  问:我可以手动修改adsense代码吗?

  答:不可以.

  问:一个页面可以投放几个推荐产品?

  答:可以为每个推荐产品放一个广告,推荐广告数量与其他广告单元不冲突.

  问:一个网页中最多可以投放几组广告代码?

  答:3组adsense广告代码,2组adsense for search,1组链接单元, 4 个产品推介(每种产品仅限1个)

  问:adsense适合投放于什么样的网页,有要求吗?

  答:adsense不能投放于非内容页(注册页,错误页,登录页等),容易产生版权纠纷的页面,非法页面.具体请参照adsense政策.

  问:我可以将adsense广告投放到多个网站吗?

  答:可以,请确保您对该网站有所有权并且该网站符合adsense 政策.

  问:我可以透过IFRAME来投放广告吗?

  答:可以,但是如果选择用iframe来投放广告则展示广告的网页页中只能有1个iframe来投放adsense 广告.例如[你的 Adsense 广告代码]

  问:可以在一个网页中同时投放百度主题推广与adsense吗?

  答:不可以,adsense禁止将与其构成竞争或摹仿adsense表现形式的广告一起投放.(请大家注意,最近国内出现很多类adsense广告,例如网易竞价,多维搜索,百度主题,51ads文字广告,这些广告都极力摹仿adsense如果大家需要投放些类广告请先与adsense进行确认!)

  问:可以把竞争性的广告做为adsense的替代广告吗?

  答:当您的网页中只放了一组adsense广告代码时是允许的,但是当代码多于一个时不允许将竞争广告做为adsense替代广告(因为有可能同时出现构成竞争关系)

  问:我可以为adsense for search 预填搜索内容吗?

  答:这种情况不被允许,政策中有明确的说明.

  问:我可以在使用adsense for search同时也使用其他公司的搜索代码吗?

  答:不可以,如果你要使用adsense for search则整个网站中不允许出现其他公司的搜索产品.

  3.支付问题

  问:adsense什么条件开始付款?付款周期是多久?

  答:付款周期为1个月, 如果你在某月底之前帐户余额超过100美元, 那么在下个月22-25号就会显示支付信息.

  问:支票已经寄出了,大概多久能收到啊?

  答:27、28、29日会打印并寄出支票,在中国的一级城市如北京、上海,会在下一个月的5-7日收到支票.由于中国地区用户改由香港投递支票,所以大家收到支票的时候会比以往有所提前!

  问:我已经收到支票了,怎样才能兑换成RMB,需要多久?

  答:收到支票后可以到一些大型银行(如中国银行)去办理托收,时间大约为40-60天.(从2005年12月开始支票将由香港寄出,大陆的1级城市有望在2-3天内收到支票,原来的安全快递改为挂号信,手续费10$)

  问:如果没收到支票应该怎么办?

  答:你可以在当月25日以前申请取消上一张支票, 如果在1号—15号之间取消, 则还来得及赶上下一个月的支付.

  4.帐户问题

  问:一个人可以申请多个帐户吗?

  答:不可以,除非得到adsense的授权.如果一个帐户因作弊被adsense封掉,那么他将永远不能参与adsense广告的发布,请大家珍惜自己的帐户!

  问:什么是个人识别号码(pin)?

  答:当 AdSense 发布商累积收益到达$50美元时,adsense会邮寄给发布商一个个人识别号码 (PIN)。以帮助adsense验证发布商地址和保护发布商的个人信息。

  问:我何时能收到我的个人识别号码?没有收到PIN码怎么办?

答:当您的帐户收入达到 $50 美元,您的个人识别号码 (PIN) 就会生成,并在 3-5 天内通过邮寄寄给您。个人识别号码应在寄出后的 2-4 周内到达。您所在地的邮政服务也可能会造成时间延长。如果未收到个人识别号码,您可以在先前的个人识别号码生成 2 周后申请替代个人识别号码。

  问:为什么我没有收到过PIN码?没有PIN码能收到付款吗?

  答:早期注册和新注册的用户不用PIN码,这个时期注册的用户不需要PIN码!

  问:在我的帐户中显示的USD与eCPM是什么意思?

  答:USD是美元的缩写.eCPM是指千次广告展示所获得的收入.

  问:ECPM是如何计划的?有什么用?

  答:ECPM是你的收入乘以1000然后去除你的广告展示次数.所以,收入越高而相对展示次数越少,ECPM就越高,其作用类似于统计广告的展示效率.

  问:个人信息中的电话号码如何填写?

  答:例如:86-10-8193XXXX.注意去掉区号前面的0(非必须),如果是手机,区号处写0,比如86-0-13901088888.

  5.常见问题

  问:我的点击率高达xxx正常吗?

  答:adsense广告计费与点击无关,如果您正常投放那么点击率为多少都没有关系,但是提醒您,每当点击率意外上生的时候您应该有防范意识防止被恶意攻击,异常点击率与频繁的无效点击通常是攻击的结果.推荐您使用www.adsenser.org的点击统计系统来跟踪您的点击情况!

  问:不小心点击了自己的广告怎么办?

  答:如果是误点请放心,adsense会判断点击为无效点击.不过请杜绝这种情况的再次发生,adsense会根据您所在地区IP段以及您登录后台的IP与cookies等等很多因素来判断点击,您的行为会被adsense察觉.

  问:我对自己网站展示的广告感兴趣怎么办?

  答:可以用Google Adsense Previrew工具,具体操作请参照:https://www.google.com/support/

  问:为什么我网站上的广告都是英文的?

  答:如果你本身是中文站点那么出现这种现象的原因,大多是由于adsense还没有抓取你的网页内容而已.(最常出现的两个原因1.刚刚开始投放adsense.2.出现英文广告的那个页面访问量非常少),对于此种现象大家不必在意,随着时间以及访问次数的增加广告会越来越匹配你网页中的内容

  问:为什么有时我无法登录Google Adsense后台?

  答:请先确认您的计算机与互联网连接正常,如果连接正常还是无法登录后台也没有关系,此时一般是服务器在维护,不影响广告收入,只是暂时无法进入后台操作.

  问:Google Adsense是否允许通过JS调用广告代码?

  答:目前可以使用JS调用广告,但是不能有影响广告显示和点击的设计。

在电子商务非常活跃的美国,联盟营销已被作为一种新颖、务实的商务模式而倍受推崇。虽然目前在中国,联盟营销还处于初级阶段。但随着中国网络广告的快速发展,中国有能力迅速建立并拥有最好的网络联盟营销体系。

联盟营销历史

联盟营销(Affiliate Marketing), 通常指网络联盟营销,也称联属网络营销。 最初的网络联盟营销是伴随着某些大型广告主的发展而兴起的,一些大型的商家将自身作为广告主来召集联盟会员,联盟会员们通过播放广告主的广告,为商家带来源源不断的客户和销售额,并从中获取一定收益。关于联盟营销的历史存在着一些争论。有些人认为,联盟营销方式起源于1996年的亚马逊网站(Amazon.com)。Amazon通过它为数以万计的网站提供了额外的收入来源,且成为网络SOHO族的主要生存方式。但实际上,亚马逊并不是第一个发起联盟营销的企业,CDNow公司才是首创这种营销形式的企业。1994年11月(几乎比亚马逊提前了一整年),CDNow公司推出了buyweb计划。在buyweb项目中,CDNow公司首次提出了“affiliate或associate”即联盟的概念,旨在通过独立的在线网站投放广告,从广告点击流导致购买行为中收取一定的费用。这一新的网络广告收费模式也在整个网络广告行业开创了基于效果的网络付费模式新纪元,此模式在现今已成为整个产业的主流。

随后1995年10月的AutoWeb公司,1996年4月的EPage公司,以及1996年11月的Kbkids/BrainPlay公司都纷纷在亚马逊之前开始开展联盟营销项目。起初的联盟营销项目都是单个广告主和多个联盟会员直接打交道,而且业绩跟踪和结算完全由广告主负责。这样便产生了很多的负面因素,如在业绩的跟踪、确认、结算等方面的信用问题等。为了解决这个问题,一个新的主体应运而生:在当今的联盟营销模式中,除了存在广告主和联盟会员这两个主角外,又产生了另一主角——联盟营销管理平台,通常由专业的第三方联盟营销公司提供。这是一个专为广告主、联盟会员提供的独立且公开、公正、透明的管理运行平台,大大减少了广告主的人力、物力、技术、结算和管理等负担。这是一个双赢的平台,一方面,广告主可以集中精力做自己的主营项目而不去考虑广告投放问题,完全由中间服务商代理;另一方面,联盟会员可以放心的选择广告主,不去顾虑广告佣金的收取问题,因为中间平台会替广告主按时支付广告佣金。这样,“三足鼎立”的模式确定后,联盟营销的网络营销模式基本发展成熟。

1996年全球首家提供联盟营销解决方案的供应商LinkShare成立。现在,LinkShare拥有全球最大的Internet网上联盟营销网络(超过1000万的网络联盟会员和合作伙伴),他用自己专门的联盟营销技术解决方案为广告主提供其所需的服务和工具,设计、管理、优化每一个联盟营销项目。另一家联盟营销解决方案供应商BeFree也于1996年开始运作。如今,在电子商务非常活跃的美国,联盟营销已被作为一种新颖、务实的商务模式而倍受推崇。

目前在我国,联盟营销还处于初级阶段,虽然早在2000年就出现了网络联盟营销,有部分个人或企业开始涉足这个领域,但规模还不大,一般的网络营销人员和网管人员对联盟营销还比较陌生。这主要是受中国网络广告模式的深刻影响,价值链的中间成分还不够成熟,信用体系不完善等因素影响。但随着2003年中国网络广告的快速发展,专业的第三方网络联盟营销公司也应运而生。我们有理由相信,随着广告主、联盟会员和第三方联盟营销管理平台的不断成熟,中国有能力迅速建立并拥有属于自己的最好的网络联盟营销体系,促进中国网络联盟营销事业的蓬勃发展。

联盟营销三要素

联盟营销(Affiliate Marketing) 也称网络联属营销,指的是一种网站A为网站B放置广告按钮,然后A从为网站B带来的销售额中获得回佣的一种网络广告营销模式。有些广告主还通过这种方式获得市场信息而不是现金销售,这种方式常被营销费用紧缺的新网站采用。

联盟营销实际上是一种广告渠道和信息传播渠道。它主要有三个要素:

商家即广告主(Merchant),他通过联盟网络来进行广告投放或者分销。广告主按照网络广告的实际效果(如销售额、引导数、点击率等)向联盟会员支付合理的广告费用(通常为一个固定比率),从而节约营销开支,提高营销质量,扩大营销效果。

联盟会员(Affiliate),即提供广告渠道或者分销渠道的会员,主要是一些联盟网站,也有电子邮件的形式。 联盟会员通过网络联盟营销管理平台选择合适的广告主并通过播放广告为商家带来收益、节约大量的网络广告销售费用,轻松地把本网站访问量变成广告主的收益。

联盟网络营销管理系统(Affiliate Management Software),一个专为广告主、联盟会员提供的独立、公开、公正、透明的管理运行平台,在这个平台上,广告主可以跟踪记录每一个联盟会员所产生的点击数(Clicks)、印象数(Impressions)、引导数(Leads)和成交次数或成交额(Sales)等,然后根据联盟协议上规定的支付方式给予联盟会员费用。联盟会员可以通过此平台获得广告主的商品销售、会员注册等信息;联盟营销管理系统还具有值得信赖的第三方监控用户访问跟踪能力、实时报告系统、佣金结算、营销等方面的功能。另外,有些联盟营销服务提供商还提供网络营销的咨询、策划、创意、广告投放、效果监测等广泛的增值服务。

图一:联盟网络营销模式图

联盟营销的形式

联盟营销是一种Pay For Performance(即按效果付费)的营销方式,根据商家网站向联盟会员支付回报的方式,联盟网络营销可以分为三种形式:

1.按点击数付费(Cost-Per-Click, CPC)。联盟会员按照送到商家即广告主网站上游客的量(通常是点击数)来收取一定的费用。联属网络营销管理系统可以记录下每个客人在联盟会员网站上点击的广告主广告(包括文字、图片或者Email链接),并链接到广告主网站的次数,商家(Merchant)按每个点击多少钱的方式支付给联盟会员广告费。

2.按引导数付费(Cost-Per-Lead,CPL;也叫CPA,Cost-Per-Acquisition)。联盟会员根据提供给广告主有效访问者信息的记录数量来收取费用。此方式在CPC的基础上发展起来,由于某些访问者通过联盟会员网站的广告链接进入广告主网站后并没有发生任何有效的行为,例如没有提供任何有效信息,更谈不上发生购买行为。对于广告主来说,这样的访问是无效的,付出的费用并没有产生实际的效果。为实现最大化投资效益,只有在客户填写并提交了某个表单,并且在联盟管理系统对有效客户信息产生了一个给这个联属会员对应的引导(Lead)记录后,商家才向会员按照引导记录数付费。

3.按销售额付费(Cost-Per-Sale,CPS)。这种付费模式要求最高,每个会员根据他为商家带来的实际销售向广告主收取费用,一般按照一个百分比或固定的佣金比例收取(如销售额的10%到50%不等)。商家不会轻易的向联盟会员付费,只有在联盟会员介绍的客人在商家网站上产生了实际购买行为后(大多数是在线支付)才给联盟会员付费

上面三种方式都属于Pay For Performance(按效果付费)的营销方式,无论对于商家还是联属会员都是比较容易接受的。由于网站的自动化流程越来越完善,在线支付系统也越来越成熟,越来越多的联盟网络营销系统采用按销售额付费的方法。由于这种方法对广告主来说是一种零风险的广告投放方式,广告主也愿意设定比较高的佣金比例,这样就使得这种方式的营销管理系统越来越多地被采用。

联盟网络营销的优势

建设一个成熟的联盟网络营销系统不是一件容易的事,需要很多技术、资金和人力的投入。但是它何以具有如此强大的生命力,在国外产生短短几年的时间后就如此风靡呢?这和联盟营销给广告主和联盟会员带来的收益息息相关,这些受益包括:

1. 低营销成本保障广告效果。

联盟营销是按效果付费,因此与不能够保障效果的购买广告位不同, 可以有效的控制广告费,实现广告费用与广告效果挂钩。 广告主通过在具有潜在目标顾客的联盟会员网站上投放广告,诱导用户访问广告主网站及购买商品。只有当购买行为或注册会员等实际效果发生时才支付费用,广告主以最小的营销费用得到最好的效果。 麦肯锡公司曾对联盟网络广告、电视广告以及杂志广告的成本进行了统计,对比统计结果发现,联盟网络营销所产生的平均客户成本是电视广告的1/3,是杂志广告的1/2。

2. 选择广泛。

无论对广告主或是联盟会员来说,在一个公共联盟营销管理系统平台上进行广告投放交易,都会扩大自己的选择余地。广告主可以根据联盟会员的网站排名、拥有的潜在受众选择适合自己广告的网站;而联盟会员也可根据自己网站的风格选择适合的网络广告。

3. 更广的网络覆盖面以及品牌强化。

如果广告主的网站在Google或百度等搜索结果中的排名较低,而联盟会员网站却可能在排名较高的位置中占据了一半,甚至排在前三位,那么,广告主无需特别对自身网站进行网站优化,或者Google排名等方面的建设就可直接凭借自己在联盟会员网站上的链接(Link)和旗帜广告(Banner)吸引目标市场的大部分潜在用户,这何尝不是一件何乐而不为的事情呢?

4. 集中精力进行产品开发和销售服务,提高工作效率。

由于这种广告投放形式完全将广告投放问题交给中间的联盟营销服务商来做,对于广告双方(联盟会员和广告主)来说,既可以基本解决网站访问量问题,又可从繁杂的营销问题中解脱出来,商家可以集中精力进行产品开发、客户服务等主营活动,从而大大提高了工作效率。

5. 可计算的结果,支持营销活动。

联盟网络营销“按效果付费”的广告支付方式比传统方式最大的一个进步是:客户的每一个点击行为和在线活动都可以被管理软件记录下来,从而可以让广告主了解广告费用的用途,使其支付的每一分钱都用在刀刃上;另外,强大的联盟营销管理平台具有跟踪记录、分析记录,并使用这些记录分析来为产品开发和营销策略提供科学决策依据的功能。

6. 准确、可靠的费用结算。

资费行为是建立在准确的数据记录基础上的,所有费用都是在联盟营销管理平台上统一结算,无需人工操作。传统的合作营销体系是广告主与多家合作单位进行一一结算的,这样就为广告主带来了很多不便之处。采用中间管理平台后,一方面,中间管理平台完全按照各个联盟会员网站给广告主带来的效果统一进行结算,广告主最后只需要确认总的营销效果是否与广告费用相一致,即可解决与多数联盟会员网站的结算问题,为广告主减少了不必要的工作,节省了大量时间;另一方面,准确、可靠的费用结算系统也为联盟会员提供了佣金保障。由中间服务商100%定期预付给联盟会员佣金的信用金保证制度可以确保佣金收入安全,保障了联盟会员的权利。联盟会员再也不需为佣金不能按期到帐而担心了。

7.  额外的增值服务。

提供中间联盟营销管理平台的服务商可以为广告双方提供许多额外的增值服务,包括:

有价值的市场营销报告:广告主开展营销活动时,中间服务商可以根据公共联盟营销管理平台上的统计数字为广告主提供业绩报告。报告内容可以包括根据广告条件发生的购买数、购买额、代理费等内容,还可以包括按不同时间段、不同网站、以及购买详细信息等内容来评价客户网上行为的信息,以及其它广告主管理联盟网站所需要的有效资料

其他营销活动支持服务:中间服务商还可以为网站促销活动提供策划及运作、E-MAIL营销支持、与联盟网站进行交流及宣传活动等支持服务,提高广告主的营销活动效果。

 1997年前后,互联网上出现一家创意企业,叫做LinkExcgange。当年由于网络高速发展带来大量的个人网页,人们随便找个大型网站注册用户名就可以放上自己的网页,然而网页做完了却没有宣传的管道。

  LinkExchange提供了这些个人网页或网站的站长们一个宣传的管道。站长们自己设计横幅广告(Banner Ads)图片上传到LinkExchange,然后获取一组程式码加在自己的个人网页上。

  这个程式码会随著网页被访客读取时,显示其他个人网页的广告图片。你的网页每帮别人显示三次广告,你的自己的广告图片会在别人的网页上出现一次。这就是链接交换(Link Exchange )的精神。

  然而,上述的交换方式看起来怪怪的。我帮别人打广告三次,理论上别人也应该帮我打三次广告才会扯平,怎么会只能获得一次的机会?原来,不见了的广告机会,LinkExchange拿去卖给真正的广告主了。

  这间公司后来在1998年以美金 2.5亿卖给微软。前阵子有个朋友写信来,说有个前所未见的Idea可以创业。一瞧,发现「前所未见的Idea 」正是10年前LinkExchange干过的事,只是把个人网页换成Blog而已。

  ◎广告联盟替Blogger 带来收入

  在LinkExchange的模式下,个人网页(或者个人网站,或者Blog)的经营者(站长,或者Blogger )是无法从这样的交换行为中获利的。相较之下,广告联盟的商业模式就比较直接。

  经营者向广告联盟申请加入,在自己网页或Blog上放程式码,当页面被显示时就带出广告。早年依照广告被显示次数(CPM )经营者可以收到广告分成,目前绝大部分则是依广告被点次数(CPC )来分成。

  说到广告联盟经营者,最重量级的要算Google Adsense了。对于希望透过写Blog还能有点收入的人来说,还有微软AD Center 及Yahoo!的 Publisher Network 可期待。但目前都还未正式开放或仅限美国地区。

  然而,随著个人Blogger 越来越多,这样的市场也越来越具有想像空间。在美国地区随便一搜,就可以找到许多广告联盟的经营者。其中不乏10年前就已经存在的老网络公司,也有新兴的参与者。

  从广告的呈现方式而言,一般来说可分为图片广告以及文字广告。而自Google出现之后,文字广告越来越成为主流。由于技术上能做到广告内容与网页内容相关,广告的点击率也比传统图片广告高很多。

  ◎内文式广告的出现

  然而,这些广告方式大部分都是选在网页的某个位置上呈现。新兴的广告呈现方式则是直接在网页的文字上加入广告链接。比如说,某篇文章谈到数码相机,那么数码相机这四个字就会自动被加入链接。

  这种广告称为「内文式广告」(In-Text Advertising )。当Mouse 移到这些关键字上,不必点击就会拉下一个小画面的广告。有的会出现文字广告,有的会直接播放一段影片,此称为焦点广告曝光。

  广告计价方式很特殊,每当广告曝光时,不管读者有没有点击,广告主就须付费,而加入此种广告联盟的网站主或Blogger 也能分成。或许是因为新鲜,广告曝光率意外的高。(有趣的是,点击率一般。)

  目前美国专事内文式广告较知名的业者例如Vibrant Media ,其他比较老牌的业者例如ValueClick以及新兴业者也都酝酿推出,而在台湾目前则有DotMore 广告,在中国大陆则有Vogate.com。

  由于内文式广告是夹在文字上,因此若文章没提到「数码相机」,跟数码相机有关的广告就不会出现。这对Blogger 来说会变成不固定收入,而如果要让广告出现多些,写作方式可能要调整,是有点别扭。

  ◎以佣金为基础的广告联盟

  除了「依广告显示次数分成」「依广告被点次数分成」以外,以佣金为基础的分成方式也有。换言之广告被播放或被点击Blogger 都拿不到钱,只有因此让广告主成功售出商品,才能分到钱。

  当然这难度很高,因此能分到的钱也比其他广告方式要高很多。一般而言要看广告主的行业,有的行业可以给到销售额的 60%,有的只有 15%,有的只要点击广告过去的人成功注册会员就给钱(称为Lead)。

  此种称为Affiliate Program 或者Commision Based 的广告方式,对广告主来说吸引力非常大,因为只有商品销售出去才分钱给Blogger ,而这些广告主本来就有编列销售佣金的预算了,花这些钱很舍得。

  目前美国此类广告联盟中,Commission Junction 是运作较成熟的。 Blogger 加入以后,可以自由从成千上百个广告主中挑选,看要帮谁打广告。广告呈现方式也很多元,从图片到文字广告都有,自己挑。

  这种广告联盟形成热闹的交易市集。各式商品等你挑,你会有各种策略,例如锁定销售利润或者锁定销售量等。广告主也尽力释出各种条件讨好Blogger ,例如比同业更高的佣金。总之,是个热闹的市集。

  ◎文字使用人口决定市场形态

  本文提到的业者都在美国,他们基本上不接受英文以外的网站,个人网页或Blog。除了因为广告主希望锁定英语系读者外,也显示出另外一种市场风貌:大陆型国家才可能出现广告交易市集。

  广告联盟是运用大量个人来吸引广告主购买广告的生意,而基于预算或品牌考量,刊登此类广告的是以中小型企业为主。当两者数量众多时,广告联盟就可能抽取单笔金额较低但交易数量庞大的佣金而存活。

  在美国或中国大陆,广告联盟的生意蓬勃发展即根基于上述情况。而岛屿型经济体例如台湾,由于腹地较小使用繁体中文人口较少,广告联盟的发展会倾向从大型广告主产生营收。

  换言之,大陆型的广告联盟市场会出现众多比较偏向 C2C模式的业者彼此竞争,而岛屿型的广告联盟市场则会产生为数不多的业者,以争取大型广告主的预算为利润来源。

  使用哪种文字的人口数量,基本上决定了市场型态,当然也决定了一个地区的Blogger 有多少人能只靠广告就赚钱。现在看起来,要辞掉工作专心写Blog赚钱养活自己,只有在大陆型市场上少数人能做到。

根据2006年6月1日eNet硅谷动力报道,博客网董事长兼CEO方兴东敲开了一枚象征着博客营销的巨型的“茧”,以此来宣布博客网已“破茧成蝶”,正式引入基于“体验经济”的交互式博客营销。与此同时,方兴东还透露,这一新的营销模式,已经为博客网吸引到了来自香熏品牌“阿芙”一笔总价值100万元的广告投放。

易观分析:

博客作为一种新的网络服务应用,目前得主要盈利模式是:网络广告、移动增值和会员服务。

网络广告是最常见的互联网媒体盈利模式,网络广告主要分为品牌型网络广告和直销型网络广告,前者主要是扩大企业的品牌影响力,后者主要是销售某个具体产品。博客网络广告所起作用主要是后者,即直销型网络广告。博客作为Web2.0的一种典型应用,与生俱来就是来满足长尾理论中80%的分散需求,因此博客网络广告更具有针对性,其直销的作用更加明显。

易观观点:

博客网利用博客进行网络营销,已经实现一定的突破,吸引了来自香熏品牌“阿芙”广告投放。在此,我们不讨论广告的投放额度的情况,我们关注的是广告投放的效果。从广告投放效果的角度来看,我们建议广告主在投放网络广告时,要把握各种网络媒体的广告作用,结合自己的投放目的,最终实现理想的广告投放效果。博客作为网络广告,其优势主要为直销,即定向性的广告。因此,广告主在博客投放广告时,其目的更多的是直销,而不是品牌广告。

今天看到BLOG里的GGAD显示了JOHNCHOW的AD就点了进去!

JOHNCHOW列出了自己的BLOG最近几个月通过BLOG赚的钱,5个月从$300+到$3,000+增长10倍!厉害啊!

不仅有几个月增长的图,还有收入的分类

下面是图

Total Blog Income For January 2007: $3,440.66

incomegraph.gif

收入来源结构

  • Direct Ad Sales: $750.00
  • Text Links Ads: $621.68
  • Affiliate Sales: $545.00
  • Google AdSense: $536.58
  • Vibrant IntelliTXT: $478.18
  • TTZ Media: $183.54
  • FeedBurner Ads: $175.68
  • ReviewMe: $150.00
  • Grand Total: $3,440.66
  • 原文  中文
  • 2006年09月07日

    Google 的秘密- PageRank 彻底解说 中文版

    原著:Google の秘密 – PageRank 徹底解説 Hajime BABA / 馬場 肇   
    翻译:Kreny / 袁 黄琳 <krenyATdalouis.com>
    创作于:2003/12   最后更新: 2004年10月28日 3:53  关键词:pagerank, google, link
    翻译说明: 一些语句的翻译上使用了意译,使得尽可能得符合中文的理解和说明思路。
    版权声明:可以任意转载,转载时请务必以超链接形式标明文章原始出处和作者信息及本声明
    http://www.kreny.com/pagerank_cn.htm

    返回首页


    本文对作为评价甚高的搜索引擎 Google 的核心技术之一 PageRank (网页等级)的基本的概念和评价原理进行解释。

    索引

    1. 前言
    2. PageRank 的基本概念
    3. 怎样求得 PageRank
    4. 实际应用时的问题
    5. Namazu 上的实际安装实验
    6. 对 PageRank 的个人见解
    7. 参考文献
    8. 附录:「guguru?/gouguru?

    ★(2003/7/1) 拙著『Namazu系统的构筑和活用』已作修订。 详情请看 介绍页面

    ★(2003/5/20) 与 Google 有关的在线新闻报道一览(日语)已被分离到 另一张页面(googlenews.html)

    ★(2001/2/28) Namazu 的索引中使用的计算 PageRank 的 Perl 脚本 prnmz-1.0.tar.gz 公开下载。

    1.前言

    最近,搜索引擎 Google (http://www.google.com/)非常引人注目。Google 是基于现担任 CEO 的 Larry Page 和担任总经理的 Sergey Brin (2001年2月)在就读于美斯坦福大学研究生院时所开发的搜索引擎的一种检索服务。Google 从1998年9月开始服务,但 Netscape Communications 在 Google 的测试阶段就开始与其合作,美国 Yahoo! 公司也从2000年6月起将默认搜索引擎(美国 Yahoo! 不能检索时作为增补的搜索引擎)由原先合作的 Inktomi 转换为了 Google。日语版 Google 在2000年9月正式登场,现已被 BIGLOBE(NEC)所采用。 (注:2001年4月 Yahoo! JAPAN 和 @NIFTY,7月索尼,2002年1月 Excite 也相继与 Google 建立了协作关系)。

    Google 被评价的优点不仅仅在于去除无用的(广告)标语构成单一页面的功能、独自的 Cache 系统、动态制成摘要信息、为实现高速检索而设置的分散系统(数千台规模的Linux群集器)等,而其中最大的优点正是它检索结果的正确性。一种能够自动判断网页重要性的技术「PageRank是(网页等级)」就是为此而设计的一种技术。 本文的目的就是以尽可能浅显易懂的语言来说明 PageRank 系统的概要和原理。

    以下是 PageRank 的一篇基础文章。

    Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, ‘The PageRank Citation Ranking: Bringing Order to the Web’, 1998,
    http://www-db.stanford.edu/~backrub/pageranksub.ps

    为了更高效地计算 PageRank,以下是改良以后的一篇论文。

    Taher H. Haveliwala, ‘Efficient Computation of PageRank’, Stanford Technical Report, 1999,
    http://dbpubs.stanford.edu:8090/pub/1999-31

    另外,以下是 PageRank 的演示用资料(PowerPoint)。

    Larry Page, ‘PageRank: Bringing Order to the Web’,
    http://hci.stanford.edu/~page/papers/pagerank/ (已失效)

    接下来就对这两篇文章(另加一篇资料)进行基本说明。 首先,用简单的例子来解说 PageRank 的概念,再归结到使用超链接关系的排序系统来解决大规模疏松疏矩阵的特性值的问题。然后我们会接触一些在现实世界中应用基本模型时出现的问题和对应方法。接下来,为了探讨是否能够作为「个人化 PageRank」使用,进行对免费全文检索系统 Namazu 的安装实验并对其结果进行阐述。最后发表我对 PageRank 的个人见解。

    另外,为了能够理解以下的说明内容,需要大学基础课程程度的数学知识(尤其是线形代数)。然而为使文科生也能够顺利读下去,尽可能地不用算式来说明问题,同时,为了加入笔者个人的见解,没有加入像原文那么多的算法和数字,也存在许多不够严密和欠正确的地方,事先在次声明。具体内容请参照原文。

    PageRank(TM) 是美国 Google 公司的登记注册商标。

    2. PageRank 的基本概念

    PageRank 是基于「从许多优质的网页链接过来的网页,必定还是优质网页」的回归关系,来判定所有网页的重要性。

    在以下冗长的说明中,许多部分大量地使用了专业用语,会造成理解上的困难。这一章虽然准备集中于定性而简单的解说,但是,即使如此也会有怎么也不明白的时候,此时只要能够理解「从许多优质的网页链接过来的网页,必定还是优质网页」这一思考方法也就非常得可贵了。因为在所有几个要点中,这个是最重要的思考方法。

    来自于 Google 自己的介绍「Google的受欢迎的秘密(http://www.google.co.jp/intl/ja/why_use.html)」 是象以下一样解说的。

    关于PageRank
        PageRank,有效地利用了 Web 所拥有的庞大链接构造的特性。 从网页A导向网页B的链接被看作是对页面A对页面B的支持投票,Google根据这个投票数来判断页面的重要性。可是 Google 不单单只看投票数(即链接数),对投票的页面也进行分析。「重要性」高的页面所投的票的评价会更高,因为接受这个投票页面会被理解为「重要的物品」。
        根据这样的分析,得到了高评价的重要页面会被给予较高的 Page Rank(网页等级),在检索结果内的名次也会提高。PageRank 是 Google 中表示网页重要性的综合性指标,而且不会受到各种检索(引擎)的影响。倒不如说,PageRank 就是基于对"使用复杂的算法而得到的链接构造"的分析,从而得出的各网页本身的特性。
        当然,重要性高的页面如果和检索词句没有关联同样也没有任何意义。为此 Google 使用了精练后的文本匹配技术,使得能够检索出重要而且正确的页面。

    通过下面的图我们来具体地看一下刚才所阐述的算法。具体的算法是,将某个页面的 PageRank 除以存在于这个页面的正向链接,由此得到的值分别和正向链接所指向的页面的 PageRank 相加,即得到了被链接的页面的 PageRank。

    PageRank 的概念图
    PageRank 概念图。(引自 Page et al.(1998) Figure 2 ‘Simplified Page Calculation’)

    让我们详细地看一下。提高 PageRank 的要点,大致有3个。

    • 反向链接数 (单纯的意义上的受欢迎度指标)
    • 反向链接是否来自推荐度高的页面 (有根据的受欢迎指标)
    • 反向链接源页面的链接数 (被选中的几率指标)

    首先最基本的是,被许多页面链接会使得推荐度提高。也就是说「(被许多页面链接的)受欢迎的页面,必定是优质的页面」。所以以反向链接数作为受欢迎度的一个指标是很自然的想法。这是因为,“链接”是一种被看作「可以看看这个页面/这个页会有用」的推荐行为。但是,值得骄傲的是 PageRank 的思考方法并没有停留在这个地方。

    也就是说,不仅仅是通过反向链接数的多少,还给推荐度较高页面的反向链接以较高的评价。同时,对来自总链接数少页面的链接给予较高的评价,而来自总链接数多的页面的链接给予较低的评价。 换句话说「(汇集着许多推荐的)好的页面所推荐的页面,必定也是同样好的页面」和「与感觉在被胡乱链接的链接相比,被少数挑选出的链接肯定是优质的链接」这两种判断同时进行着。一方面,来自他人高水平网页的正规链接将会被明确重视,另一方面,来自张贴有完全没有关联性的类似于书签的网页的链接会作为「几乎没有什么价值(虽然比起不被链接来说好一些)」而被轻视。

    因此,如果从类似于 Yahoo! 那样的 PageRank 非常高的站点被链接的话,仅此网页的 PageRank 也会一下子上升;相反地,无论有多少反向链接数,如果全都是从那些没有多大意义的页面链接过来的话,PageRank 也不会轻易上升。不仅是 Yahoo!, 在某个领域中可以被称为是有权威的(或者说固定的)页面来的反向链接是非常有益的。但是,只是一个劲地在自己一些同伴之间制作的链接,比如像「单纯的内部照顾」这样的做法很难看出有什么价值。也就是说,从注目于全世界所有网页的视点来判断(你的网页)是否真正具有价值。

    综合性地分析这些指标,最终形成了将评价较高的页面显示在检索结果的相对靠前处的搜索结构。

    以往的做法只是单纯地使用反向链接数来评价页面的重要性,但 PageRank 所采用方式的优点是能够不受机械生成的链接的影响。 也就是说,为了提高 PageRank 需要有优质页面的反向链接。 譬如如果委托 Yahoo! 登陆自己的网站,就会使得 PageRank 骤然上升。但是为此必须致力于制作(网页的)充实的内容。这样一来,就使得基本上没有提高 PageRank 的近路(或后门)。不只限于PageRank (Clever 和 HITS 等也同样),在利用链接构造的排序系统中,以前单纯的 SPAM 手法将不再通用。这是最大的一个优点,也是 Google 方便于使用的最大理由。(虽然是最大的理由,但并不是唯一的理由。)

    在这里请注意,PageRank 自身是由 Google 定量,而与用户检索内容的表达式完全无关。就像后边即将阐述的一样,检索语句不会呈现在 PageRank 自己的计算式上。不管得到多少的检索语句,PageRank 也是一定的、文件固有的评分量。

    PageRank 的定性说明大致就是这样一些。但是,为了实际计算排列次序、比较等级,需要更定量性的讨论。以下一章将做详细的说明。

    3.怎样求得 PageRank

    我们感兴趣的是,在有像超级链接构造那样的互相参照关系的时候,定量地知道哪一个页面是最「重要」的。换句话大胆地说,这个也就是严密计算「应该从哪一页开始读取」这个指标的过程。就算从谁都不看的小页面开始读取也没有办法。

    那么,一般地说为了使得像 Web 那样的超级链接构造能够反映在在排列次序上,需要在计算机上建立超级链接构造的数字模型。 怎么模型化需要取决于安装者的方针所以一概而论,但是如果应用图表理论来观察超级链接构造的话,最终常常回到线形代数考虑方法上去。这对于 PageRank 也是一样的。

    计算方法的原理

    作为最基本的考虑方法,就是用行列阵的形式来表达链接关系。从页面 i 链接到另一张页面 j 的时,将其成分定义为1,反之则定义为 0 。即,行列阵 A 的成分 aij 可以用,

      aij=1 if  (从页面 i 向页面 j 「 有 」 链接的情况)
          0 if  (从页面 i 向页面 j 「没有」链接的情况) 

    来表示。文件数用 N 来表示的话,这个行列阵就成为 N×N 的方阵。这个相当于在图表理论中的「邻接行列」。也就是说,Web 的链接关系可以看做是采用了邻接关系有向图表 S。总而言之,只要建立了链接,就应该有邻接关系。

    (*注)由点和点连接的线构成的图形被称为「图表(graph)」。这些点被称为「顶点(vertex)」或者「节点(node)」;这些线被称为「边(edge)」或者「弧(arc)」。图表分为两类,“边”没有方向的图表被称为「无向图表(undirected graph)」,“边”带有方向的图表被称为「有向图表(directed graph)」。把有向图表想像成单向通行的道路就可以了。 图表能用各种的方法来表示,但一般用在数据结构上的是「邻接行列(adjacency matrix)」和「邻接列表(adjacency list)」。需要注意的是,如果是无向图表,邻接行列 A 就成为了对称行列,而如果是有向图表,A 就会成为不对称行列。

    以下是用位图表示的 Apache 的在线手册(共128页)的邻接行列。当黑点呈横向排列时,表示这个页面有很多正向链接(即向外导出的链接);反之,当黑店呈纵向排列时,表示这个页面有很多反向链接

    邻接行列的例子
    邻接行列的例子(采用了Apache 的在线手册)

    PageRank 的行列阵是把这个邻接行列倒置后(行和列互换),为了将各列(column)矢量的总和变成 1 (全概率), 把各个列矢量除以各自的链接数(非零要素数)。这样作成的行列被称为「推移概率行列」,含有 N 个概率变量,各个行矢量表示状态之间的推移概率。倒置的理由是,PageRank 并非重视「链接到多少地方」而是重视「被多少地方链接」。

    PageRank 的计算,就是求属于这个推移概率行列最大特性值的固有矢量(优固有矢量)。

    这是因为,当线性变换系 t→∞ 渐近时,我们能够根据变换行列的"绝对价值最大的特性值"和"属于它的固有矢量"将其从根本上记述下来。换句话说,用推移概率行列表示的概率过程,是反复对这个行列进行乘法运算的一个过程,并且能够计算出前方状态的概率。

    再者,虽然听起来很难,但是求特性值和固有矢量的值是能够严密分析的一种基础的数学手段。我们能够自由地给矢量的初始值赋值,但是因为不断地将行列相乘,得到的矢量却会集中在一些特定数值的组合中。我们把那些稳定的数值的组合称为固有矢量,把固有矢量中特征性的标量(scalar)称为特性值,把这样的计算方法总称为分解特性值,把解特性值的问题称为特性值问题

    (*注) 对 N 次的正方行列 A 把满足 Ax =λx 的数 λ 称为 A 的特性值,称 x 为属于 λ 的固有矢量。如果你怎么也不能适应行列的概念的话,你也可以考虑 N×N 的二元排列就可以了。同时,也可以把矢量考虑成为长度为 N 的普通的(一元)排列就可以了。

    简单的例子

    让我们用简单的例子来试着逐次计算 PageRank 。首先考虑一下有像下图表示那样的链接关系的7个HTML文件。并且,这些HTML文件间的链接关系只是闭合于这1-7的文件中。也就是说,除了这些文档以外没有其他任何链接的出入。另外请注意,所有的页面都有正向和反向链接(即没有终点),这也是后面将提出的一个重要假定,在此暂且不深入探讨。

    链接关系的推移图
    表示页面间互相链接关系的推移图

    首先,把这张推移图图表构造的邻接列表表示为排列式,就有以下式子。即,根据各个链接源ID列举链接目标的ID。

    链接源I D 	链接目标 ID
    1		2,3 ,4,5, 7
    2		1
    3		1,2
    4		2,3,5
    5 		1,3,4,6
    6		1,5
    7		5

    以这个邻接列表中所表示的链接关系的邻接行列 A 是以下这样的 7×7 的正方行列。一个仅有要素 0 和 1 位图行列(bitmap matrix)。横向查看第 i 行表示从文件 i 正向链接的文件ID。

    A = [
    	 0, 1, 1, 1, 1, 0, 1;
    	 1, 0, 0, 0, 0, 0, 0;
    	 1, 1, 0, 0, 0, 0, 0;
    	 0, 1, 1, 0, 1, 0, 0;
    	 1, 0, 1, 1, 0, 1, 0;
    	 1, 0, 0, 0, 1, 0, 0;
    	 0, 0, 0, 0, 1, 0, 0;
     ]

    PageRank 式的推移概率行列 M ,是将 A 倒置后将各个数值除以各自的非零要素后得到的。即以下这个 7×7 的正方行列。横向查看第 i 行非零要素表示有指向文件 i 链接的文件ID(文件 i 的反向链接源)。请注意,各纵列的值相加的和为 1(全概率)。

    M = [
    	0, 	1,	1/2,	0,	1/4,	1/2,	0;
    	1/5,	0,	1/2,	1/3,	0,	0,	0;
    	1/5,	0,	0,	1/3,	1/4,	0,	0;
    	1/5,	0,	0,	0,	1/4,	0,	0;
    	1/5,	0,	0,	1/3,	0,	1/2,	1;
    	0,	0,	0,	0,	1/4,	0,	0;
    	1/5,	0,	0,	0,	0,	0,	0;
    ]

    表示 PageRank 的矢量 R (各个的页面的等级数的队列),存在着 R = cMR 的关系(c 为定量)。在这种情况下,R 相当于线形代数中的固有矢量,c 相当于对应特性值的倒数。为了求得 R ,只要对这个正方行列 M 作特性值分解就可以了。

    在分解特性值时有相应的各种各样的数值分析法,但是本文将不在这里对各种方法详细说明,请读者自己去阅读一本恰当的教科书(在你的暑假里一定有这么一本被埋没的教科书)。在此,我们就暂且使用决 GNU Octave 这个计算程序实际计算一下特性值和固有矢量。

    (*注) GNU Octave ,是支持数值计算,类似于描述性出色的 MATLAB 的编程语言。扩展后的处理语言更适合于行列演算,但基本上和C语言的语风相像,因此可读性很高。详细请参照 http://www.octave.org/。 当然,除了Octave以外 MATLABScilab 也是非常不错的语言,但是根据 GPL, Octave 是最容易得到的。

    实际举例

    下面我们举一个实际例子。如果不太明白以下例子在做什么的话,只要认为我们能够使用 Octave 这个程序来解特性值问题即可。

    首先,使用恰当的编辑器制作以下 Octave 脚本。(在行尾加上分号就能消去多余的结果输出,不过,此次为了说明特意去掉了。)

    % cat pagerank.m
    #!/usr/bin/octave
    ## pagerank.m - 计算 PageRank(TM) 用的简单的 GNU Octave 脚本
    
    ##设置计时器。
    tic(); 
    
    ## 根据PageRank 的定义,将从文件 i 链接到文件 j 的链接状态的推移概率行列定义为 M(i,j)
    
    M = [
    	0,	1,	1/2,	0,	1/4,	1/2 ,	0;
    	1/5,	0,	1/2,	1/3,	0,	0,	0;
    	1/5,	0,	0,	1/3,	1/4,	0,	0;
    	1/5,	0,	0,	0,	1/4,	0,	0;
    	1/5,	0,	0,	1/3,	0,	1/2,	1;
    	0,	0,	0,	0,	1/4,	0,	0;
    	1/5,	0,	0,	0,	0,	0,	0;
    ]
    ##计算 全部 M 的特性值和固有矢量列的组合。
    
    [V,D]= eig(M)
    
    ## 保存与绝对价值最大的特性值对应的固有矢量到EigenVector。
    
     EigenVector = V(:, find(abs(diag(D))==max(abs(diag(D))))) 
    
    ## PageRank 是将 EigenVector 在概率矢量上标准化后得到的值。
     PageRank = EigenVector./ norm(EigenVector,1) 
    
    ## 输出计算时间。
    elapsed_time = toc()
    

    (2003/7/23: 修正上述脚本的错误。)

    误: EigenVector = V(:, find(max(abs(diag(D))))  )
    正: EigenVector = V(:, find(abs(diag(D))== max(abs(diag(D))))) 

    用 Octave 运行这个 pagerank.m 脚本后在标准输出中得到以下结果。

    % octave pagerank.m
    GNU Octave, version 2.0.16 (i586-redhat-linux-gnu).
    Copyright (C) 1996, 1997, 1998, 1999, 2000 John W. Eaton.
    This is free software with ABSOLUTELY NO WARRANTY.
    For details, type `warranty'. 
    
    M =
    
    0.00000 1.00000 0.50000 0.00000 0.25000 0.50000 0.00000
    0.20000 0.00000 0.50000 0.33333 0.00000 0.00000 0.00000
    0.20000 0.00000 0.00000 0.33333 0.25000 0.00000 0.00000
    0.20000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000
    0.20000 0.00000 0.00000 0.33333 0.00000 0.50000 1.00000
    0.00000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000
    0.20000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 
    
    V =
    
    Columns 1 through 3: 
    
    0.69946 + 0.00000i 0.63140 + 0.00000i 0.63140 + 0.00000i
    0.38286 + 0.00000i -0.28715 + 0.15402i -0.28715 - 0.15402i
    0.32396 + 0.00000i -0.07422 - 0.10512i -0.07422 + 0.10512i
    0.24297 + 0.00000i 0.00707 - 0.24933i 0.00707 + 0.24933i
    0.41231 + 0.00000i -0.28417 + 0.44976i -0.28417 - 0.44976i
    0.10308 + 0.00000i 0.22951 - 0.13211i 0.22951+ 0.13211i
    0.13989 + 0.00000i -0.22243 - 0.11722i -0.22243 + 0.11722i 
    
    Columns 4 through 6: 
    
    0.56600 + 0.00000i 0.56600 + 0.00000i -0.32958 + 0.00000i
    0.26420 - 0.05040i 0.26420 + 0.05040i 0.14584 + 0.00000i
    -0.10267 + 0.14787i -0.10267- 0.14787i 0.24608 + 0.00000i
    -0.11643 + 0.02319i -0.11643 - 0.02319i -0.24398+ 0.00000i
    -0.49468 - 0.14385i -0.49468 + 0.14385i 0.42562 + 0.00000i
    -0.14749+ 0.38066i -0.14749 - 0.38066i -0.64118 + 0.00000i
    0.03106 - 0.35747i 0.03106+ 0.35747i 0.39720 + 0.00000i 
    
    Column 7: 
    
    0.00000 + 0.00000i
    -0.40825 + 0.00000i
    -0.00000 + 0.00000i
    0.00000 + 0.00000i
    -0.00000 + 0.00000i
    0.81650 + 0.00000i
    -0.40825 + 0.00000i 
    
    D = 
    
    Columns 1 through 3: 
    
    1.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
    0.00000 + 0.00000i -0.44433 + 0.23415i 0.00000 + 0.00000i
    0.00000 + 0.00000i 0.00000 + 0.00000i -0.44433 - 0.23415i
    0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
    0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
    0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
    0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 
    
    Columns 4 through 6: 
    
    0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
    0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
    0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
    0.02731 + 0.31430i 0.00000 + 0.00000i 0.00000 + 0.00000i
    0.00000 + 0.00000i 0.02731 - 0.31430i 0.00000 + 0.00000i
    0.00000 + 0.00000i 0.00000 + 0.00000i -0.16595 + 0.00000i
    0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 
    
    Column 7: 
    
    0.00000 + 0.00000i
    0.00000 + 0.00000i
    0.00000 + 0.00000i
    0.00000 + 0.00000i
    0.00000 + 0.00000i
    0.00000 + 0.00000i
    -0.00000 + 0.00000i 
    
    EigenVector =
    0.69946
    0.38286
    0.32396
    0.24297
    0.41231
    0.10308
    0.13989 
    
    PageRank =
    0.303514
    0.166134
    0.140575
    0.105431
    0.178914
    0.044728
    0.060703 
    
    elapsed_time = 0.063995
    

    Octave 的输出中,特性值被表示为对角行列 D 的对角成分,各个特性值相对应的固有矢量被表示为行列 V 对应列的列矢量。也就是说 M * V = D * M 成立。 如果包含复数特性值的话这里的特性值有7个,其中绝对价值最大的特性值 λ 是λ=1。与之相对应的固有矢量为实矢量:

    EigenVector =
    	0.69946
    	0.38286
    	0.32396
    	0.24297
    	0.41231
    	0.10308
    	0.13989

    即行列 V 的第1列。请注意,这个求得的固有矢量中概率矢量(要素的和等于1的 N 次元非负矢量)没有被标准化,只是矢量的「大小」等于 1。 用算式来表达就是,Σpi ≠1 ,Σ(pi)2=1。 在这里,对概率矢量进行标准化

    PageRank =
    	0.303514
    	0.166134
    	0.140575
    	0.105431
    	0.178914
    	0.044728
    	0.060703

    PageRank 就是排位了。 注意,全部相加的和为 1。 计算只用了0.064秒。

    求得的 PageRank 的评价

    将 PageRank 的评价按顺序排列 (PageRank 小数点3位四舍五入)。

    名次 PageRank   文件ID    发出链接ID  被链接ID
      1     0.304     1       2,3,4,5,7   2,3,5,6
      2     0.179     5       1,3,4,6     1,4,6,7
      3     0.166     2       1           1,3,4
      4     0.141     3       1,2         1,4,5
      5     0.105     4       2,3,5       1,5
      6     0.061     7       5           1
      7     0.045     6       1,5         5
    

    首先应该关注的是,PageRank 的名次和反向链接的数目是基本一致的。无论链接多少正向链接都几乎不会影响 PageRank,相反地有多少反向链接却是从根本上决定 PageRank 的大小。但是,仅仅这些并不能说明第1位和第2位之间的显著差别(同样地、第3位和第4位,第6位和第7位之间的差别)。总之,绝妙之处在于 PageRank 并不只是通过反向链接数来决定的。

    让我们详细地看一下。ID=1 的文件的 PageRank 是0.304,占据全体的三分之一,成为了第1位。特别需要说明的是,起到相当大效果的是从排在第3位的 ID=2 页面中得到了所有的 PageRank(0.166)数。ID=2页面有从3个地方过来的反向链接,而只有面向 ID=1页面的一个链接,因此(面向ID=1页面的)链接就得到了所有的 PageRank 数。不过,就因为 ID=1页面是正向链接反向链接最多的页面,也可以理解它是最受欢迎的页面吧。

    反过来,最后一名的 ID=6 页面只有 ID=1 的15%的微弱评价,这可以理解为是因为没有来自 PageRank 很高的 ID=1 的链接而使其有很大地影响。 总之,即使有同样的反向链接的数目,链接源页面评价的高低也影响 PageRank 的高低。

    链接关系的推移图(PageRank)
    表示页面互相的链接关系的推移图(加入了PageRank)

    实际地试着计算一下PageRank的收支。因为λ=1所以计算很简单,只要将自各页的流入量单纯相加即可。譬如 ID=1 的流入量为,

    流入量=(ID=2发出的Rank)+(ID=3发出的Rank)+(ID=5发出的Rank)+(ID=6发出的Rank)
        = 0.166+0.141/2+0.179/4+0.045/2
        = 0.30375

    在误差范围内PageRank的收支相符合。其他页面ID的情况也一样。以上的 PageRank 推移图正表示了这个收支。沿着各自的链接发出的PageRank等于此页面原有的PageRank除以发出链接数的值,而且和各自的页面的PageRank收支相平衡。

    不过,这样绝妙均衡的本身,对理解线形代数的人来说当然不会是让人惊讶的事情。因为这正是「特性值和固有矢量的性质」,总之这样被选的数值的组就是固有矢量。但即使是这样,实际试着确认一下的话,已经能够很好地使用PageRank的方法来考虑了。

    以上就是 PageRank 的基本原理。 Google 做的就是大规模地处理这样的非常特性值问题。

    4.实际应用时的问题

    PageRank 的基本考虑方法并不是很难的东西。实用效果中的巨大成分并不是复杂离奇的算法,而是进行简单的线性变换,倒不如都属于简明直观的类别吧。但是,实际使用 Web 超级链接构造来计算 PageRank 的话,不是简单地能够用嘴巴来说明的东西。主要的困难主要有二个。一、由来于纯粹假设的数值模型和现实世界的不同;二,在实际数值计算上(专门技术的)困难。

    准备:数学用语(主要概率过程)的解说

    推移概率行列和概率过程上的马尔可夫过程存在很深的关系。本章先离开与 PageRank 本身的说明,预先说明几个呈现在概率过程上的数学用语。因为会设计相当难的部分,如果不能够理解也可以跳过这里。(也可能是我的说明方法不好) 同时,请注意这里几乎没有证明就直接使用了。详细的解说请阅读教科书。

    从有向图表S的状态 i 出发,将有限时间之后再次回复到状态 i 的概率作为 1 时,也就是说,当沿着(有向)图表的方向前进能够回到原来位置的路径存在的时候,i 就被成为「回归」。不能回归的状态被称为「非回归」。从状态 i 出发,当通过有限次数的推移达到状态 j 的概率非负的时候,我们就说「从状态 i 到达状态 j 是可能的」。当反方向也可能到达的时候,我们称「i 和 j 互相可能到达」。从状态 i 不能到达其他任何状态的时候,称 i 为「吸收状态」。

    从邻接行列 A 所决定的图表(graph)的任意顶点出发,指向其他任意的顶点图表的路径能够像箭头那样到达时被称为「强联结」( 也被称为「分解不能」)。强联结,等价于从任意状态到任意状态可以互相到达。邻接行列 A 的成分中有很多 0 时,强联结性就会有问题。注意,如果全部成分都为 aij ≠0 的话,则都属于强联结。因为,对应的 马尔可夫链的样本路径表示 S 的任意两点间以正的概率来往通行。

    我们可以把全体状态以等价类(或者回归类)来划分。在这里,回归类是指链接所围成的范围。属于一个等价类的状态可以互相到达。从一个类出发以正的概率进入到其他的类的可能性也是存在的。可是很明显,在这种情况下不可能回复到原来的类。不然的话,这两个类就归于等价类了。下图表示了,当 T 作为非回归性的等价类、R 作为回归性等价类时,虽然存在 马尔可夫链 既不来自回归类,也不来自非回归类的情况,但如果一旦来自前两者的话,就不再会回到非回归类中了。

    重归?非重归的图
    回归、非回归示意图(修改了小谷(1997)的图11.1)

    这个等价关系中只有一个回归类的时候,那个 马尔可夫链就被称为「最简」。换句话说,全部的状态之间互相可以到达时就被称为最简。最简时都是强联结。

    互相完全没有关联的邻接行列(或推移概率行列),乘以恰当的置换行列(掉换行和列)以后得到

    P = | P1 0 |
        | 0 P2 |

    这样的关系。这表示回归类 P1 和 P2 间完全不存在直接的链接关系。

    回归类、非回归类掺杂在一起的邻接行列(或推移概率行列),乘以恰当的置换行列后得到,

    P = | P1 0 |
        | Q P2 |

    这样的关系(Q≠0)。此时,P1是非回归类,P2是回归类。

    推移概率行列有时也被称作马尔可夫行列。称马尔可夫过程的试验行列的观测结果为马尔可夫链(Markov chain)。 当经过相当的时间后马尔可夫链会趋向某种平衡状态。对任意的状态 i, 如果 j 是非回归状态,则 Pij(n)→0。相反,当 i 为非回归、j 为回归时,停留在状态 i 上着的概率是0。如果 i,j 属于同样的非周期性回归类的话,Pij(n)→Pj≥0。

    定理:若 P 是有限马尔可夫行列的话,P 的特性值 1 的重复度等于 P 决定的回归类的数目。(证明太长,省略)。

    跟随着推移概率行列的有向图表的最大强联结成分(与之对应的状态的集合)被称为Ergodic部分(历遍部分),此外的强联结成分被称为消散部分。因为无论从怎样的初期状态概率 x(0)开始,经过时间 n 后 x(n) = P(n)x(0),所以属于消散部分的状态概率几乎接近于0。关于EllGoth部分,连同与各联结成分对应状态的类、像独立的最简的马尔可夫链一样行动,其中,各类中的状态概率(即从过去开始的平均值)的值和初期状态概率无关,换言之,是近似于与对应 P 的最简成分的固有矢量成比例的东西。在类之间概率的分配依存于初期状态的概率。

    离散时间型马尔可夫链的不变分布是属于极限分布,从那个分布开始已经不是在分布意义上的随时间的变化了。状态的概率分布在时间变化时也不会变化时被称为固定分布。PageRank 用马尔可夫过程来说就是,PageRank就是以一定时间内用户随机地沿着(网页)链接前进时对各个页面访问的固定分布

    假想模型和现实世界的不同

    那么,让我们将概率过程(即图表原理)的考虑方法和实际的网页链接构造合起来看一看。

    对于刚才举例的假想网页群来说,只要相互顺着链接前进则在彼此页面间必定有相互链接的关系。即,有向图表是强联结的行列既是回归又是最简。像上面举的很多的概率过程的教科书一样,许多证明都是把回归和最简作为前提来证明的,如果是最简的话,各种各样的性质就变得容易说了。

    但是现实的网页并不是强联结。也就是说邻接行列不是最简的。具体来说,顺着链接前进的话,有时会走到完全没有向外链接的网页。通常这样的情况,只有利用 web 浏览器的「返回」功能了。如果人们只是浏览而已的话,一切就到此结束了,然而 PageRank 的计算却不能到此结束。因为PageRank 一旦被引入以后是不能返回的。Pagerank 称这种页面为为「dangling page」。同样道理,只有向外的链接而没有反向链接的页面也是存在的。但 Pagerank 并不考虑这样的页面,因为没有流入的 PageRank 而只流出的 PageRank,从对称性来考虑的话必定是很奇怪的。

    同时,有时候也有链接只在一个集合内部旋转而不向外界链接的现象。这是非周期性的回归类多重存在时可能出现的问题。(请读者考虑一下陷入上图中一个 R 中而不能移动到别的 R 和 T 的情况)。 Pagerank 称之为「rank sink」。在现实中的页面,无论怎样顺着链接前进,仅仅顺着链接是绝对不能进入的页面群总归存在,也就是说,这些页面群是从互相没有关联的多数的同值类(回归类)形成的。

    总之,由现实的 Web 页组成的推移概率行列大部分都不是最简的。当不是最简时,最大特性值(即1)是重复的,并且不能避免优固有矢量多数存在的问题。换句话说,PageRank 并不是从一个意义上来决定的。

    在此,Pagerank 为了解决这样的问题,考虑了一种「用户虽然在许多场合都顺着当前页面中的链接前进,但时常会跳跃到完全无关的页面里」,这样的浏览模型。再者,将「时常」固定为 15% 来计算。用户在 85% 的情况下沿着链接前进,但在 15% 的情况下会突然跳跃到无关的页面中去。(注:Pagerank 的原始手法是各自87%(=1/1.15 )和13%(=0.15/1.15)。)

    将此用算式来表示的话得到以下公式。

    M’= c*M +(1-c)*[1/N]

    其中,[1/N]是所有要素为 1/N 的 N次正方行列,c =0.85(=1-0.15)。M’当然也同样是推移概率行列了。也就是说,根据 Pagerank 的变形,原先求行列 M 的特性值问题变成了求行列 M’的优固有矢量特性值问题。M 是固定无记忆信息源(i.i.d.)时,M’被称为「混合信息源」,这也就是固定但非ellGoth信息源的典型例子。

    如果从数学角度看,「把非最简的推移行列最简化」操作的另外一种说法就是「把不是强联结的图表变成强联结」的变换操作。所谓对全部的要素都考虑0.15的迁移概率,就是意味着将原本非最简的推移概率行列转换为最简并回归的(当然非负的情况也存在)推移概率行列。针对原本的推移概率行列,进行这样的变换操作的话,就能从一个意义上定义 PageRank、也就是说能保证最大特性值的重复度为1。如果考虑了这样的变换操作的话,因为推移概率行列的回归类的数目变成 1 的同时也最简化,根据前面的定理,优固有矢量(即 PageRank)就被从一个意义上定义了。

    数值计算上的问题点(其1)

    在此,只要大概明白 PageRank 的概念就可以了,不需要很深的陷入数值计算上的技术的问题中(其实,笔者自己即使有自信也说不清楚)。但是,因为特性值分析和联立一次方程式分析一样,是利用在各种的统计分析中重要的数值计算手法的一中,所以这里我们简单的触及一些分析方法。

    主记忆领域的问题是在数值计算上的问题之一。

    假设 N 是 104 的 order。通常,数值计算程序内部行列和矢量是用双精度记录的,N 次正方行列 A 的记忆领域为 sizeof(double)* N * N =8 *104 * 104=800MB。 800MB 的主记忆领域不是那种经常会拥有的东西, 虽然这么说也非那种不可能的数字。但是,N 如果变成 105 或106 的话,各自就变成80GB,8TB。这样的话不用说内存就连硬盘也已经很困难了。 Google 从处理着10亿以上的页面(2001年时)以来,就知道这种规矩的做法已经完全不适用了。

    不过,A 只是稀疏(sparse)行列。因为即使有一部分的页面拼命地进行链接,但是向整个Web展开链接的页面是没有的,即使有也是极为稀少的。平均一下,每一张页面有10-20个左右的链接(根据 IBM Almaden 研究所’Graph structure in the web‘ 的统计,平均在16.1个左右)。因此,我们可以采用恰当的压缩方法来压缩 A 。 N 即使是 106 时,如果平均链接数是10,最终的记忆领域只要 80MB,从规模上来说可以收纳到合理的数字里。

    稀疏行列的容纳方式当今已经被充分地研究(有限要素法的解法等),在恰当的数值计算的专业书中就可以学到。虽然这么说,因为相当地难解还是需要很复杂的手法。但想指出的是如果可以很好的解决的话,并列化的高速计算(也许)就变得可能了。因为比起怎样排列并容纳非零要素来说,计算性能和并列性能对其的影响会更大。

    数值计算上的问题点(其2)

    另一个是收敛问题。

    固定方程式

    xi=ΣAijxi

    是 N 元的联立一次方程式,一般地不能得到分析解,所以只能解其数值。刚才举的例子中为了求特性值和固有矢量,使用了 Octave 的 eig()函数, 不过,这个在问题小的时候不能适用。说起来,并不需要计算全部的特性值/固有矢量。

    求最大特性值和属于它的固有矢量(优固有矢量)的数值计算手法中,一般使用「幂乘法」(也叫反复法)。这是指,取适当初期矢量 x0 ,当 x(n+1) = A y(n) (其中 y(n) = x(n) / c(n) )中的 n →∞ 时,x 向拥有最大特性值的固有矢量收敛的同时 c 向此最大特性值收敛的利用线形代数性质的计算方法(证明请参照线形代数的教科书)。幂乘法(反复法)的特长与逐次反复计算的近似法比,能够改善解矢量的问题。它的优点是,因为只要反复对行列和矢量进行适当次数的乘法运算,所以只要通过程序就能够简单地解决,并且还可以进行由于受到内存和硬盘的限制通过直接法不能解决的大规模分析。这是许多的实用算法的出发点。

    在这里,请注意从线形代数的简单定理(Peron-Frobenius定理)得到推移概率行列的绝对价值的最大特性值是1。如果采用了这个,就会使得反复法的 PageRank 的计算变得更容易。即,因为最大特性值是既知的,比起求满足 Ax=x 的矢量 x来说 ,变成更加简单的问题了。这虽然是很细小的地方但是很重要。首先,可以去掉比较花费成本的除法计算 (y(n)=x(n)/c(n))不用完成。如果是反复法的话,不能得到很高的精确度,并且如果搞错了加速方法的话,计算出的不是是最大特性值而是第二大特性值和属于它的固有矢量(虽然这种情况很少,但是说不定就是从根本上错误的值)。但如果知道了最大特性值,就可以进行核对了。在 Pagerank 的第一篇论文中他们似乎没有注意到这个事情,但在 Haveliwala 的第二论文中增加了关于此的修正。

    反复的次数取决于想要求的精度。也就是说,想要求的精度越高,反复的次数就越多。可是,幂乘法(反复法)的误差的收敛比与系数行列的谱段特性(特性值的绝对值分布)有很强的依存关系。具体地说,绝对值最大的特性值用λ1表示,第二位用 λ2 表示,优越率(收敛率 probability of dominance)为 d =λ12 话,可以知道d离1越近收敛就变得越慢。在 N 很大的情况时d当然离1很近。这是因为,绝对值最大的特性值是1,而其他所有的 N-1 个特性值的绝对值都比1小。但是,N-1个特性值之间非常的拥挤,所以λ1和λ2 之间几乎没有差别。因此一般来说,收敛会变慢。

    所谓收敛变慢,严密地说,就是无论经过多少时间也完成不了的计算。对此,为了使收敛加快的适当的加速方法也是存在的,应用这些方法时,需要对数值计算技术有十二分的理解,因此如果不是数值计算的专家就很难引入。

    5. Namazu 上的实际安装实验

    为了使更简单地推测上文描述的问题,PageRank 并不是非世界所有的web页面而不能使用的考虑方法,即使是个人的利用方法也能实现。为了实现「Personalized PageRank」,针对在各种 UNIX 和 Windows 上运作的中小规模网站适用的全文检索系统 Namazu 进行了实际安装实验。(关于Namazu可参考 日语全文检索引擎软件列表。)

    由于实验能简单地控制内存的使用量,并将最大特性值用1来考虑,所以将 Have liwala(1999)的想法做为基本的考虑方法。但是对 dangling pages 的处理有少许不同。固有矢量的计算内核使用了数值计算脚本 GNU Octave。所以基本的代码编写自己只用了一天就解决了。另外,从用 mknmz 编写的索引不能直接计算 PageRank,而要事前准备表示邻接关系的索引(邻接列表)。这个也有可能被编入检索者(Indexer)的主要部分。

    以下表示了实际计算时间(单位:秒)。运行机器的配置为 PentiumII 400MHz x 2,内存512MB,Kondara MNU/Linux 1.2的(kernel-2.2 .17-15ksmp),Octave-2.0.16(一般状态分发物)。收敛精度(剩余差矢量的L1规范)取了到1.0e-10,也许有些过分精确了。

    文书数N     mknmz时间    准备时间   PageRank计算时间
    ============================================================
    128          58          2          6
    2,301       1, 575       46         214
    49,604      15,975       478        5,872

    因为没用一些巨大的web页群来做测试,所以实验只停留在小规模的基础上。虽然有这个难点,但从基本上可以了解与索引所花的时间相比,在很短的时间里就可以计算 PageRank 的倾向吧。

    因为 Namazu 自身中也有很多难题,所以并不寄予很大的奢望,但至少使用 105 程度(尽可能 106)规模的web页面群来实验。从趋势来看可以预想 N=106 的计算时间恐怕会发散开去,所以在 N=106 时,若是能够讨论把mknmz时间变成和comparable一样的加速方法的话,对于Personalized PageRank 来说就十分实用了。作为参考,根据Page et al.(1998),Google 对7500万的URL的实际 PageRank 计算时间约是5小时。(2001年2月现在不明)。从这个角度来说,研究更加高效的加速法的余地就十分得必要了吧。

    计算实际运行时的使用内存最大也是10几MB左右。如果是Haveliwala (1999)那样的「吝啬地作战」的话,最大只有O(3N+2)左右的内存使用量就做完了,不过 N 是 104-5 程度和内存的使用量连 N2 也放不进的话,其他的也只能勉强调谐了,所以以 O(5N+α) (α是疏松行列的非零成分数字,典型的是5-20N左右) 程度来编写代码。另外 N 是103 左右时,可以确认不压缩疏松行列就在内存上使用幂乘法来计算,从速度面上来说是非常有利的。实测时速度为上述数字的6-7倍左右的。但遗憾的是,这个方法从内存的限制来看,尽可能地只使用2-3千页以内。

    此次我们使用了 Octave 分发附属的「Tsurushi」,不过,正像大家知道的那样,如果把 Octave 调谐的好的话,会戏剧性地提高完成的速度。Octave-2.1.x 和 ATLAS 的组合有时候根据情况甚至会使大规模行列乘法的运算速度提高10倍以上。

    实验的详细结果请参照prnmz-1.0.tar.gz 中的文档。

    Personalized PageRank 的基本性质

    人们经常会利用 MHonArc、latex2html 或者 PowerPoint 这样的工具将文档变成 HTML,针对这样的人工制作的HTML链接群求 PageRank 的话,大部分页面的得分几乎都是一样的(~1/N)。如果考虑邻接行列,则大部分的成分是1,或者对角成分附近全部是1。因为这样的推移概率行列的固有矢量成为(1,1,…,1)。

    或是象 sitemap.html 一样变成树状的情况下,分数会集中在sitemap.html中。就算占据全体的9成也不算新奇。

    从现在起能说的是,为了计算有意义的 PageRank,要尽可能地排除机械生成的链接关系。如果把链接关系看做是推荐关系的话更加容易认同了吧。

    6.对 PageRank 的个人的见解

    (读者)应该没有余地去怀疑象 PageRank 那样利用超级链接来决定排列次序有效手法吧。

    不过,阅读了这些论文以后笔者自身也考虑了许多问题。在这里,列举几个对 PageRank 的个人见解。虽是见解,说到底就是方法论,也许会有很多错误的地方。

    • 关于 dangling page,不相反考虑的原因是什么?

    只是因为考虑一定的变异概率时「偶然」会变成最简才不予考虑吗?还是有时看漏了什么吗?稍微有点不太明白。

    • 改善推移概率行列的可能性

      说起来,为了保证 PageRank 的单一意义的性质(一意),只要保证推移概率行列是最简(有向图表是强联结)就行了,没有必要所有的要素 aij 都是非零要素。事实上,像在web上浏览 Toyota 汽车网站后紧接着跳向色情网站,接着又继续跳到白宫网站浏览的怪异的人应该是不存在的吧。(请注意这里是指在随时间变化连续的形式)。因此,从实用的意义上来说,区别于改善多少的使用方便程度,应该留下对算法改良的余地。

    • 考虑「逗留概率」会怎样

    根据 PageRank 的考虑方法,在一定的时间后必定顺着链接前进到其他的页面,或者突然怪异的、歪曲的跳到其他页面。但是如果对照现实的web浏览模型,也要考虑一定的逗留概率。具体地说,就是推移概率行列的对角成分中只取( 1-c)/N 的话取得过小了。在原本所有变迁概率都一定的情况下,更加进一步分析会怎样?因为对于无聊的页面(浏览者)必定会想都不想就转到另外的页面,反过来对于重要的页面却会停留较长的时间。

    • 如果考虑概率论应用的话必定会考虑其他许多问题

    即使是将实现性置之度外,我们也再来试着进一步考虑这个想法。概率论中,存在着一种叫消灭概率或叫固定概率的概率。比起 PageRank 的单纯而同样考虑方法,导入这种考虑方法会得到更期望的结果,所以理所当然被大家所期待。大家都知道马尔可夫链中的分枝过程的考虑方法。这是考虑遗传基因突变时的一个模型,即,说明经过一定的时间而产生淘汰的可能性的模型。很多人认为这个考虑方法或许会被采用。那么导入带有限制的概率(禁忌概率)又会怎么样呢? 即,相当于导入通过 n 次的推移从状态 i 移动到状态 j 时,不经过状态 k 的概率。如果考虑到web浏览的性质的话,不是也能理所当然地成为假定吗?

    • 不能作为非马尔可夫过程(或者说 m次的多重马尔可夫过程)来考虑吗

    所谓马尔可夫过程,就是与过去的经历无关,只从现在的状态来确定未来的概率法则的概率过程。 马尔可夫过程只依存于1步之前的过程。这个过程和没有对过去的记忆,没有依存于过去经历的要素。 PageRank 是在单纯马尔可夫过程随时间变化而固定的状态下计算时候所求得的结果。但是,人类的理性行动必须以非马尔可夫过程来表现。复杂的过程总是以一些形式和过去有着牵连。因此,不仅仅单一地分析从哪个页面连接来,而要分析沿着怎样的路径连接而来的。这样的分析才会使其有可能成为更有用的排序系统。在能抑制住计算量爆炸的范围内,试着引入非马尔可夫过程来研究说不定也很有趣。

    在考虑到和看到的许许多多中,有像实际安装那样不太难的东西,也有因为只是嘴上说说而不知道怎样实际安装的东西,不管怎样,定量地评价它的效果是极为困难的。难道真的是不能实现的东西吗?

    PageRank 的技术有多少

    即使只是采用评价很高的 PageRank 技术,作为基本的想法也只是使用了枯竭的数值分析的手法来实现的。但是,象我在这里说明的事情,如果从专业的研究者来看完全是理所当然的事情了。只是克服规模这一点就能建立一个专业的研究领域吧。 也可以认为专业领域的内部并没有那么深的尽头。事实上,我做事,充其量只是表示了「如果是极其小规模的问题,即使是教科书的手法也能大约地得到满足计算量的结果」。

    尽管是这样,充其量只触及了概要的表面就在嘴边说「没什么嘛,原来是程度这么简单的技术呀」 的那种不懂装懂的人也是有的。在这里事先强调:这种浅薄的看法是从根本上完全错误的

    当然,PageRank 技巧的非常好的地方是「从许多优质的页面连接过来的页面是还是优质的页面」,如果明白了就会觉得是简单的想法。但更进一步说,真正绝妙的地方是,不仅仅只是想到一个主意,而是将想法用固定状态变迁的概率分布来定式化,为了实证其有效性而实际地进行安装实验,并证明其在现实领域也能很好地运作的过程。在所有的这些阶段都成功了才是真正值得被称赞的。

    的确,不仅有斩新而且巧妙的想法,再加上结合教科书的手法,也有可能制造出能和 Google 匹敌(或是凌驾)的搜索引擎。也可以说实际上 Google 自己也在这么做着。但是,实际完成的人却是少得惊人。假想模型中的「肯定能够完成」的东西和实际运作的东西之间有着天差地别。在实际问题上,处理大规模疏松行列本身,通过一般的手法也是相当的困难,需要高度的专业技术。应该铭记在头脑中总觉得能够理解的事和实现中能够做的事之间绝对会有不能填埋的差距。不可过分轻率地考虑。

    7.参考文献

    以下列举了除了在「前言」中介绍的基本论文以外的关联论文。(译者去掉了许多无用的连接)

    以下列举数学关联的参考书籍。

    • S.卡琳 著,佐藤健一,佐藤由身子译,『概率过程讲义』(数理分析与周边3),1974年,产业图书
    • 岩堀信子著,『图表和概率过程』 (与数理分析与周边4),1974年,产业图书
    • 伊藤升 他著,『经济系、工学系的行列及应用』, 1987年,纪伊国屋书店, ISBN4-314-00477-0
    • L.V.Atokinson, P.J.哈里, J.D.赫德森 共著,神谷纪生,大野信忠,佐胁丰,北荣辅 合译,『数值计算及其应用- FORTRAN77-』, 1993年,Science公司,ISBN4-7819-0690-7
    • 宫泽政清著,『概率和概率过程』(现代数学研究小组17),1993年,近代科学社, ISBN4-7649-1034-9
    • 伊理正夫著,『线形代数II』(岩波讲座应用数学11) ,1994年,岩波书店, ISBN4-00-010521-3
    • 韩太舜,小林欣吾著,『信息和符号化数理』(岩波讲座应用数学13) ,1994年,岩波书店, ISBN4-00-010523-X
    • 小国力著,『MATLAB及其实际利用-现代应用数学和CG -』( Information & Computing=86),1995年,Science公司, ISBN4-7819-0763-6
    • 长谷川里美,长谷川秀彦,藤野清次译,『反复法 Templates』(应用数值计算Library),1996年,朝仓书店, ISBN4-254-11401-X
    • 小谷真一著,『测每次和概率2』(岩波讲座现代数学基础10 ),1997年,岩波书店, ISBN4-00-010640-6
    • 藤野清次著,『数值计算之基础-以数值解法做为中心』(Library新信息工程之基础9),1998年,Science公司,ISBN4-7819-0861-6

    与有关 Google 的在线新闻报道(日语新闻)已经分离到其另一张页面(googlenews.html) 。(2003/5/20)

    其他,特别列出几个认为有关联的页面。

    感谢转载!其他许多的个人站点和BBS都介绍了此文。

    8.附录:「guguru?/ goguru?」

    英语(美式英语)中是不可能把 Google 念成「goguru」的。 和没有人拉面的 noodle 发音或标记为「nodoru」一样,如果硬要用片假名来表示的话应该写成「グーグル」。

    不过,有oo 这个拼写的英文单词有以下这些。

    book, bool, cook, cool, food, good, hook, look, loop, loose, mood, moon, noon, pool, roof, soon, tool, wood, zoo, …

    这些都是简单的一般的英文单词,但不论取哪个都有「u:」这个发音。至少,对许多的典型的日本人来说听起来是这样的吧。英语(美式英语),oo 的拼写基本读成「u」。当然,goo就读成「gu:」。 广末凉子不也在中古车信息杂志的电视广告中说「如果要说车,gu―」吗?另外,游泳时使用游泳眼镜的拼写是 goggle。

    当然,如果 Google 不是英语(美式英语)话那就另当别论了。但是,Google 名字的由来是从表示10的100次方的英文单词「googol」而来的,也许还是英语发音比较适合(google)吧。不用说,googol 的发音也是「guguru」吧。

    另外,创业者之一是 Sergey Brin,从他的名字就能明白他是俄罗斯出身,也有可能是他的英语发音带有自己的方言。如果扯到那里的话,已经是牵强附会了。而且,我也不太清楚Google 用俄罗斯的地方口音怎么发音。如果有识之士在的话,请一定告诉我。

    补充(2001/4): 给Google的支持中心发了「是goguru,还是guguru?」的询问信的一位读者,热情地给我转发了这封邮件。对方说虽然 Google 自己本身的发音是「guguru」,不过,你以你自己喜欢的叫法称呼也决不会介意的哦。

    Date: Wed,31 Jan 200116:12:01-0800
    From:”GoogleTech”<googletech@google.com>
    Subject: RE:{Google#034-917 } pronunciation
    To:转送邮件者(Thanks)!
    
    We go by:”GU Gul” 
    
    But you are welcome to say whichever you prefer! 
    
    Regards,
    The Google Team 

    补充2(2001/10/29):请看Google的页面 ”Google”怎么发音


    Hajime BABA / 馬場 肇 <baba@kusastro.kyoto-u.ac.jp>
    Copyright (C) 2001-2003 Hajime BABA. All rights reserved.
    $Id: pagerank.html,v 1.113 2003/07/23 00:38:48 baba Exp $
     翻译:Kreny / 袁 黄琳 <krenyATdalouis.com>
    创作于:2003/12   最后更新: 2004年10月28日 3:53

    返回首页