基于最大熵模型的微博传播网络中的链路预测

微博是基于用户关注关系建立的具有媒体特性的实时信息分享社交平台.微博上的信息扩散具有快速性、爆发性和时效性.理解信息的传播机理,预测信息转发行为,对研究微博上舆论的形成、产品的推广等具有重要意义.本文通过解析微博转发记录来研究影响信息转发的因素或特征,把微博信息转发预测问题抽象为链路预测问题,并提出基于最大熵模型的链路预测算法.实例验证的结果表明:1)基于最大熵模型的算法在运行时间上具有明显的优势;2)在预测结果方面,最大熵模型比同类其他算法表现优异;3)当训练集大小和特征数量变化时,基于最大熵模型的预测结果表现稳定.该方法在预测链路时避免了特征之间相互独立的约束,准确率优于其他同类方法,对解决复杂网络中其他类型的预测问题具有借鉴意义.

Link prediction in microblog retweet network based on maximum entropy model

Microblog is a social media platform, based on the follower-followee relationship, that enables users to share real-time information, by which the information propagation is characterized as rapid, explosive, and immediate. The research on the information propagation and retweet prediction is very important for public sentiment analysis and product promotion. A majority of existing works adopt several traditional prediction methods to predict the future information retweet based on the features extracted from existing retweet behaviors, which are hard to reconcile accuracy, complexity, robustness and feature extensiveness. To overcome the above mentioned shortcomings in existing works, we propose in this paper a link prediction algorithm based on maximum entropy model to predict retweet behavior on microblog. In our proposed approach, firstly we abstract the retweet prediction problem to a link prediction problem. Then we analyze the retweet behaviors on microblog and determine the factors influencing the retweet behavior. We extract the features from the retweet behaviors based on these factors in the next step. Now based on these features, the retweet behavior could be predicted by the proposed approach. However, information redundancy and other issues may exist among these features. These issues will cause an increase in computational complexity or a decrease in computational accuracy. To solve the above problems, we selecte the features dominating the retweet behavior with feature selection methods such as Information Gain, IG-CHI. The proposed model requires no further independent assumption in features or intrinsic constraints, and omits the processing in relation to features, which is usually the prerequisite of other prediction methods. We take the Sina Weibo retweet records in a time span from 2009 to 2012 as an example to test the effectiveness and efficiency of our link prediction algorithm. Results show that: 1) the proposed algorithm has incomparable advantages in running time; 2) as for the predicted result, the proposed algorithm is better than other algorithms in performance evaluations; 3) the proposed algorithm runs stably for different sizes of training sets and feature sets; 4) the accuracy of the predicted results remains stable based on the selected features. The proposed approach avoids the independent restriction among features and shows better accuracy than other similar methods, thus it has reference values for resolving other prediction problems in complex networks.