免费论文查重: 大雅 万方 维普 turnitin paperpass

试述树状基于树状朴素贝叶斯模型社会网络联系预测

最后更新时间:2024-01-31 作者:用户投稿原创标记本站原创 点赞:27830 浏览:123511
论文导读:
摘要:
在社会网络关系预测研究领域,把基于拓扑结构信息的共邻节点属性作为相似性度量的预测模型应用比较广泛,但是该类算法具有较强的假设独立性,不能完全反映社会网络的“链接”结构。引入树状朴素贝叶斯(TAN)分类模型,采用信息熵度量节点对的角色,赋予共邻节点集合差异化的贡献权重进行社会关系预测,同时把模型推广到CN,AA和RA 等3种基于相似度的链接预测算法中。对5个真实社会网络采用AUC和ROC曲线进行实验评价后证明,该模型能够在深入挖掘共邻节点对贡献及解决共邻节点角色独立性的基础上提高预测精确度,同时为该类模型的研究提供一种新的方案。
关键词:
社会网络分析;关系预测;链接预测;共邻节点;贝叶斯模型
0引言
社会网络分析是数据挖掘和机器学习领域其中一个非常活跃的研究课题,也是众多知名的互联网公司例如Facebook、Twitter、YouTube的主要业务方向。它主要通过学习社会网络中用户属性及其相互间活动关系,挖掘其中内在的知识规律并提供推广和推荐服务,例如展示用户之间 “潜在好友”的关联推荐,对用户感兴趣新闻的推荐,发现社会关系中的社区属性,把具备相似兴趣的用户归纳为特定群组和判断微博和博客中的谣言传播等[3]。
在社会网络分析领域,关系可以用网络或者图的结构[4]摘自:毕业论文的格式www.7ctime.com
来表示,其中节点(顶点)表示一个用户,链接(边)表示两个用户之间的关系,如何根据社会网络的历史结构信息预测其演化方式及其用户之间社会关系发生的潜在可能便显得异常重要,这也是本文的研究领域——社会关系预测(后称关系预测)所要解决的基本问题。
1相关工作
目前,大部分关系预测模型都是基于社会网络的拓扑特征结构建立,其中基于共同邻接(Common Neighbor, CN)节点——简称共邻节点,特征计算节点对之间的相似度[5] (Similarity)应用最为广泛。在基于相似度的关系预测模型中,相似度表示两个节点(后称节点对)结构属性的相似性产生关系可能性,相似性越大,它们之间存在关系的可能性就越大。LibenNowell等[5]总结了基于网络拓扑结构的相似性定义方法,将这些指标分为基于共邻节点和基于路径的两类,并分析了若干指标[5]的相互作用及其预测效果。目前,基于共邻节点相似度的预测模型有了更广阔的研究领域:Soundarajan等[6]和Yan等[7]提出了引入社区发现概念,赋予处于不同社区的共邻节点差分化的贡献权重进行关系预测;Murata等[8]和Lyu等[9]提出了基于关系权重的预测模型,并取得了较好的预测效果。但是,基于共邻节点的相似度算法假设所有节点对预测节点对的贡献权重视为一致,不利于区分具备不同属性共邻节点的角色及其贡献。例如在图1中,(A,B)是预测节点对,C、D、E是三个共邻节点,在图(a)中,三个共邻节点是独立无关系的,而图(b)中则相反,各节点对之间都存在一条关系边。对于经典的CN预测算法,两子图中(A,B)的共邻节点数目均为3,所以其产生关系的可能是一样的。但在真实社会网络中,如果两节点的共同朋友他们之间关系较为紧密,那么其产生关系的可能性更高,所以两图邻节点对(A,B)的影响显然是不一样,故(A,B)在图(b)中产生关系的可能要比在图(a)高。
AdamicAdar(AA)和Resource Allocation(RA)等算法针对以上的问题作出了改进[4],采用共邻节点的度数和度数的对数来差分其角色权重;最近,Liu等[10] 也提出了一种基于朴素贝叶斯模型的节点角色定义算法,但是该类算法具有较强的独立性假设,无法表示两个紧密联系的共邻节点之间的共同贡献。如何找到一种新的度量表示共邻节点之间的内在关系并计算其对预测节点对的贡献尤其重要。由此,本文提出引入TAN(Tree Augmented Ne Bayesians)分类模型表示共邻节点之间的贡献并进行关系预测的模型。
首先给出社会网络的定义,然后介绍基于朴素贝叶斯理论的关系预测框架,引入TAN模型[11]差分化处理不同共邻节点的贡献并挖掘其内在关系,将其推广到其他基于相似度的关系预测算法中,最后采用AUC(Area Under ROC Curve)和ROC论文导读:为独立特征模型,给定一个特征集合E(a1,a2,…,an),其中an是属性特征值,给定特征E下某个分类C的概率可表示为条件概率P(C|E):上一页12
(Receiver Operating Characteristic)曲线对真实网络进行实验评价,验证方法的性能。
综合来说,本文的贡献主要有3点:
1)引入机器学习领域的TAN分类模型改进基于朴素贝叶斯的关系预测中独立性假设这一问题。
2)把基于TAN的关系预测模型推广到其他基于相似度的算法当中。
3)给出了基于真实网络的实验评价和分析。
2本文方法

2.1社会网络定义

定义社会网络的无向图,V和EV×V分别为模型中节点和链接的集合,R定义为网络中的关系,节点u,v∈V形成的链接e∈E被认为是R上定义的一个关系,其映射函数为:φ:V×V×R→E。其中(x,y)为节点对,Γ(x,y)=Γ(x)∩Γ(y)为节点对的共邻节点集合,其简写记为Γ(x,y)或者Γ。

2.2朴素贝叶斯关系预测模型

朴素贝叶斯分类器是一种应用基于独立假设的贝叶斯定理的简单概率分类器,为了更精确描述这种潜在的概率模型为独立特征模型,给定一个特征集合E(a1,a2,…,an),其中an是属性特征值,给定特征E下某个分类C的概率可表示为条件概率P(C|E):