WISE 竞赛的组织者收集 到近百个GB的数据，归纳出与粉丝关系和微博转发相关的 19 个查询题目 ，广发英雄帖， 希望参赛者 对这些查询的通过量、延时和数据规模等三项指标 进行 性能分析，从而预测微博转发和阅读范围，例如 11 年 6 月 5 日李娜于法国网球公开赛夺冠时新浪微博的热议 … (本文作者为：李伟钢、方令、Edans Sandes 和 Felipe Modesto)。 粉丝模型亮相 神奇的网络已悄然铺开，星罗棋布的各类关系正潜移默化地影响着博主们的信息传递方式。而网络专家们基于上述分析，开始建立描述微博这些关系和机制的数学模型，来进行粉丝查询和转发预测。 微博类在线社交网络可以用一有向图来描述：G = (V，E)，这里图的节点V表示用户；节点间的有向连接为E：V x V，表示用户间的关系。(A,B)ϵ E, 表明用户A关注用户B，即A是B的粉，B是A的关注人。 较正式的用户关系数学描述是这样的：对于用户间关系函数 f in 、 f out 、 f r ，V →V*，有： f out (A) = {B|(A,B) ϵ E }，表示A的关注人集函数，A关注B； f in (B) = {A|(A,B) ϵ E }，表示B的粉丝集函数，A为B的粉； f r (A) = f out (A)∩ f in (A)，表示A的互粉集函数，A的关注人集合与关注A的粉丝集合之交集。 这些函数称为粉丝模型 ( Fans Model ) ，并可以进行不同目的的组合：如 f in • f out (A) 是指A关注人的粉丝集函数，而 f in 2 (A)就是A的粉丝的粉丝集函数，而 f r n (A)就是A的互粉的互粉的...互粉的集函数。 而上述新浪微博页面的系统推荐信息， “关注 TA 的人同时关注了…”对应的粉丝模型， 是对 f out f in (A) 的求解 ；“这些人也关注 TA …”，可由 f out (A)∩ f in (B) 函数来描述；而“我和 TA 都关注了…”的查询则是对 f out (A)∩ f out (B) 函数集 的计算。 这些看似简单的用户关系数学描述，却是微博 的 转发哲学精华所在，里面隐藏着信息传播的关键线索和主要渠道，更是纵深了解博主和其粉丝们的网络行为、开发优化算法以及充分发掘微博价值的理论基础。 微博大赛为哪般？ 在网络信息技术方面颇有影响的 国际 Web 信息系统工程会议 ( The 13th International Conference on Web Information System Engineering ， WISE ) 今年的亮点是举办以新浪微博为主题的大竞赛项目。 WISE 竞赛的组织者从新浪微博收集到客户关系数据和微博信息数据，提出两个竞赛项目。第一个是对客户关系和微博信息数据的查询性能比赛，组织者归纳出微博关系和转发的 19 个查询题目，要求参赛者开发优化算法，并使用由中国 IMC 公司推出的 BSMA 性能测试工具 ( Benchmark for Social Media Analysis ， BSMA ) ，对这些查询进行通过量 ( Throughput ) 、延时 ( Latency ) 和数据规模 ( Scalability ) 等三项指标进行性能分析。 这 19 个查询题目十分有效和实用，不妨列出前三个为例进行说明。这些查询的结果都需要从海量数据中理清客户关系，得出合乎某种要求的 Top-X ，即常说的前 10 名、前 50 或 100 名： 查询 1 ：列出某用户互粉的互粉排行，查询目的在于推荐给该用户这些朋友的朋友， Top-X 次序以粉丝量为准，亦可根据需要以微博数或转发数等为准。 查询 2 ：列出某用户关注人的粉丝排行，了解该用户关注人的粉丝情况，以便推荐关注， Top-X 次序以粉丝数量为准。 查询 3 ：列出某用户关注人的关注人排行，了解该用户关注人的关注人的情况，以便推荐关注， Top-X 次序以粉丝数量为准。 图二显示该模型用于查询 1 的示范，即用户互粉的互粉 Top-X 的计算过程。例如，用户 A 的互粉数有 4 个： f r (A) = {W ， X ， Y ， Z} ，他的互粉网友的互粉网友可按下式算出： f r 2 (A) ＝（ f r (A) ∩ f r (B) ）∪（ f r (A) ∩ f r (C) ）∪（ f r (A) ∩ f r (D) ） ＝ {B ， C} 。 图 2 微博粉丝模型用于挖掘互粉的互粉 Top-X 的查询示意 图二示例非常简单，共涉及 7 名用户，口算即可得出。但实际上如果 A 有 M 个互粉，每个互粉有 N i 个互粉， i ＝ 1 ， 2 ，…， M 。考虑到 Top-X 的排序，如果这些互粉的粉丝数没按大小排序的话， f r 2 (A) 的计算复杂度为Ｏ (Mx(N 1 +N 2 + … +N M )) ；如果这些互粉的粉丝数已按大小排序， f r 2 (A) 的计算复杂度为Ｏ (M+N 1 +N 2 + … +N M ) 。面对微博海量数据，加上提及、转发和时段等约束条件，这些计算的工作量将会很大，需要在粉丝模型的基础上进一步开发优化算法，提高各项查询效率。 这个模型对微博传播机制研究也意义重大。 A 发出的微博可以到达用户 {W ， X ， Y ， Z} ，由于他们是 A 的互粉，有极大的可能转发 A 的微博，传到 {B ， C} 处。这些查询结果是研究微博传播机制的基础，这就引起下面的话题：微博转发预测。 转发预测话李娜 WISE 的第二项竞赛项目是预测新浪微博与 6 个社会事件有关的 33 个微博的转发情况。主办方界定一个时间戳，并给出在此时间前用户对这些微博的原始资料。参赛者应根据发表在 30 天内的这 33 个微博，预测原微博被转发的次数和原微博可能被阅读的次数。一次微博转发行为后，微博可能被阅读数定义为转发该微博的用户粉丝数。原微博可能被阅读的总次数是所有转发行为后该微博可能被阅读数之和。 这两个数字的计算取决于上文已述的微博转发的三种特性、粉丝模型和优化算法得出一些查询结果，由此建立预测模型，如基于条件随机场( Conditional Random Fields-CRFs )模型等，展开计算。图三展示笔者团队参与的本次大赛中，有关新浪微博 2011 年 6 月 5 日对李娜在法国网球公开赛夺冠事件评议的微博转发和阅读范围预测结果。图中，深蓝、浅蓝和粉红色表示条件随机场等三种模型对微博转发数的预测结果；棕色、黄色和红色表示三种模型对微博转发阅读范围的预测结果。 图 3 李娜法国网球公开赛夺冠评议的微博转发和阅读范围预测结果 令人欣慰的是，参加竞赛的清华大学团队，从近 30 个参赛者胜出，以优异的通过量和延时指标获得微博数据查询性能金奖 ( Championship on T1: Throughput and Latency ) ；巴西利亚大学团队以数据规模处理能力并列第一 ( Championship on T1: Scalability ) ；而澳洲昆士兰大学在微博转发预测项目以夺冠 ( Championship on T2 ) 。 微博发展，势头正旺；微博研究，方兴未艾。研究微博粉丝、关注、转发机制，建立数学模型和优化算法，是预测微博的转发路径和信息传播走向的前提工作，可以帮助理清微博世界里错综复杂的万千关系，也能为进一步发掘微博的商业和社会价值打下基础。 本文系巴西利亚大学 TransLab 团队参加国际 Web 信息系统工程会议 ( WISE) 举办的新浪微博竞赛获奖项目部分成果。中文版发表在 2012 年第 8 期《千人》杂志，文章作者为李伟钢、方令、 Edans Sandes 和 Felipe Modesto ，科学网博文版本略有修改。 TransLab 团队的科研活动无任何商业集团资助，纯属公益行为，敬请网友关注指教。 相关博文： 微博的转发哲学 (上) 微博关系的数学描述: 粉丝模型
微博具有在线即时、网络浩瀚、关系复杂、行为任意和海量数据等特征。伦敦奥运期间的社交网络更是丰富多彩，孙杨诗文拉郎配、H2O钓鱼博、《自然》杂志抹黑等等，情况不断，让人应接不暇。跨学科、多方位的理论和技术研究面临着巨大挑战。虽说复杂网络的理论和实践 已取得丰硕结果，但在描述微博用户间的关注(Follow)、互粉(R-friend)以及转发(Repost)等的关系和行为时，理论和方法尚存不足，需要深入探讨和研究。 应运而生的粉丝模型(FANS model)系巴西利亚大学团队参加2012年WISE国际会议微博竞赛获奖项目的部分结果 ，旨在对社交网络新型关系和行为进行 准确有效的数学描述。本文从微博用户界面分析入手， 在前人复杂网络研究的基础上，建立粉丝间关系的逻辑模型，简化微博大数据咨询分析，为研发快捷查询算法提供理论依据。粉丝模型为新浪微博竞赛研发，但对腾讯、网易和推特等微博平台具有同样实用意义。 1．微博之问：“我”和姚晨 ... 笔者和姚晨没什么事儿，本是南美学者，业余研究微博，在新浪有325位粉丝；Ta是当红明星，勤于微博运作，拥有2341多万粉丝，美誉中国微博王。 用笔者的新浪微博账号进入姚博主的微博网页，便是开始有点事了。图一是7月5日姚晨微博界面截图。先看右边新浪微博平台为用户提供的相关信息： 关注她的人同时关注了 …，就是说姚晨的粉丝同时也关注了林心如、李冰冰、郑丽郑丽和走过高考等等。当然，新浪是在暗示“我”，是否需要也和他们一样关注这些... 这些人也关注她 …，这里是说本人的粉丝中也关注她的网友如周杰伦、齐鲁晚报、郑建亚和东方卫视等等。 我和她都关注了 …，这项指标反映了“我”和美女的共同爱好，就是说笔者和姚晨共同关注的网友有杨幂、朱丹和潘石屹等等。 新浪告诉用户这三条信息的意图为何？ 说白了，实际上都是微博平台利用在线查询结果，吸引用户眼球。笔者在微博尚为新人，算算上面的后两项没太大意思。如从新浪微博排行第二的小S帐户进入姚晨网页，两个大腕一起耍，想一想，这拥有2341万和2260万粉丝博主间的并集、交集咨询计算，参照3亿多新浪微博用户，这可是有玩的！更有意思的是如何用数学把这些关系描述清楚，进一步挖掘出有用的社会和商业价值来。 图一 从“我”进入姚晨新浪微博界面截图 2．微博关系的粉丝模型(FANS model) 微博上尊称用户为“博主”，有时亦叫“粉”。在这个社区内，如果用户A关注B，称A是B的粉(Follower)，称B是A的关注人(Followee)。如果A是B的粉，B亦是A的粉，称A和B为互粉关系(R-friends)。 微博类在线社交网络可以用一有向图来描述：G = (V，E)，这里图的节点V表示用户；节点间的有向连接为E：V x V，表示用户间的关系。(A, B) ϵ E, 表明用户A关注用户B，即A 是 B 的粉，B 是 A 的关注人。 较正式的用户关系数学描述是这样的：对于用户间关系函数 f in 、 f out 、 f r ，V →V*，有： f out (A) = {B|(A,B) ϵ E }，表示A的关注人集函数，A关注B； f in (B) = {A|(A,B) ϵ E }，表示B的粉丝集函数，A为B的粉； f r (A) = f out (A)∩ f in (A)，表示A的互粉集函数，A的关注人集合与关注A的粉丝集合之交集。 这些函数把微博用户关系简洁和准确 描述出来。 为便于分析和应用，笔者团队暂将其称为粉丝模型（FANS model），在新浪微博62GB大数据的查询和算法优化方面，已崭露头角，取得理想结果 。 3．粉丝模型基本性质 粉丝模型依附于图论描述的社交网络，也就是常说的在线复杂网络，但具备以下特点： 1）反对称与对称性。 从函数的对称意义来看，可以定义其反函数。若 f ϵ { f in 、 f out 、 f r }，有其反函数 f ′ 定义为： f in 若 f = f out f ′ = { f out 若 f = f in (1) f r 若 f = f r 2）可组合性。 若 f 1 、 f 2 ϵ { f in 、 f out 、 f r }，对于用户间关系函数 f 1 、 f 2 ，V →V*，则函数间的并集、交集计算为： f 1 • f 2 = U f 1 (A), c ϵ f 2 (B) (2) I(A, B) = f 1 (A) ∩ f 2 (B)， (3) 对于交集计算，前述的互粉关系函数定义就是特例： f r (A) = f out (A)∩ f in (A) ，这里 f 1 = f out 、 f 2 = f in 。 3）可扩展性。 考虑到进一步的操作性，这些函数间的扩展可表达更多的用户关系，实现不同查询计算。例如， f in • f out (A) 是指A关注人的粉丝集函数，而 f in 2 (A)就是A的粉丝的粉丝集函数。 这里如果 f 1 、 f 2 相同，(2) 式并集计算有 f • f = f 2 和进一步的 f • f n-1 = f n 。例如， f in 2 (A) 就是A的粉丝的粉丝的集函数；而 f r n (A)就是A的互粉的互粉的...互粉的集函数。 有了微博用户关系的函数定义和特性，图一中姚晨微博平台的有关网友关系的在线查询可以较正式地用数学函数表示了。 关注她的人同时关注了 …，对应上述定义的微博用户逻辑关系，是对 f out f in (A) 的求解，A在这里就是博主姚晨，函数集表示关注她的粉丝同时关注的网友。 这些人也关注她 …，对应上述定义的微博用户逻辑关系，是对 f out (A)∩ f in (B) 的求解，这里的A是笔者，B是姚晨博主，就是说这个用户集是笔者所关注的网友，同时也是姚晨的粉丝。 我和她都关注了 …，对应上述定义的微博用户逻辑关系，是对 f out (A)∩ f out (B) 的求解，这里的A是笔者，B是明星姚晨。函数集表达“我”和Ta共同感兴趣的网友。 4．小结 上面简单介绍用于描述微博关系的粉丝模型和其特性。2012年国际Web信息系统工程会议(WISE)的对客户关系数据和微博信息数据的查询性能比赛项目中，需要参赛者实现对客户关系和微博转发相关的19个查询(Query)。粉丝模型模型的提出使得这些查询的数学描述更准确和方便，成为开发优化算法和转发预测的理论基础。 以后的文章将继续介绍这方面的工作。 需要指出的是，基于图论开展的经典复杂网络研究，提出了某节点用户的点出度(outdegree)和点入度(indegree) 。但这些概念仅是用于研究网络各节点的量化指标。描述微博用户间的关注(Follow)和互粉(R-friend)等关系的粉丝模型具备三个特性，1) 对称和反性对称刻画了动态节点(微博用户)间的单向/双向关系和相互转换规则；2) 可组合性是通过粉丝关系函数间的并集或交集，生成新的用户特性集合，为进一步转发预测和博主推荐开拓空间；3) 可扩展性则是粉丝关系函数的深层展示，根据微博机制，提出新的函数关系定义，使得复杂的用户关系得以清晰和简单的数学描述。粉丝模型的这三个特性，是传统文献中没有的 。 粉丝模型的原创作者为：Edans Sandes, Li Weigang and Alba de Mello，参照文献 。本文以微博平台为实例，进一步解释该模型特性和应用。只是博文中的公式和符号表达不太严密， 敬请网友和同行专家的批评指正。感谢博士生郑建亚和唐建生两位同学对本文中文版的有益建议。 参考资料 Valente, T., (2012), Network Interventions, Science, Vol. 337, 6 July, 2012. Kwak, H., Lee, C., Park, H., and Moon, S. (2010). What is twitter, a social network or a news media? In the ACM proceedings of the World Wide Web, pp. 591-600， Raleigh, USA. D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. J. Am. Soc. Inf. Sci., 58(7):1019–1031, 2007. L. Lü. and T. Zhou. Link prediction in complex networks: A survey. Physica A, 390 (2011) 1150. K Lerman, S. Intagorn, J-H Kang, and R. Ghosh, Using proximity to predict activity in social networks, in the Proceedings of ACM WWW 2012 Companion, pp. 555-556. April 16–20, 2012, Lyon, France. A. Clauset, C. Moore, and M.E.J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature 453 (2008) 98. 2012中国网络科学论坛， 2012年4月。 http://bbs.sciencenet.cn/blog-266190-558494.html 2012年第八届全国复杂网络学术会议， 2012年10月。 http://www.ccnchina.org/ Edans Sandes, Li Weigang and Alba de Mello, 2012, Logical model of relationship for online social networks and performance optimizing of queries, to appear in proceedings of the 13th International Conference on Web Information System Engineering - WISE, Paphos, Cyprus. Championship on T1: Scalability 相关博文 WISE微博竞赛揭晓 四国名校擂台获奖 微博研究系列：WISE，塞浦路斯新浪微博大赛
前几天，在我的博士论文写作正进行得如火如荼之时，意外收到一个印度学生 Zeeshan 的邮件，他介绍说自己是印度 I.I.T Kharagpur 大学采矿工程专业的三年级本科生（看样子比我小不了几岁）， 其邮件的大意是在网上看到我的英文处女作 A comparison of two ISRM suggested chevron notched specimens for testing mode-I rock fracture toughness 之后，对岩石断裂力学很感兴趣，想申请来我们的实验室跟我一起做岩石断裂力学试验方面的研究（约三个月）。看来他把我这个异国的师兄当作老板了，多美丽的误会啊。 我的那篇文章只是刚挂到网上，突然遇到个国外的 fans ，这对我这个尚未毕业的博士生（科研的生瓜蛋子）来讲还真是个很新鲜的事情，感觉很奇特，怎么形容呢，颇有点陌生美人儿冷不丁地向你示爱后过电的感觉吧（有此经历的路人甲会心一笑）。师兄和他老婆当时来办公室知道此事后，他老婆便一脸严肃地问是男的还是女的，我告诉她是男的（业内人士都知道，学采矿的基本没女生），她略有遗憾地感慨：要是个女生就好了，就可以让她过来，印度女孩做媳妇很好，他们的嫁妆还很贵重呢，哈哈，这位师嫂真有点国际媒婆的天赋。当时还联想到《大话西游月光宝盒》调侃说，既是印度的三年级学生，又要来学习三个月，跟三忒有缘了，姑且称之为印度阿三（罗家英饰演）吧。 这里的调侃并没有不尊重这个 fans 的意思，诸位别误会，相反，人敬我一尺，我敬人三丈，我从内心对他表示了极大的赞许和尊重。但是由于我目前不是老板身份，面对这么优秀而又积极上进的 fans ，心有余而力不足啊，最终只能实话实说，告诉他：我目前在做博士论文，没钱养他，希望将来有机会在岩石断裂力学领域多交流与合作，并希望在将来的某个国际学术会议上与他不期而遇 新鲜感过后，我也直犯嘀咕：那么优秀的孩子怎么不像我们中国孩子一样崇尚欧美呢？为何偏偏要来中国？他才大三就非常明确地确定了自己的研究兴趣，并积极规划自己未来的博士研究方向及科研生涯，真可谓深谋远虑啊，大家都知道，尽早地找到自己感兴趣的方向并尽快进入研究状态对科研的重要性自不必言。不知道国内的研究生中有多少人曾积极做过自己的研究规划，更不用说本科生了，至少我在本科期间还是在一片混沌中乱撞和找不着北呢，自愧不如啊，这正是我钦佩这位可爱的印度阿三的地方。仔细想想也不奇怪，印度现在的教育理念是精英教育，像 Zeeshan 这样能在那么好的机构读大学的学生该是他们国内最优秀的孩子之一了，既然是精英，必然有其过人之处，其志气和理想也必是不同于常人了。 总说人家印度穷，但是人家人穷志不短啊，在一些顶尖科技、军事领域也都有很出色的建树，并一直一往无前地向着他们的强国梦进发。这让我想起了中国嫦娥探月工程首席科学家欧阳自远先生去年在我们所里做报告时讲的一段话，其大意是这样的：据说印度要在探月和登月领域赶超中国和日本，你别看印度穷，但是印度这个国家的人很有志气的，如果有一天他们在这方面超过了中国，大家也不必感到奇怪，咱们被超越那只能怪自己不争气，活该 吾志所向，一往无前，愈挫愈奋，再接再厉，请各位学术界前辈们带着我们这些后生们一起争口气吧！ 下面附上我 fans 的邮件内容，哪位同行导师对他感兴趣，请不妨放下架子和面子联系他，圆了这个有志气的印度阿三来中国做科研的梦吧。 Respected Sir, To introduce myself, I am Md Zeeshan , 3 rd y ear student in the department of Mining Engineering at I.I.T Kharagpur (India) . I.I.T Kharagpur is one of the best technical institutes in India. I have read your paper A comparison of two ISRM suggested chevron notched specimens for testing mode-I rock fracture toughness a nd found it quite interesting. I have keen interest in this area. Can I have an opportunity to perform research under your expert guidance in this area, or any other topic you might suggest? I would like to know if it is possible for me to apply for a Internship position at your Lab, during the period May-July 2010 , performing research under your expert guidance. Some of my academic achievements : 1. Qualified IIT-JEE-2007 with an All India Rank of 3177 ( 99.09% ) out of around 0.35 million candidates appeared. 2. Ranked 3 rd in the Department of Mining Engineering, IIT Kharagpur. Projects done: 1.Done a Rock Mechanics project based on Numerical modeling: Numerical analysis of subsidence potential using 2-D and 3-D m odelling in ANSYS over underground uranium mine. Site: Narwapahar mine,U.C.I.L (Uranium Corp. of India Ltd.) 2. Underwent a 2 month Intensive training at Underground Coalfields at Jhanjra, ECL (Coal India), including the study of Longwall Panel development and Underground Continuous miner. If such a position is possible, I am willing to perform any work assigned to me or study whatever material you might suggest, since I have time till April 2010. H ere is the link to my Resume, with detailed information about me. You can also download it in pdf format. If required, I will make a formal application through whatever channels you specify. I would be glad to furnish any further details if required. To reiterate, such an opportunity would really help me in evaluating my career goals since I intend pursuing a PhD programme after my graduation, and hence I would be grateful indeed if you could guide me in this respect. In anticipation of an encouraging reply, Best regards, Md Zeeshan I.I.T Kharagpur India 3rd year Undergraduate Department of Mining Engineering Address:D-107,RK Hall Of Residence IIT Kharagpur India-721302 E-mail: zee.iitkgp@gmail.com
标签: fans
