——《复杂网络实证，演化和动力学》重点项目2009年年度报告

 

本项目组从2007年开始，利用复杂网络的技术，研究信息挖掘与信息推荐的算法。随着互联网和万维网的爆炸性增长，我们可以获取的信息总量呈指数上升。遗憾的是，信息总量的增加，并不能带来用户获取信息效率的增加。事实上，任何以个人都没有精力浏览亚马逊的上百万本书或者万维网上数百亿计的网络。信息过载以及随之而来的信息检索的困难已经成为了信息时代亟待解决的问题。本项目组尝试将统计物理，特别是复杂网络的理论和方法，应用于信息过滤的研究中，近三年来获得了一系列的成果，又一定的科学意义和应用价值。利用物理学的办法研究信息系统的意义和价值，还没有被统计物理与非线性科学的主流学者充分认识到，但是我们相信这一系列的工作会产生长期的重要影响。特别地，本项目组是国际上最早从事信息系统统计物理机制理论与应用系统研究的小组，研究成果具有相当的原创性，这也使得该成果不同于跟踪国际研究热点所做出的改进型研究。

 

到目前为止，在国际物理学正式期刊上共发表接受20篇论文，其中发表在较好期刊上10篇：《新物理学》1篇，《美国物理评论E》3篇，《欧洲物理快报》6篇。主要贡献简单总结如下。(1) 我们提出了一种基于物质扩散过程的推荐机制[1]，该机制可以得到比经典的协同过滤更快且更精确的推荐结果，而且可并行性好。这是利用物理方法解决信息问题的成功范例。这个机制不仅可以用于二元推荐系统（只有用户以及用户选择过哪些物品的记录）的推荐问题，还可以改进后用于更复杂的打分系统（包含用户对物品的打分记录）的预测中[2]。该算法已经被应用于社会标签网站www.sesamr.com 的开发中。(2) 在以往的关于信息挖掘的研究中，研究人员超乎寻常的关注推荐的精确性。然而，我们指出，精确的推荐并不一定就是有用的（例如，推荐拿大奖的好莱坞大片，一般而言观众都会比较喜欢，但是这种推荐缺乏真正的价值，因为观众从其它渠道也可以知道），而推荐系统的价值在于帮助用户挖掘出靠他自己不可能找到的物品。基于此，我们在[3]中率先提出了两个度量推荐多样性和新颖性的指标，并设计了一种对于文献[1]中算法的改进，改进后的算法在精确度、多样性和新颖性三个方面同时得到了提高。更进一步地，在文献[4]中，我们新提出了两种可以刻画多样性和新颖性的指标，并且提出了一种通过消除推荐信息中的冗余，该算法可以在两个精确性指标和四个多样性指标（其中两个指标由文献[3]提出）同时大幅度超过文献[1]。该文是首次在仅仅知道网络链接的前提下全方位刻画算法各项性能（以前的工作都需要知道每个节点的属性或者内容信息）。(3)我们注意到现在很多推荐系统已经不仅仅是用户-物品二部分图，而是用户-物品-关键词三部分图。文献[5]提出了一种三部分图上面的物质扩散算法，该尝试可以在很大程度上提高算法的精确程度，尤其是对于刚刚进入系统的用户和物品，提高尤为明显。(4)链路预测是复杂网络研究的一个新兴问题，受到物理学界的关注始于2008年Clauset等人在《自然》发表的论文。相关研究可以帮助理解网络演化的内在机制，可以用来评估各种节点相似性的度量指标，而且在生物网络实验前预估与在线社会网络朋友推荐方面有重要的应用前景。本项目在这个方向上进行了比较系统的研究：我们提出了一种新的基于局部信息的相似性指标，该指标较文献中常见报道了9种经典的相似性指标有更好表现，并且在最近被另外的研究小组证明在交通系统权重刻画与网络群落结构挖掘方面也表现最好[6]；我们提出了半局部的指标，其计算复杂性和局部指标相似，但是精确度却可以达到全局指标的水平[7]；另外，我们还指出在链路预测中弱链接可能扮演着比强链接更重要的角色[8]，从而有望逐步推动形成信息挖掘中的弱链接理论。(5)我们指出下一代的信息推荐系统将不再是中心管理系统执行的推荐系统，而是基于用户朋友关系的分布式的社会推荐系统。我们建立了一个简单的模型，并且在该模型上验证了社会推荐机制的有效性[9]。该文已经被L’Atelier报道。

 

