说明：网络信息挖掘，或称图挖掘，是数学中的图论、物理中的统计力学和计算机科学中的离散数学与算法等方向共同感兴趣的一个研究领域，致力于从网络中挖掘有重要价值的信息，狭义而言可以看作数据挖掘面对网络对象的一个分支！我最近受汪秉宏老师和《科技成果管理与研究》杂志社要求，简要总结近年来在网络信息挖掘方面的相关工作。下面主要分为识别网络中起关键作用的节点，预测网络中缺失的链路和向用户进行个性化推荐三个方面进行介绍。

第一部分链接：

http://blog.sciencenet.cn/home.php?mod=space&uid=3075&do=blog&id=1102268     

第二部分链接：

http://blog.sciencenet.cn/home.php?mod=space&uid=3075&do=blog&id=1102641  

第三部分：推荐系统

互联网技术的迅猛发展把我们带进了信息爆炸的时代。海量信息的同时呈现，一方面使用户很难从中发现自己感兴趣的部分，另一方面也使得大量少人问津的信息成为网络中的“暗信息”，无法被一般用户获取。推荐系统通过建立用户与产品（可以是实体商品，也可以是新闻、书籍、电影、歌曲等信息产品）之间的二元关系，利用用户已有的浏览、收藏、转发、点赞、评论、购买等等行为，或者用户自身的属性和产品的特征，挖掘每个用户潜在感兴趣的对象，进而进行个性化推荐[32,33]。我们在这方面的工作可以粗糙地分成以下四个方面。

一是设计了一系列具有普适性的个性化推荐算法。这方面的工作又大体可以分为基于扩散动力学的算法，对经典协同过滤算法中相似性指标的优化，基于迭代寻优的自洽算法和利用了内容信息（标签）的算法。

我们考虑推荐系统最简单的形式，就是一个二部分图，有两类节点，分别是用户和商品——如果一个用户购买过某件商品，就建立一条连边。用户和商品的其他信息都不考虑在内。推荐系统要做的事情，就是根据用户以前的购买记录（也就是这张二部分图），在用户没有买过的东西里面，为用户挑选他所喜欢的，然后推荐给他。扩散算法的思想就是在该二部分图上，假设目标用户自身或其购买过的商品上附着了某种兴趣量（可以看成物质、能量或者热量等等），然后通过模拟物质扩散、热传导或者更复杂的扩散动力学，看这种兴趣量会不会转移汇聚到某些目标用户没有购买过的商品上——这些商品就可以推荐给目标用户。我们最早针对二元推荐系统[34]（只考虑购买与否）和打分推荐系统[35]（用户给所购买的商品或者浏览观看的信息产品打分，因此每一条连边上有一个分数），设计了总量守恒的扩散动力学，获得了好于经典协同过滤算法的推荐精度。在最简单的守恒的局部扩散算法[34]基础上，我们考虑了一系列进一步提高算法精度的方法，包括适当降低流行商品的影响力[36]、去除同一喜好重复记入带来的偏差[37]、将打分系统中离散分值看成各自独立的不同传播渠道[38]、根据用户购买活跃度设计不同的扩散强度[39]、将节点度作为考虑因素引入热传导过程中[40]、把商品和用户交换位置同时考虑双向的匹配[41,42]，等等。

传统的协同过滤算法的基本思想是将与目标用户选择相似性度较高的用户喜欢的商品推荐给目标用户。这里面相似性的度量起到了关键的作用：一方面要基于相似性大小选择出一批最相似的用户作为参考，另一方面相似性大小本身在推荐中起到权重的作用。我们在传统的余弦相似性中把节点度作为一个参数引入，提出了改进后的相似性指标，对应的推荐精度也可以得到提升[43]。我们还提出了一种新的名为“转移相似性”的全局相似性指标，其基本思想是如果节点A和B相似，B和C相似，那么可以有部分相似性能从A通过B转移到C。基于这种和PageRank等类似的思路，我们得到了一个自洽的相似性指标，基于此，可以获得显著好于余弦相似性的预测精度[44]。介于局部和全局之间，考虑用户之间的高阶相似性，也可以提高协同过滤的精确度[45]。最近，我们找到了一种完美结合余弦相似性指标和资源分配指数的新的不含参数的局部相似性指标[46]，该指标对应于非常高的推荐精确性，在目前已知的局部指标中独树一帜！

