异质复杂信息网络上的搜索路径研究*

唐四慧

(华南理工大学 工商管理学院，广东 广州 510640)

随着互联网应用的普及，使用这些应用的个体与个体之间的交互行为会产生一些大量的，相互作用的信息网络，Newman在他的论文中将这种在结点上存有信息的网络归结为信息网络，他举的最典型的信息网络的例子就是引文网；另一个就是万维网，这个网络不同于互联网，它是由网页及网页之间的链接组成的。[1]对于万维网的研究非常多，最多的研究领域是网页的推荐算法，根据CNNIC的调查，2010年仅中国网页数量达到600亿个，年增长率达78.6%，在这样的庞大的网络中如何有效的提供网页搜索推荐确实是一个具有挑战性的问题。

一、研究背景

对于如此巨大的网页数量，更多的研究是将推荐问题聚焦在一些特定的应用中，如Amazon的图书推荐、Netflix的电影推荐、Youtube的视频推荐、eBay的商品推荐等等。推荐系统各种各样，包括协同过滤(collaborative filtering)推荐系统，基于内容(content-based)推荐系统，混合(hybrid)推荐系统。[2]随着用户使用数据的不断被记录，基于用户行为数据形成的信息网络之上的推荐方法也随之被提出，其中有周涛的资源分配算法，[3]Han的RankClus算法。[4]在周涛的资源分配算法中，他将用户和产品的二部图映射为产品单粒子图，对边和点进行加权来做推荐的，这种映射的操作会使推荐问题简化，但也会使得一些信息被丢失掉；在考虑了映射操作会使得异质信息网络的信息损失后，Han在其RankClus算法中，直接对异质的信息网络进行排序和聚类操作，研究结果显示这种不进行映射的算法所得的排序结果和聚类结果都更加有意义。在一般的推荐算法中，都会用到排序这一环节，通过排序得到哪种商品是用户最想购卖或最想阅读的。在Han的算法中，核心是利用聚类后的条件概率进行排序，然后利用排序的结果来指征聚类的优劣，他给的例子是会议—作者的两类异质网络，对于多类异质网络仅是一带而过没有更详细的交待，事实上，我们发现现实社会中更多的信息网络包括两种以上的异质结点，本文中所研究的豆瓣网数据，它就包括小组，组员，图书三类结点；另一个是在他的研究中假设会议这种结点之间是没有关系的，关系仅存在于会议与作者，作者与作者之间；而我们的案例中，小组与小组，组员与组员，图书与图书，小组与组员，小组与图书，组员与图书之间均存在不同类型的关系，并且我们通过对组员的行为进行分析后发现，小组，组员，图书这三种结点在推荐中有先后关系，这些现象是Han的论文中不曾涉及的，因此我们认为有必要对这一现象进行分析，进而产生更有效的推荐方法。

二、前人的研究

基于网络的搜索，最早的研究我们可以追溯到Milgram的小世界实验，在Milgram的实验中，他选定了两个目标对象，一个是美国马萨诸塞州沙朗的一位神学院研究生的妻子，另一位是波士顿的证券经纪人。然后他在遥远的堪萨斯州和内布拉斯加州招募发信者，要求发信者通过自己的熟人，用自己认为尽可能少的传递次数，将信转交到一个给定的目标对象手中，实验的结果证明社会网络是可达的并且是可导航的。[5]在2002年，Watts等人重做了上述实验也证明网络的直径是小的，并且网络是可导航的。[6]Watts在其后来的研究中，对这种可导航性进行了解释，他认为在实际的社会网络中人们会根据各种各样的标准来判断两人之间的距离，地理位置、职业、国籍、受教育程度、兴趣爱好等都是很好的标准，这些标准将整个世界分为更小更特定的团体，在对团体进行划分的时候，通常存在多重标准。[7]这种结论的得出，是基于他前面实验的结果，在那次实验中他发现在搜索的早期大约在前两、三步人们会考虑地理上与目标对象接近，到了三步以后人们更多的考虑后续者在职业上是与目标对象相似的。在整个搜索过程中，我们可以看到判断标准是在变化的，因此我们考虑异质信息网络的搜索时，我们用异质的树结构搜索方式更符合实际情况。但我们在做图书或音乐的推荐的时候，与Watts不同的是，我们并不知道目标是什么，更不要说目标的具体信息。

