大规模社交网络中二元关系预测方法研究

摘要

大规模社交网络中的二元关系预测问题是指通过已知的网络结构信息预测网络中已存在边的二元关系问题,该问题对于研究网络完整的结构和挖掘网络隐藏的相关信息都具有很重要的意义。目前预测效果最好的方法是 Jure等人提出了的使用LR模型的方法,LR模型是一种线性回归方法,不能很好的拟合大量的、复杂的社会关系,因此本文在此基础上提出了使用支持向量SVM模型来解决普通的社交网络中的二元关系。
　　针对于普通的社交网络,本文主要在3个方面上进行了改进:第一,Jure等人虽然选取了23种特征描述网络,但通过分析发现在这23种特征中,存在一些线性相关的特征,这样的特征对于预测没有意义,但却会耗费时间以及空间,因此,本文通过特征选择的方法(PCA方法)进行特征选择。本文首先提出了10种新的特征,综合Jure等人的23种特征,一共33种特征,然后使用PCA对这33种特征中的11种特征进行了降维处理,选出影响力大的主成分,再对网络中的二元关系进行预测;第二,Jure等人使用LR的模型适合处理线性分类,而社交网络中的关系不是线性可分的,因此本文提出使用SVM模型进行分类,支持向量SVM支持非线性的分类;第三,使用Adaboost算法对已有的算法进行集成,将多个单独的算法作为弱分类器,使用Adaboost集成为一个强分类器,提高了预测的准确率。
　　以上三个改进是针对于普通的社交网络中的二元关系预测问题的改进,而针对于大规模社交网络难以使用单一的模型进行预测的问题,本文提出了将一个大规模的网络划分为几个小的网络,然后对每一个子网络单独建立各自的SVM模型,取得了较好的预测结果。本文提出了两种划分网络的方法,第一种方法是根据边的EM值,即边的嵌入度来划分网络,第二种方法是使用K-means聚类方法将整个网络聚为 K类。通过这两种分类方法将一个大规模的社交网络划分为几个小的子网络,然后对每一个子网络建立各自的SVM模型。
　　该算法在Epinions, Slashdot以及Wikipedia三个数据集上进行了测试,在隐藏10％的边的条件下,slashdot中准确率从84.9％提升到了88.37％,在Epinions中准确率从92.62％提升到了94.31％,Wikipedia中准确率从70.16％提升到了75.65％。
　　通过实验可以看出,使用SVM模型优于使用Logistic Regression模型,并且通过划分子网络的方法不但能够解决大规模社交网络中的二元关系预测问题,还能提高预测的准确率。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 研究工作的背景与意义

1.2 国内外研究历史与现状

1.3 本文主要研究内容

1.4 本论文的结构安排

第二章 相关技术概述

2.1 算法流程

2.2 结构平衡理论与社会地位平衡理论

2.2 PCA算法

2.3 SVM模型

2.4 Adaboost集成算法

2.5 K-means聚类算法

2.6本章小结

第三章 基于SVM模型的预测方法

3.1 二元关系网络中的特征

3.2 基于PCA的特征选择

3.3 基于SVM模型的二元关系预测

3.4 实验结果

3.5 本章小结

第四章 基于Adaboost集成算法的二元关系预测

4.1 启发式算法

4.2 二元关系预测问题中的Adaboost算法

4.3 实验结果

4.4 本章小结

第五章 大规模社交网络中的二元关系预测

5.1 基于K-means算法的多分类SVM模型

5.2 基于EM值的多分类SVM模型

5.3 实验结果

5.4 本章小结

第六章 全文总结与展望

6.1 全文总结

6.2 后续工作展望

致谢

参考文献

攻读硕士学位期间取得的成果