迭代寻优是一种重要的算法思想。如果只考虑用户-商品二部分图，则整个推荐系统的信息可以用对应的邻接矩阵A表示。在很多情况下，推荐算法都可以看成是一个作用在A上的算子R，R(A)就是算法的结果。这个算子可以很简单（例如传统的协同过滤或者扩散动力学方法），也可以很复杂（例如SVD及其变体）。我们把A中取值为1的元素看成不能变化的边界条件（已知条件），令A1是把R(A)中所有边界条件还原后的矩阵（在R(A)中令原来A中为1的元素依然为1，其他元素不变）。类似地，我们令A2是把R(A1) 中所有边界条件还原后的矩阵（在R(A1)中令原来A中为1的元素依然为1，其他元素不变）。这样得到A1、A2、A3……最后收敛。这个收敛的结果就是自洽的结果。给定A和一个算子R，一般而言都能得到一个自洽的结果，我们用这个结果来做推荐[47]。实验显示，这种算法的效果要明显好于非自洽的算法。

上面讨论的情况都是把推荐系统抽象成二部分图，只涉及用户-商品之间的关系。如果商品还可以用一系列标签描述（这是最简单的内容描述），那么就可以建立一个用户-商品-标签的三部分图，在这个三部分图上利用扩散动力学[48]或者变体的协同过滤[49]来进行推荐，其推荐精确度都会显著高于没有标签信息的情况。我们有一篇短综述总结了利用标签信息进行个性化推荐的前沿进展[50]。

二是尝试推动解决一些推荐系统研究中长期存在的挑战，包括推荐的多样性问题、冷启动问题、社会推荐问题和脆弱性问题。

如果要给用户推荐他喜欢的商品，最“保险”的方式就是给他特别流行的商品，因为这些商品有更大的可能性被喜欢（否则也不会那么流行）。但是，这样的推荐产生的用户体验并不一定好，因为用户很可能已经知道这些热销流行的产品，所以得到的信息量很少，并且用户不会认同这是一种“个性化的”推荐。在不降低精确性甚至提高精确性的前提下提升推荐的多样性，是一个困难的挑战。我们给出了一系列度量推荐算法多样性和新颖性的指标[36,37]，并通过精巧混合能量扩散和热传导算法，实现了同时提升推荐效果的精确性、多样性和新颖性[51]。

新用户因为罕有可以利用的行为信息，很难给出精确的推荐。反过来，新商品由于被选择次数很少，也难以找到合适的办法推荐给用户——这就是所谓的冷启动问题。标签系统的广泛应用提供了解决冷启动问题的可能方案[52]。因为标签既可以看作是商品内容的萃取，同时也反映了用户的个性化喜好——譬如对《桃姐》这部电影，有的人打上标签“伦理”，有的人打上标签“刘德华”，两个人看的电影一样，但是兴趣点可能不尽相同。除去利用外在的标签信息，我们也设计了若干有倾向性的算法[53,54]，这些算法从整体上对于推荐的精确度提升并不明显，但是能够显著提高较新的用户和较不流行的商品推荐的精准度。

很早以前，研究人员就注意到，用户更喜欢来自朋友的推荐而不是被系统“算出来的推荐”，因此很多人认为社会影响力比历史行为的相似性更加重要。一个容易被发现的现象是来自朋友的社会推荐会增加销售，而我们首次通过大量实证表明来自朋友的推荐还会提升销售后用户的评价[55]。我们建立了社会推荐的一个基础性的理论模型[56]，并对该模型的表现以及在遇到蓄意攻击时的脆弱性进行了深度分析[57]。以此模型为依据，我们探索了如何建立更好的机制以促进社会推荐[58,59]。

受推荐系统在电子商务领域重大的经济利益的驱动，一些心怀不轨的用户通过提供一些虚假恶意的行为，故意增加或者压制某些商品被推荐的可能性。除了生成虚假用户进行有针对性的虚假打分外，攻击者还通过将攻击对象和热销商品或特定用户群喜欢的商品绑定而提高攻击效果，甚至通过持续探测猜测系统的计算相似性的算法，从而有针对性地开展攻击。我们提出了通过迭代寻优的办法给不同用户不同信誉分的办法[60,61]。试验显示，常见的攻击方法中恶意攻击者的信誉分会非常低，从而在以信誉分为权重的推荐算法中影响微弱。

