论文研究-基于多维属性的社会网络链接预测算法MDA-TF.pdf

所需积分/C币:10 2019-07-22 21:42:07 941KB .PDF

针对传统社会网络链接预测算法忽视节点多维属性的问题,提出一种基于多维属性的社会网络链接预测算法MDA-TF。该算法首先经过数据预处理,结合节点的多维属性,构建张量模型;然后采用高阶正交迭代算法进行张量分解,得到核心矩阵和因子矩阵;最后根据核心矩阵生成链接预测结果。采用真实的社会网络数据集进行测试取得了较好的实验结果,实验结果也表明了该算法的有效性和正确性。
第2期 仇丽青,等:基于多维属性的社会网络链接预测算法 MDA-TE 419 存在链接,A1=0表示节点i到j之间不存在链接或者是否存 relation四个属性,分别构建了其相应的用户相似度矩阵,如图 在链接未知。链接预测的基本任务是找出A=0的节点对之6所示。 可能存在的链接,为每个可能存在的链接计算出现链接的概 率并进行降序排列,概率值越高则岀现链接的可能性越高。 另外,每个节点并不仅仅包含结构信息,还有多维属性信 acton 息,这些多维属性信息构成一个个矩阵,称之为多维属性矩阵。 例如,对于包含N个节点M维属性的网络,可以构成M个 user 矩阵,对第m个矩阵来说,R代表节点和j在第m个属 性上的链接概率取值。例如针对新浪徼博网络,考虑 topIc、 tag、 action、 relation四维属性,木文可以分别构建G(v,E) Gu(V,E)、Gnmn(V,E)和 Gel(V,E)四个矩阵,分别用于描 述在这四维属性上,节点对之间出现链接的概率。 3.2算法的步骤 图6基于多维属性的张量模型 基于多维属性的社会网络链接预测方法 MDA-TE充分考 3.2.3张量分解得到因子矩阵和核心矩阵 虑节点的多维属性,构建多维属性的张量分解模型,从而预测 恨据张量模型,采用HOOⅠ方法(算法1)进行张量分 解,经过若干次迭代得到了因子矩阵和核心矩阵。核心矩阵可 可能出现的链接,其流程如图2所示。 以看做是对原张量模型的降维处理结果,是原张量模型的 数据顶处理 近似。 构建张星分解模型 3.2.4生成链接预测结果 该算法的最终目的是根据核心矩阵,对节点之同可能出现 张量分解得到风子矩阵和核心矩军 的链接给出个值,值小的节点对之间出现链接的可能性比较 生成链接预測结果 小,值大的节点对之间出现链接的可能性比较大 图2算法流程 3.2.1数据预处理 4实验分析 在社会网络上的数据格式、内容比较复杂,因此需要对原4.1实验数据集 始数据进行预处理。首先构建用户一属性特征值矩阵;然后使 为了进一步验证算法的有效性,本文采用了两个真实的社 用TF-IDF技术为每个用户的属性特征值赋予一定的数值;最 会网络数据集 后恨据传统的余弦相似度公式计算用户相似度。 a)新浪徼博。新浪微博是我国最大的社交网站,通过该 以新浪微博为例,对于pi这样的文本信息属性,首先使网站用户可以与朋友、同事以及其他周围的人保持互动交流。 用切词、过滤等自然话言处理技术构建用户一关键间矩阵,如本文仅使用了共中鄙分数据作为实验数据集。 图3所示;然后使用TFDF技术为每个用户的每个关键词,使 b)安然数据集。安然数据集是一个基于通信的邮件网 用T-DF取值代替其对应的关键词,从而构建出一个基于用络,节点表示用户,链接表示用户之间通过邮件进行通信。 户关键词的TF-IDF矩阵,如终4所示;最后使用余弦相似度公 这两个数据集的网络拓扑性质如表1所示。 式计算用户相似度,得到个基于 topIc属性的用户相似度矩 表1真实社会网络拓扑性质 阵,如图5所示。 网络节点连边凝聚系数平均节点度社区数目模块度 keywordl keyword2 kevword3 keyword keywords 新浪微博7651189240.56110.234 keywords keyword keyword keyword keywords 112720.462 0.259 k k k 4.2评价指标 图3用广一关键词矩阵 链接预测算法性能的评价指标主要有两个:AUC( area un der the receiver operating characteristic curve)和Pec@1度量。 keyword2 keyword k a)AUC度量。每次从测试数据集合中随札选取一组有链 user TF TF-IDF TE-IDI TF-IDF TF-IDF TF-IDF TF-IDE TE-IDI TE-IDE 接的节点对和无链接的节点对,然后计算节点对得分进行比 图4基于用户关键词的TF-DF矩阵 较,在n次比较中有n1次有链接节点对得分大于无链接节点 对,n2次得分相同,则AUC的值为 value AuC_1 +n2 user2 USCl valuc valuc b)Prec@L度量。对测试数据集合中的节点相似度取值 图5基于 topic属性的用厂相似度矩阵 从大到小排列,排在前L位的所对应的链接有m个在测试集 合屮 3.2.2构建张量分解模型 在数据预处理阶段,木文可以对节点的每个属性建立相应 Prec(al-m (3) L 的用户相似度矩阵。这些相似度矩阵就形成张量,从而构建出 这两种评价指标的侧重点不一样,以AUC最为常用。这 张量分解模型。以新浪微博数据为例,对于υopic、ag、 ac LIOr、两种度量方法的结果倌越大,代表链接预测算法效果越好。 420 计算机应用研究 第35卷 4.3实验结果与分析 验证明,参数R取值过大或过小都不理想。取值过小,核心张 遁取经典链接预测算法CN( common neighbors)、AA 量过大,降维效果不好;取值过大,核心张量过小.会失去过多 (Admi/dx)作为比对算法,分别按照AC和PrlL两种的能够表现节点特征的属性。经过本文实验,R=10时实验 度量方法进行评价,实验分别进行10、20、30次,取其中的最好结果比较好,实验结果如图8所示。 平均值作为最终结果。对参数R(算法1的输入参数),根据 0.88 0.86 网络的大小,在新浪微博数据集中取R=1000,在安然数据集 0.84 中取R=100。在后面,本文会具体分析参数的选取对实验产 0.82 生的影响。表2是对新浪微博数据的实验结果。 0.78 表2新浪微博数据集的链接预测 算法 AUC Prec@≤0 0.74 50100 l50 00 50 0.6544 0.2406 0.3485 0.7038 0.4327 0.5100 图8参数R取值和预测结果之间的关系 MDA-TE 0.8200 表3安然数据集的链接预测 5结束语 AUC 0.7201 0.3281 0.3890 首先分析了单纯依靠社会网络的结构特征或者单一节点 0.7842 0.5619 0.5895 属性特征,进行社会网络链接预测的弊端。为了更好地将被忽 MDA-TF 0.8729 0.6531 0.7017 视的多维属性数据结合到传统的链接预测算法,本文提出了基 从实验结果可以看出 于多维属性的社会网络链接预测算法MDA-I},通过综合分析 a)在安然数据集上的链接预测结果要明显好于在新浪微节点的多维属性信息以及网络结构特征,在张量分解模型中结 博上的链接预测结果。这是因为新浪微博数据集数据量比较合多维属性信息,构建链接预测模型对社会网络进行有效的链 大,复杂度比较高,而安然数据集数据量相对较小,复杂度比接预测,提出了基士多维属性的社会网络链接预测算法MDA 较小 l。最后在两个真实的社会网络数据集上进行了验证,相对 b)无论是新浪微博数据集还是安然数据集,本文提出的于传统算法而言,取得了很好的预测结果。 基于多维属性的社会网络链接预测算法 MDA-TF,在AUC或 由于张量分解时运行复杂度比较高,还存在定的局限 者是Prec@L上,都取得了最好的结果。分析原因是,MDA性。所以,下步的作将进研究张量分解与并行、大数 算法采用了张量分解技术,综合考虑了节点的多维度属性,从据处等技术的融合,以降低其运行复杂度。 而使得链接预测结果更为准确。 参考文献 另外,木文分析了10次ALC取值的标准差,结果如图7 所示。 [1 Narang K, Lerman K, Kumaraguru P Network flows and the link pre- diction problem[C//Proc of the 7th Workshop on Social Network 0.45 新浪 Mining anrl Aralysis 2013: 1-8 ■安然 [2 Newman M E J. Clustering and preferential attachment in growing net works [J]. Physical Review E, 2001, 64(2): 251021-251024 [31 Carmi S, Havlin S, Kirkpatrick S, et al. A model of internet topo using k-shell decomposition[ J]. Proc of the National Acader Sciences,2007,104(27):l1150-11154 0.05 I 4 Murata T, Moriyasu S Link prediction of social networks based on weighted proximity measures[ C_//Pmc of IEFE/WIC/ACM Interna 图7AUC标准差 tional Conference on Web Intelligence. 2007: 86-88 从图7可以看出: [5]朱玄格.基于海量数据的社会网络链接预测分析[D].合肥:屮国 a)MDA-TF算法结果的稳定性要强于两个比对算法CN 科学抆术大学,2014. 和AA。分析原因是 MDA-TF采用张量分解技术,降维后得到[61 Hasan A L, Chaoyi M, Salem V S. Link prediction using supervised 的张量能够在很大程度上逼近原始张量,取得了较好的降维效 learning. C//Proc of SDM Workshop on Link Analysis, Counterter 果,因此使得结果相对平均值而言,浮动较小。 rorism and Security 2006: 798-805 b)MDA-TF算法在新浪徼博上的AUC标准差比较大,每[7]LyuL,inCH, Zhou t. Similarity index based on local paths for link 次执行结果与平均值差距较大;在安然网络数据集上的AUC prediction of complex networks[ J]. Physical Review E Statistical 标准差比较小,每次执行结果与平均值差距较大。分析原因 Nonlinear Soft Matter Physics, 2009, 80(4): 046122 是,新浪微博数据集的数据量、复杂性要远远大于安然数据集, 8 Yin Zhijun, Gupta M, Weninger T, et al. A unified framework for link 从而造成了结果的不稳定性。 recommendation using random walks[C]//Proc of IEEE/ACM Inter 4.4参数R的诜取 rational Conference un Advances in Social Nel works Analysis and 参数R作为 MDA-TF算法的输入参数,决定了核心张量[9 Yin Xusen, Wu Bin, Lin xiumin, A unified framework for predicting 的大小和降维的程度,因此在很大程度上影响实验结果。木文 attributes and links in social networks[C// Proc of the IEEE Inter- 在安然数据集上比较了參数R的选择对实验结果的影响。实 national Conference on Big Data. 2013: 153-160

...展开详情
试读 4P 论文研究-基于多维属性的社会网络链接预测算法MDA-TF.pdf
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于多维属性的社会网络链接预测算法MDA-TF.pdf 10积分/C币 立即下载
    1/4
    论文研究-基于多维属性的社会网络链接预测算法MDA-TF.pdf第1页
    论文研究-基于多维属性的社会网络链接预测算法MDA-TF.pdf第2页

    试读已结束,剩余2页未读...

    10积分/C币 立即下载 >