我们还在相关问题上发表和接收了其它11篇论文，这里不再一一赘述。另外，在我们已经投稿的文章中，也包含较大贡献的工作。例如在[21]中，我们对大量表达为二部分图的推荐系统进行了实证分析。特别地，我们提出了用于刻画用户和物品选择成团性的协同集聚系数（collaborative clustering coefficient），实证分析揭示了很多有趣的度度相关性和簇度相关性，这些相关性恰到好处地定量解释了以前信息挖掘研究比较困惑的问题：例如为什么对新用户的个性化推荐效果往往很差？什么情况要选择以用户为中心的推荐算法，什么情况要以物品为中心？不同流行程度的物品在信息挖掘中地位一样吗？等等。在文献[22]中，我们详细分析了信息多样性和精确性看似矛盾实际可以调和的关系，并且提出了一种将守恒的物质扩散和不守恒的热传导（含外界恒温热源）结合的混合扩散算法。这个算法可以解决多样性和精确性之间的矛盾。特别地，我们提出了一种框架性观念，通过这种办法，很多系统的表现都能够得到提高。最后，在文献[23]中，我们提出了一种动态算法（针对文献[1]的算法），可以对单条信息的加入进行实时反应。由于所有真实的系统都是处在动态的数据环境中，这方面的研究具有非常重要的实用价值。不同于其他报道的动态算法（针对其他推荐算法），我们提出的算法可以实现误差不累积，也就是说不管这个算法运行多久，算法误差永远很小，也永远都不需要进行全局数据的重新计算。从我们的了解来看，这是第一个真正实现了不累积误差的近似动态算法。

 

加注基金号且已经发表或接收的代表性文献：

[1] T. Zhou, J. Ren, M. Medo, Y.-C. Zhang, Bipartite network projection and personal recommendation, Phys. Rev. E 76 (2007) 046115.

[2] Y.-C. Zhang, M. Medo, J. Ren, T. Zhou, T. Li, F. Yang, Recommendation model based on opinion diffusion, EPL 80 (2007) 68003.

[3] T. Zhou, L.-L. Jiang, R.-Q. Su, Y.-C. Zhang, Effect of initial configuration on network-based recommendation, EPL 81 (2008) 58004.

[4] T. Zhou, R.-Q. Su, R.-R. Liu, L.-L. Jiang, B.-H. Wang, Y.-C.Zhang, Accurate and diverse recommendations via eliminating redundant correlations, New J. Phys. 11 (2009) 123008.

[5] Z.-K. Zhang, T. Zhou, Y.-C. Zhang, Personalized recommendation via integrated diffusion on user-item-tag tripartite graphs, Physica A 389 (2010) 179.

[6] T. Zhou, L. Lü, Y.-C. Zhang, Predicting missing links via local information, Eur. Phys. J. B 71 (2009) 623.

[7] L. Lü, C.-H. Jin, T. Zhou, Similarity index based on local paths for link prediction of complex networks, Phys. Rev. E 80 (2009) 046122.

[8] L. Lü, T. Zhou, Link Prediction in Weighted Networks: The Role of Weak Ties, EPL (accepted).

[9] M. Medo, Y.-C. Zhang, T. Zhou, Adaptive model for recommendation of news, EPL 88 (2009) 38005.

 

加注基金号且已经发表或接收的其它相关文献：

[10] J. Ren, T. Zhou, Y.-C. Zhang, Information filtering via self-consistent refinement, EPL 82 (2008) 58007.