三是对推荐系统本身的结构和演化，以及推荐算法进行了深入的分析。

我们分析了用户-商品二部分图的结构特征[62,63]，特别是如何精确刻画用户和商品分别的度分布，以及两者之间的度度关联特性——事实上，这个特性也可以被利用来提高推荐的精确度[63]。我们还反过来看推荐算法本身是否会影响网络结构的演化。我们分析了若干类似Twitter和新浪微博的社交网络，发现用户粉丝数目的分布都是幂律的，特别地，我们提出了一个新的机制——社会推荐——来解释这种幂律分布的起源[64]。

在对若干有代表性的推荐算法进行深入分析的过程中，我们注意到如果数据密度足够高，那么给一个商品打低分是一个负面信号，但如果数据密读非常低，那么这些负面的投票都可以看成正面的信号——尽管用户恶评一部电影，但至少说明用户对这类电影感兴趣。所以，在数据密读非常低的情况下，两个用户只要同时评价了一些商品，不管打分多少，都可以看成是相似的——在经典的协同过滤框架下，这时候去掉打分信息（处理成二元信号）[65]或者把打分不相似的用户（甲喜欢的乙讨厌）处理成相似用户进入推荐中[66]，反而推荐精度更高。事实上，在数据足够稀疏的情况下，负面投票都可以起到正面正面的作用[67]。

所谓锚定效应是指当人们需要对某个事件做定量估测时，会将某些特定数值作为起始值，起始值像锚一样制约着估测值。在做决策的时候，会不自觉地给予最初获得的信息过多的重视。许多研究从不同角度证明锚定效应是一种普遍存在的、十分活跃又难以消除的判断偏差。

我们分析了网络在线评价系统WikiLens和MovieLens上的用户打分（用户通过1-5分给系统中的对象打分）。我们首先观察一些特殊的对象——平均得分高于4.5分或者低于2.0分的对象（这样的对象在所有对象中占比不到1%），发现在高分对象后面的打分普遍高，而在低分对象后面的打分普遍也低。这个差异非常明显，在MovieLens中两个均值分别是4.16和2.72，而在WikiLens中两个均值分别是4.13和2.63。进一步地，我们采用了多种去除均值偏移的办法来把一个用户的打分分成两类——相比而言偏高的打分和相比而言偏低的打分。我们发现，偏高的打分和偏低的打分出现具有明显的记忆性，也就是说偏高分和偏低分倾向于集中一起出现。通过和随机化后的系统做对比，这种统计具有显著性！去掉锚定误差后，推荐的精度会得到提升[68]。

在推荐系统研究中有一种著名算法叫做top-k协同过滤，就是说不要考虑目标用户和所有用户的相似性并做加权，只考虑最相似的k个，这样效果反而更好。主成分分析等等都有类似的观点，因为很弱的那些关联，基本上可以看成噪音。我们大胆推广，认为去掉一些信息，推荐算法的精确性可能也能保持，甚至提高。我们提出了相应的算法萃取网络中的信息核，并且只用这部分数据做推荐。我们发现，信息核在只包含20%的用户时，有的时候比用所有信息得到的推荐精确度还要高。最差的情况下，也能达到91.4%的精确性[69]。

因为节点相似性在推荐算法甚至各种网络信息挖掘算法中都扮演重要角色，我们最近分析了相似性指标的稳定性。我们认为，一个指标如果要好，必然有相当的稳定性。举个例子，如果给定一个网络G，我把它所有边随机分成两个部分A1和A2，分别用这两个部分计算节点对的相似性。那么一个好的指标，虽然用的信息变少了，针对A1和A2计算出来的相似性排序应该有很大的相关性。我们针对15种相似性指标，在大量的人造网络和真实网络中作了实验，发现相似性的指标稳定性有很大差异，而常见的共同邻居相似性，Adamic-Adar相似性和资源分配相似性稳定性很好。特别地，我们用这些方法作了个性化推荐的实验，发现用稳定性好的相似性指标，效果很好；反过来用稳定性差的相似性指标，效果不佳，会给出很多不正确的推荐[70]。