另一种搜索的研究是Gnutella网络中的广播搜索，它与我们这里研究的内容相同的是用户并不知道所要查找文件在网络中的具体位置，因此在每次信息传递过程中不知道是接近还是远离了目标节点。在这样的搜索条件下，Gnutella采用的是一种广播的方式进行搜索，为了避免搜索范围的几何级数的增长，在Gnutella网络搜索中规定每次查询的生存时间为5次或6次。为了减轻Gnutella中广播搜索带来的大量的流量负载，人们提出了一些改进的方法如Yang和Garcia-Molina提出的有向广度优先搜索策略，[8]在这种搜索策略中要求源节点选择一些能够快速返回高质量结果的邻居并将查询消息发给它们，为了能够选择“好”的邻居，在每个节点中会存储一些关于邻居的简单的统计信息，这样就自然而然的形成了我们前面所讲的信息网络——在结点上存有信息的网络。这种搜索策略与我们研究的对象不同的是，在它进行搜索过程中，它的邻居会加入到搜索过程，而我们研究的图书推荐或音乐推荐主要是用户自己的查找，查找的深度会比有其它邻居加入的算法要短，因为一个人的精力是有限的。对于本地信息的存储内容，Yang和Garcia-Molina又提出了一种本地索引的方法，在这种方法中本地节点上会存储与自己距离在r步之内的所有节点的文件目录。[8]

图1 读过与想读关系图

图2 分类与排序关系图[4]

(一)数据来源及收集方法

我们考虑图书推荐是一个比较经典的推荐例子，同时在豆瓣网上图书、用户、小组呈现出的多种类型的关系也比较符合异质网络的特性，在豆瓣网中每本图书、每个用户、每个小组都有一些介绍信息，这也符合我们对信息网络的要求。此次实验的数据来自一个比对实验，我们先在图书馆中抽取了6万多条借阅记录，然后再将借阅记录中有的书，在豆瓣网上找出来，比对这两种不同方式推荐图书的效果，另外豆瓣网也有一个推荐效果的记录就是每本书都有一个读过和想读的记录，记录下哪些用户读过，哪些用户想读，想读的用户我们可以理解为受了网上宣传或读过这些书的人的影响。我们共找到1291本图书，有923个读过这些书，简单的统计信息如表1。

表1 读书的简单统计信息表

我们将读过的人数和想读的人数画在图上，得到图1。从图中我们找出那本想读人数最多的书，书的编号为1049136，书名为《数学: 确定性的丧失》，原来共有53人读过，现在有91人想读。这本书只被一个名为数学的小组所收藏，如果用户参加了这个小组，我们可以认为书的信息可以通过对小组收藏书籍的浏览所获得。

为了去除小组对于想读书的影响，我们收集了另一组数据，此组数据中的书籍是某个组员读过，小组的收藏中没有的书籍，收集的组员注册名为jake，他读过的书但小组没有的如表2。

表2 组员有小组没有的书籍被想读的统计信息表

在这个表中，我们可以看到，想读的人数非常多的书籍，在关注jake人中并不是很多，这里我们理解为，这些被很多人想读的书籍属于热门书籍，人们可以通过很多渠道得到对于该书的评价，如《长尾理论》这样的热门书籍，学生在学校的时候老师都会讲到这本书，甚至在当当，亚马逊这样的网上书店，这些热门的书都会出现在网站首页的醒目位置，所以这里非常多的用户不是通过关注jake来得到这本书的信息也是非常正常的。反而我们应该关注的是那种想读的人不是很多，比如人数是100以下，而读过的人不是很多的那种书，它是怎样通过豆瓣中的关注关系扩散开来。这才是本文要研究的重点，如何让一些大众媒体没有观注到的，而且对于读者个人来讲又是有意义的书籍，如何进行推送。这里我们看到有四本书是比较符合我们前面的限定：《量子计算和量子信息(一)——量子计算部分》、《Quantum Finance》、《In the Beat of a Heart》、《Laws of Form》。选择这些书去研究它们的推送过程还有一个优势，在于这四本书里有三本是外文名，基于关键字的查询方法，它的优势在于只要读者能够比较准确的判断自己所需书籍的关键字，往往可以通过关键字来找到自己所需的书籍，但如果是外文的书籍，我们在判定所需书籍的关键字的时候就会存在一些困难，这时人际推荐的意义就显得更大。

(二)数据分析

在对数据进行分析时，因为我们研究的是异质的网络，传统的分析是将网络映射为单粒子然后再处理，我们想直接对异质的粒子进行处理可以用的方法如Han的条件概率的方法，因为在计算条件概率时条件和概率可以是不同的属性，比如条件是圆的(形状)，红色(颜色)，判断它是苹果(水果种类)的概率，在这里我们可以看到异质属性在一个公式里出现，另一个我们常用的就是判定树，判定树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出。判定树同条件概率一样可以将不同的属性放在一起进行判断，但在判定树中会体现流程的概念，我们选用判定树的方法来分析这些数据。

图3 数学被传播的判定树

对另一组将小组的影响去除的数据我们也可以得出这样的判定树图：

