每一个可以努力的日子,都是一份厚礼。
PageRank与社交网络模型评估(3)
5. HITS算法
与PageRank算法类似,HITS也是在网络建模和权重排名中比较经典的算法。
有的时候我们希望把高centrality值赋予那些链接了很多重要节点的节点,例如综述性的学术论文引用了该研究领域内的大量重要论文,于是这篇综述也被认为很有价值。因为即使这篇论文没有为该科研领域做出什么突破,但它总结了已有成果,告诉大家去哪里找做出了突出贡献的论文。
于是我们拥有两种节点:authorities(权威型)的节点包含了具有贡献的原创信息,hubs(枢纽型)节点总结了很多信息,指向了很多authorities节点。Kleinberg是康奈尔大学一位十分牛B的年轻教授(70后年轻有为啊!),他提出了hyperlink-induced topic search (HITS)算法来量化计算authority centrality和hubs centrality。
在HITS中对于某个节点i,xi用来表示authority centrality,yi用来表示hubs centrality。每个节点既有authority属性又有hubs属性。节点若有高xi值则该节点被很多其他hub节点关注,如论文被大量引用、微博有很多粉丝。节点若有高yi值则该节点指向了很多其他authority节点,例如一篇综述论文,又例如hao123.com这样的网址导航站点(理解百度为什么要收购hao123了吧)。
用数学语言描述如下:
或者矩阵表达式
合并演化得到
这意味着authority centrality为AAT的特征向量,而hubs centrality为ATA的特征向量。有趣的是AAT和ATA拥有相同的特征值λ,大家可以自行证明。
我们知道了x,也就可以计算得到y。
6. 社交网络建模工具(Python)
最近比较忙,如果没有需求,这个系列可能就不会再继续写下去了。下面用一个python程序来演示社交网络的建模分析,以实际应用作为结束吧。
假设有这样两个文本文件sigcomm_author.txt和sigcomm_network.txt,文件内容如下:
sigcomm_network.txt:
1,2 (ID_1 与 ID_2 有合作发表论文)
3,4 (ID_3 与 ID_4 有合作发表论文)
4, 216 (ID_4 与ID_216 有合作发表论文)
…sigcomm_author.txt:
1: Amer El Abbadi (ID_1: name)
2: Thomas Lui (ID_2: name)
…
这是一个学术圈的社交网络,描述了发表论文的作者之间的一些合作关系。它一个无向图,也就是说[ID_1, ID_2] 等同于 [ID_2, ID_1]。通过编写程序,我们可以挖掘如下信息:
- n: 节点数量(有多少个作者)
- m: 边的数量(有多少个论文合作关系)
- 网络中连接部的大小(节点互相连接形成网络连接部,另外还可能有孤立的一些节点(自娱自乐么,比如我,发表了2篇论文,无人引用。。。)。其实就是所谓的人际圈子,一个圈子里的作者们互相引用论文,而跨圈子引用可能就比较少,例如计算机专业的学术圈子会很少引用化学学科的论文。)
- clustering coefficient群聚系数
- 网络直径(两两节点间会有一条最短路径,在所有的节点对中,最长的最短路径有多长。六度空间理论嘛,不过Facebook最新研究表明只有不到5度,也就是以不超过5个人的关系你可以联系到这个世界上的任何一个人。)
- 节点度分布(大概应该是幂律分布,有高连接度高影响力的人少,大部分人都是平庸的。)
- 最短路径长度分布(看看每个人的六度空间系数都是怎么分布的)
- degree centrality
- eigenvector centrality
NetworkX是一个用Python语言开发的图论与复杂网络建模工具,内置了常用的图与复杂网络分析算法,包括我已经介绍过的degree centrality,eigenvector centrality等等。使用NetworkX可以方便的进行复杂网络数据分析、仿真建模等工作。
一般Linux都默认自带Python运行环境,Ubuntu下只需要执行以下命令即可获得NetworkX库进行程序开发。
sudo apt-get install python-setuptools sudo easy_install networkx |
Windows下则需要手动安装,具体可以参考这个安装步骤。环境都搭建好了之后就可以对社交网络之间的关系进行分析了,查看这个入门指南。
回到上文提出的例子,在调用NetworkX提供的接口的基础上,我们可以挖掘论文作者之间的关系,分析整个网络的一些属性。示例源代码和测试数据都在 Github 上供围观,你也可以直接 下载ZIP包。
更新:
7. EdgeRank 和 GraphRank
不知道大家有没有注意到,人人网手机版客户端上会显示朋友们的所有新鲜事,而 PC 网页版上则会过滤掉一些。这是为了控制信息泛滥,防止某些人刷屏,其实也是还一种排序策略。
今天和“史上最牛学长” yewen 讨论社交网络中的 Feeds(新鲜事)呈现,了解到 Facebook 的一套排序算法。有了我之前介绍的这些算法的基础,再去尝试思考这些问题,应该还是比较容易理解的。推荐阅读《乱弹 EdgeRank》。
这篇文章由lovelucy于2011-05-25 21:15发表在网络。你可以订阅RSS 2.0 也可以发表评论或引用到你的网站。除特殊说明外文章均为本人原创,并遵从署名-非商业性使用-相同方式共享创作协议,转载或使用请注明作者和来源,尊重知识分享。 |
批评不自由
则赞美无意义
Google Chrome 61.0.3163.98 MI 6 Build/NMF26X) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/61.0.3163.98 Mobile Safari/537.36 大约7年前
非常感谢博主,解释得简单明了,连我这个没学过高数的文科生都看懂了。