最后，我们还针对若干复杂场景开展了应用研究，包括为大量电子商务企业建设推荐系统，并利用用户在其他电子商务网站的行为提高目标电子商务网站推荐的效果[71]。我们还将经典的推荐算法推广到地点推荐等复杂场景中[72-74]。

参考文献：

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

[33] Lü, L., Medo, M., Yeung, C. H., Zhang, Y. C., Zhang, Z. K., & Zhou, T. (2012). Recommender systems. Physics Reports, 519(1), 1-49.

[34] Zhou, T., Ren, J., Medo, M., & Zhang, Y. C. (2007). Bipartite network projection and personal recommendation. Physical Review E, 76(4), 046115.

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

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

[37] Zhou, T., Su, R. Q., Liu, R. R., Jiang, L. L., Wang, B. H., & Zhang, Y. C. (2009). Accurate and diverse recommendations via eliminating redundant correlations. New Journal of Physics, 11(12), 123008.

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

[39] Liu, J. G., Zhou, T., Wang, B. H., Zhang, Y. C., & Guo, Q. (2009). Effects of user's tastes on personalized recommendation. International Journal of Modern Physics C, 20(12), 1925-1932.

[40] Liu, J. G., Zhou, T., & Guo, Q. (2011). Information filtering via biased heat conduction. Physical Review E, 84(3), 037101.

[41] Nie, D. C., An, Y. H., Dong, Q., Fu, Y., & Zhou, T. (2015). Information filtering via balanced diffusion on bipartite networks. Physica A, 421, 44-53.

[42] Zhu, X., Tian, H., Zhang, P., Hu, Z., & Zhou, T. (2015). Personalized recommendation based on unbiased consistence. EPL (Europhysics Letters), 111(4), 48007.

[43] Liu, R. R., Jia, C. X., Zhou, T., Sun, D., & Wang, B. H. (2009). Personal recommendation via modified collaborative filtering. Physica A, 388(4), 462-468.

[44] Sun, D., Zhou, T., Liu, J. G., Liu, R. R., Jia, C. X., & Wang, B. H. (2009). Information filtering based on transferring similarity. Physical Review E, 80(1), 017101.

[45] Liu, J. G., Zhou, T., Che, H. A., Wang, B. H., & Zhang, Y. C. (2010). Effects of high-order correlations on personalized recommendations for bipartite networks. Physica A, 389(4), 881-886.

[46] Chen, L. J., Zhang, Z. K., Liu, J. H., Gao, J., & Zhou, T. (2017). A vertex similarity index for better personalized recommendation. Physica A, 466, 607-615.

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

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

[49] Shang, M. S., Zhang, Z. K., Zhou, T., & Zhang, Y. C. (2010). Collaborative filtering with diffusion-based similarity on tripartite graphs. Physica A, 389(6), 1259-1264.

[50] Zhang, Z. K., Zhou, T., & Zhang, Y. C. (2011). Tag-aware recommender systems: a state-of-the-art survey. Journal of Computer Science and Technology, 26(5), 767.

[51] Zhou, T., Kuscsik, Z., Liu, J. G., Medo, M., Wakeling, J. R., & Zhang, Y. C. (2010). Solving the apparent diversity-accuracy dilemma of recommender systems. PNAS, 107(10), 4511-4515.

[52] Zhang, Z. K., Liu, C., Zhang, Y. C., & Zhou, T. (2010). Solving the cold-start problem in recommender systems with social tags. EPL (Europhysics Letters), 92(2), 28002.

[53] Qiu, T., Chen, G., Zhang, Z. K., & Zhou, T. (2011). An item-oriented recommendation algorithm on cold-start problem. EPL (Europhysics Letters), 95(5), 58003.

[54] Liu, J. H., Zhou, T., Zhang, Z. K., Yang, Z., Liu, C., & Li, W. M. (2014). Promoting cold-start items in recommender systems. PLoS ONE, 9(12), e113457.