图4 量子被传播的判定树

(三)结果分析

我们将计算的结果列在下表中：

表3 小众书籍传播的可解释比例表

可解释人数的计算是关注过读过此书的人，参加过此人为小组长的小组，参加收藏此书的小组或这个小组的友情小组，我们认为影响流是通过这些关系流动的。

图5 搜索小众书籍的路径图示

图6 异质网络间相互影响示意图

在这张图上，我们除了看到成员在形成自己的社会关系网络，从而对自己今后的读书信息过滤起到作用，而且看到了成员从一个已知的领域走向自己未知领域的理性过程，自己读过的书、自己的兴趣，成员自己是知道的，由自己知道的找到与自己相似的一群人——读过同一本书的人(这些人并不一定会形成关注关系，它只是为下一步找寻小组信息提供过滤的标准)，然后找到读过同一本书的人参加的小组，然后再在这些小组中找到跟自己兴趣相近的人形成关注关系，然后通过这样的关注关系，找到自己没有读过但与自己有较大关系的书。这里需要澄清的一点是，成员为什么不是通过读过同一本书来找自己关注的人，因为在豆瓣中每个成员的名字都是自己定义的，有英文，有中文，有数字编号，成员发现与自己读过同一本书的人后得到是这个人在豆瓣注册的用户名，这个用户名基本不包括用户的兴趣，另外，与成员读过同一本书的人是非常多的，在如此重多的选择中找到与已相似的人所需的精力是比较大的。不去直接选择读过同一本书的人形成关注关系，从小组的角度来讲，小组的组名一般会以小组关注的问题为名，并且小组的组数要远小于成员的人数，举个例子，《虚实世界：计算机仿真如何改变科学的疆域》读过这本书的用户有96个，但收藏了这本书的小组只有3个，分别为集智俱乐部小组、人工生命小组、复杂自适应系统研究小组，这些小组的名字中会有一些与书名契合的点，成员可以通过自己的经验来选择这些小组，所以小组在这里起到的作用是帮助进行信息过滤和桥的作用。

四、结论

通过对异质的复杂信息网络上的读者被影响行为的研究，我们发现，读者在找寻自己想要读的书时候可以有多种获得方式，通过自己构建的社会网络是一种形式，这种形式对于较专业的书籍的推荐作用是比较大的。整个的图书信息的获得是有路径的，读者大多是从自己关注的人或关注的小组获得，从关注的人那里获得的解释更多些；而对于自己关注的人是怎么得到的，我们从小组角度进行了解释。所有这些都与传统的度大的结点(小组，成员，书)会获得更多的关注存在不同，这与Watts的搜索实验相印证，在他的实验中没有出现“漏斗”现象——大家通过度大的点来传递信件，我们认为这是人们利用信息网络中结点信息的结果。另一个，我们发现，在进行推荐的时候，如果我们将异质的网络转换成单粒子结点时会损失信息，在我们发现的找寻路径上，发现了小组、关注的人在不同的阶段起到不同的作用，这也与Watts实验中，前三步人们用地理信息，后续步骤用职业信息吻合，由此我们可以看出不进行映射操作是必要的。文章中提出的判定树的方法是对以往分析异质网络的一种尝试，用了这种方法我们确实也得到了一些新的结果。由于篇幅的限制，我们应该还可以做的更细致些，如在确定小组后读者如何找到自己关注的人；加入小组后，如何确定自己感兴趣的书；另外，我们还可以考虑将条件概率方法与判定树方法相结合，因为条件概率方法提供的是一种概率，更容易让人接受。

参考文献：

[1]Newman M E J.The structure and function of complex networks[J].SIAM Review ，2003(2)：167 -256.

[2]刘建国，周涛，汪秉宏.个性化推荐系统的研究进展[J].自然科学进展，2009(1): 1-15.

[3]Zhou T, Ren J，Medo M，et al.Bipartite network projection and personal recommendation[J].Phys Rev E，2007(4)：1-10.

[4]Yizhou Sun，Jiawei Han.RankClus：integrating clustering with ranking for heterogeneous information network analysis[C].Saint Peterbung, Russia: Extending Database Technology - EDBT, 2009 ：565-576.

[5]汪小帆，李翔，陈关荣.复杂网络理论及应用[M].北京: 清华大学出版社，2006.

[6]Peter Sheridan Dodds，Roby Muhanad，Duncan J Watts.An Experimental Study of Search in Global Social Networks[J].Science，2003(301)：827-829.

[7]Duncan J Watts，P S Dodds，M E J Newman.Identity and search in social networks[J].Science，2002，296：1302～1305.

[8]Yang B，Garcia Molina H.Improving search in peer～to～peer networks[C].Vienna, Austria: Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02)，2002.