[11] C.-X. Jia, R.-R. Liu, D. Sun, B.-H. Wang, A new weighting method in network-based recommendation, Physica A 387 (2008) 5887.

[12] J.-G. Liu, B.-H. Wang, Q. Guo, Improved collaborative filtering algorithm via information transformation, Int. J. Mod. Phys. C 20 (2009) 285.

[13] R.-R. Liu, C.-X. Jia, T. Zhou, D. Sun, B.-H. Wang, Personal Recommendation via Modified Collaborative Filtering, Physica A 388 (2009) 462-468.

[14] D. Sun, T. Zhou, J.-G. Liu, R.-R. Liu, C.-X. Jia, B.-H. Wang, Information filtering based on transferring similarity, Phys. Rev. E 80 (2009) 017101.

[15] M.-S. Shang, C.-H. Jin, T. Zhou, Y.-C. Zhang, “Collaborative filtering based on multi-channel diffusion”, Physica A 388 (2009) 4867.

[16] M.-S. Shang, L. Lü, W. Zeng, Y.-C. Zhang, T. Zhou, Relevance is more significant than correlation: Information filtering on sparse data, EPL (accepted).

[17] J.-G. Liu, T. Zhou, H-A. Che, B.-H. Wang, Y.-C. Zhang, “Effects of high-order correlations on personalized recommendations for bipartite networks”, Physica A (accepted).

[18] M.-S. Shang, Z.-K. Zhang, T. Zhou, Y.-C. Zhang, “Collaborative filtering with diffusion-based similarity on tripartite graphs”, Physica A (accepted).

[19] J.-G. Liu, T. Zhou, B.-H. Wang, Y.-C. Zhang, Effects of user tastes on personalized recommendation, Int. J. Mod. Phys. C (accepted).

[20] J.-G. Liu, T. Zhou, H.-A. Che, B.-H. Wang, Y.-C. Zhang, Effects of high-order correlations on personalized recommendations for bipartite networks, Physica A (accepted).

 

加注基金号在审稿中的较重要工作：

[21] M.-S. Shang, L. Lü, Y.-C. Zhang, T. Zhou, Empirical analysis of web-based user-object bipartite networks, EPL (under first-round refereeing).

[22] T. Zhou, Z. Kuscsik, J.-G. Liu, M. Medo, J. R. Wakeling, Y.-C. Zhang, Diversity vs. accuracy: solving the apparent dilemma facing recommender systems, PNAS (under second-round refereeing).

[23] C.-H. Jin, J.-G. Liu, Y.-C. Zhang, T. Zhou, Adaptive information filtering for dynamic recommender systems, EPL (under first-round refereeing).

 

----- 感谢贡献者 （字母序）------

Prof. Hong-An Che (上海理工大学)

Prof. Qiang Guo（上海理工大学）

Ms. Chun-Xia Jia (中国科学技术大学) 

Mr. Luo-Luo Jiang (中国科学技术大学)

Dr. Ci-Hang Jin（瑞士弗里堡大学）

Dr. Zoltan Kuscsik（斯洛文尼亚萨法里克大学）

Porf. Tao Li (中国人民大学)

Prof. Jian-Guo Liu（上海理工大学）

Mr. Run-Ran Liu (中国科学技术大学)

Ms. Linyuan Lü（瑞士弗里堡大学）

Dr. Matus Medo（瑞士弗里堡大学）

Mr. Jie Ren (新加坡国立大学)

Prof. Ming-Sheng Shang（电子科技大学）

Mr. Ri-Qi Su (中国科学技术大学)

Mr. Duo Sun (中国科学技术大学)

Prof. Bing-Hong Wang (中国科学技术大学)

Dr. Joseph Wakeling（瑞士弗里堡大学）

Prof. Fan Yang (北京航天航空大学)

Mr. Wei Zeng (电子科技大学)

Prof. Yi-Cheng Zhang（瑞士弗里堡大学）

Mr. Zi-Ke Zhang（瑞士弗里堡大学）