[55] Huang, J., Cheng, X. Q., Shen, H. W., Zhou, T., & Jin, X. (2012, February). Exploring social influence via posterior effect of word-of-mouth recommendations. In Proceedings of the fifth ACM international conference on Web search and data mining, ACM Press, pp. 573-582.

[56] Medo, M., Zhang, Y. C., & Zhou, T. (2009). Adaptive model for recommendation of news. EPL (Europhysics Letters), 88(3), 38005.

[57] Cimini, G., Medo, M., Zhou, T., Wei, D., & Zhang, Y. C. (2011). Heterogeneity, quality, and reputation in an adaptive recommendation model. The European Physical Journal B, 80(2), 201-208.

[58] Wei, D., Zhou, T., Cimini, G., Wu, P., Liu, W., & Zhang, Y. C. (2011). Effective mechanism for social recommendation of news. Physica A, 390(11), 2117-2126.

[59] Cimini, G., Chen, D., Medo, M., Lü, L., Zhang, Y. C., & Zhou, T. (2012). Enhancing topology adaptation in information-sharing social networks. Physical Review E, 85(4), 046108.

[60] Zhou, Y. B., Lei, T., & Zhou, T. (2011). A robust ranking algorithm to spamming. EPL (Europhysics Letters), 94(4), 48002.

[61] Gao, J., & Zhou, T. (2017). Evaluating user reputation in online rating systems via an iterative group-based ranking method. Physica A, 473, 546-560.

[62] Shang, M. S., Lü, L., Zhang, Y. C., & Zhou, T. (2010). Empirical analysis of web-based user-object bipartite networks. EPL (Europhysics Letters), 90(4), 48006.

[63] Liu, J. G., Zhou, T., Wang, B. H., Zhang, Y. C., & Guo, Q. (2010). Degree correlation of bipartite network on personalized recommendation. International Journal of Modern Physics C, 21(01), 137-147.

[64] Zhou, T., Medo, M., Cimini, G., Zhang, Z. K., & Zhang, Y. C. (2011). Emergence of scale-free leadership structure in social recommender systems. PLoS ONE, 6(7), e20648.

[65] Shang, M. S., Lü, L., Zeng, W., Zhang, Y. C., & Zhou, T. (2010). Relevance is more significant than correlation: Information filtering on sparse data. EPL (Europhysics Letters), 88(6), 68008.

[66] Zeng, W., Shang, M. S., Zhang, Q. M., Lü, L., & Zhou, T. (2010). Can dissimilar users contribute to accuracy and diversity of personalized recommendation?. International Journal of Modern Physics C, 21(10), 1217-1227.

[67] Zeng, W., Zhu, Y. X., Lü, L., & Zhou, T. (2011). Negative ratings play a positive role in information filtering. Physica A, 390(23-24), 4486-4493.

[68] Yang, Z., Zhang, Z. K., & Zhou, T. (2012). Anchoring bias in online voting. EPL (Europhysics Letters), 100(6), 68002.

[69] Zeng, W., Zeng, A., Liu, H., Shang, M. S., & Zhou, T. (2014). Uncovering the information core in recommender systems. Scientific Reports, 4, 6140.

[70] Liu, J. G., Hou, L., Pan, X., Guo, Q., & Zhou, T. (2016). Stability of similarity measurements for bipartite networks. Scientific Reports, 6, 18653.

[71] 张亮, 柏林森, & 周涛. (2013). 基于跨电商行为的交叉推荐算法. 电子科技大学学报, 154-160.

[72] Lian, D., Xie, X., Zhang, F., Yuan, N. J., Zhou, T., Rui, Y., & Data, B. (2015). Mining Location-based Social Networks: A Predictive Perspective. IEEE Data Eng. Bull., 38(2), 35-46.

[73] Lian, D., Ge, Y., Zhang, F., Yuan, N. J., Xie, X., Zhou, T., & Rui, Y. (2015). Content-aware collaborative filtering for location recommendation based on human mobility data. In IEEE International Conference on Data Mining (ICDM'2015), IEEE Press, pp. 261-270.

[74] Lian, D., Ge, Y., Zhang, F., Yuan, N. J., Xie, X., Zhou, T., & Rui, Y. (2018). Scalable Content-Aware Collaborative Filtering for Location Recommendation. IEEE Transactions on Knowledge and Data Engineering (in press).