网络中的链路预测是指根据网络的已知边预测可能产生的未知边。预测的方法是基于结点相似性的，即两节点越相似越可能连边。吕琳媛同学总结和提出了21种相似性算法：1）有11种是基于节点的，也就是局部信息的。其中吕琳媛同学提出的Resource Allocation Index和Local Path Index两个指标在其中表现甚好。尤其是后者在有些情况下几乎能够达到和全局算法一样高的精确度，但是相比全局算法具有非常小的计算复杂度。2）有7种是基于全局路径信息的算法。其中吕琳媛同学提出的Local Random Walk和Superposed Random Walk方法具有较高的预测精确度。3）其余3种是比较复杂的算法。该方向已经发表接收期刊论文两篇（PRE+EPJB），会议论文一篇(CIKM 2009)，投稿两篇(EPL*2，一篇已经基本接收)，一篇综述正在撰写。

⑴    T. Zhou, L. Lü, Y.-C. Zhang, Predicting Missing Links via Local Information, Eur. Phys. J. B 71, 623-630 (2009).

本文将11种局部算法应用于6个实际网络的链路预测中，并比较其精确度。结果显示Common Neighbors算法在所有9种基于CN的算法中表现最好，而文章提出的Resource Allocation和Local Path方法比CN表现还好。尤其是后者在有些情况下几乎能够达到和全局算法一样高的精确度，但是相比全局算法具有较小的计算复杂度。

⑵    L. Lü, C.-H. Jin, T. Zhou, Effective and Efficient Similarity Index for Link Prediction of Complex Networks, Phys. Rev. E (Accepted) arXiv: 0905.3558.

本文比较了Common Neighbors，Local Path和Katz index三种相似性算法的预测精确度和计算复杂度。结果显示局部算法CN计算复杂度最低，但是由于信息不充足其精确度也较低。另一方面katz index是全局算法，精确度较高，同时计算复杂度也很高。文章提出的Local Path算法是一个很好的权衡，既可以得到相对较高预测精度又不会有很高的时间复杂度，而这优势在规模较大而且较稀疏的网络中更加明显。特别地，文章设计了一种检测链路预测精确度的网络模型，具有可控的网络密度和噪音强度。

⑶    L. Lü, T. Zhou, Link Prediction in weighted networks: The Role of Weak Ties, EPL (submitted) arXiv:0907.1728 (粗糙的结果发表于CIKM 2009).

本文考察了含权网络的链路预测问题，给出了三种局部算法CN，AA和RA的含权表达式。在对3个实际网络的预测中，我们发现了弱连接效应，即在链路预测的时候应更重视权小的边。对此问题我们又进行了motif分析，发现弱连接效应与网络的拓扑结构相关。

⑷    W.-P. Liu, L. Lü, Link Prediction Based on Local Random Walk, EPL (Submitted).

本文提出了一系列基于局部随机游走的链路预测方法，此方法相比其他基于随机游走的算法即有较高的精确度又有很低的计算复杂度，尤其在稀疏网络中优势明显。

   (5) L. Lü, T. Zhou, Link Prediction in Complex Networks: A Mini-Review

       一个相关方向研究的迷你综述，撰写中。

 

在语言系统中存在两个标度律。一个是文本中词频分布服从Zipf’s Law, 另一个是文本中的不同字的数量随文本长度的变化服从Heaps’ Law。在已有的文献中这两个标度律分别受到了热切的关注，但是很少被一起提及。张子柯与吕琳媛针对这一问题作了极为详细的实证和理论研究。

(1) Z.-K. Zhang, L. Lü, J. G. Liu, T. Zhou, Empirical analysis on a keyword-based semantic system, Eur. Phys. J. B 66,557-561 (2008).

本文实证分析了PNAS的关键词的统计特征以及演化规律。结果显示其关键词的词频分布服从Zipf’s Law，并初步发现了不同关键词的个数与关键词的总个数呈现出Heaps’ Law. 通过考查出现次数最多的关键词的使用衰减情况，我们发现影响因子较高的期刊遵循相似的衰减模式（e指数拟合），而较差的期刊几乎观察不到衰减效应。

 

理论研究部分（此处删去1000字）。

 

主要讨论了不完全信息下产品质量和中间商的作用及影响，包括：

(1) L. Lü, M. Medo, Y.-C. Zhang, D. Challet, Emergence of product differentiation from consumer heterogeneity and asymmetric information, Eur. Phys. J. B 64, 293-300 (2008).

本文研究了市场中存在产品质量差异性的原因。不同的消费者由于掌握着不同程度的市场信息，他们选择产品时的质量识别能力也不同。通过建立一个消费者选择产品的概率模型，我们最终发现，导致市场中不同质量产品共存的原因是信息的不对称性。

(2)    L. Lü, M. Medo, Y.-C. Zhang, The role of a matchmaker in buyer-vendor interactions, Eur. Phys. J. B 71, 565-571 (2009).

本文考查了中间商在市场中的作用。市场中的交易过程可以看成是买卖双方的配对过程。买者或者卖者对所有产品都有一个效用值，即购买或者卖出产品所获得的收益。通过最大化市场总收益我们可以得到相应的配对方式。结果显示中间商的存在可以让市场总收益达到最大。

 

 

近年来,协同标签系统(Collaborative Tagging Systems) 越来越受到学术界和工程界的关注.协同标签(Tag)具有高概括性, 强简洁性等特点, 包含了大量的用户个性化信息.并且Tag的使用情况从一定程度上能反映了用户对于其收藏品的的重视和喜爱程度, 从这一基本思想出发, 张子柯设计了几个利用Tag的信息来进行用户推荐的算法. 包括三部图中分别以Item和User为中心的推荐方法, 以及利用用户对Tag的使用频率等信息来构造含权的二部图,并将之应用到推荐系统中去. 实验结果证明, 合理利用用户个性化Tag信息,能够很大程度上提高推荐算法的精确度,多样性和新鲜性。在这个研究方向上,张子柯已经发表和基本接收的文章包括:

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

本文将Tag信息引入推荐系统中, 并设计了以item-based为基础的三部图中的物质扩散算法. 实验结果证明, Tag信息的使用能够极大程度上提高推荐算法的精确度,多样性和新鲜性.是弗里堡组内第一次在该研究方向的尝试.

    (2) M.-S. Shang, Z.-K. Zhang, Diffusion-Based Recommendation in collaborative Tagging Systems. Chin. Phys. Lett. 26 (2009) 118903.

用户使用Tag的频繁程度,很大程度上隐含了用户对物品的喜爱程度. 本文通过将用户使用tag的频率作为加权信息. 构建了含权的二部图网络. 并在此基础之上考察其对推荐算法的性能是否有提高作用. 实验结果证明, 含权的二部图网络能够极大程度上提高推荐算法的精确度.

    (3) M.-S. Shang, Z.-K. Zhang, T. Zhou, Y.-C. Zhang, Collaborative filtering with diffusion-based similarity on tripartite graphs, arXiv: 0906:5017, Physica A (revised version submitted)

本文设计了以user-based为基础的三部图中的物质扩散算法，并嵌入到标准的协同过滤框架中. 实验结果证明, Tag信息的使用能够极大程度上提高推荐算法的精确度。文章结果较[Physica A 389 (2010) 179]有明显提高。