论文部分内容阅读
链路预测在数据挖掘领域又称为链路挖掘,作为近些年研究学者关注的热点。它能够利用网络中己知的信息,预测出在空间上未知的连边或者是在时间上即将产生的连边。由于复杂网络在人类社会和自然界中广泛存在,许多社会、信息、生物系统在人们生活、科研领域内受到广泛关注。并且随着信息时代的到来,社会网络中产生了大量的数据。这些数据在一定程度上反映了人与人之间的社会关系。其中手机是人们使用率与普及率很高的通讯设备。以手机用户为节点,以他们之间通话关系为边构成一个移动通话网络。利用链路预测算法挖掘出在移动通话网络中的连接关系,是本文需要研究的重点。本文的主要目的是在以联通用户和移动用户为节点的网络中,己知联通用户与联通用户之间、联通用户与移动用户之间的通话连接关系后,预测出移动用户之间的通话连接关系。 本文第一部分首先介绍了社会网络的基本概念、网络的表示方法以及网络特性,即社会网络具有小世界效应、聚类效应和无标度性质。社会网络中的链路预测的主要任务,是对网络中缺失的信息以及对未来可能发生的信息进行预测。总结了网络中链路预测的三种方法,分别是基于相似性的链路预测算法、基于似然估计的链路预测算法和基于概率模型的链路预测算法。其中后两种算法的复杂度较高,不适宜大型网络中的预测。 文章第二部分是以移动通话网络为研究对象,在己知联通用户通话记录的情况下,通过信息筛选,以用户为节点、用户之间进行过通话连接为边构建一个加权网络模型。其中边权受用户通话的时长与次数的影响,因而综合考虑设定边权的计算方法。对所建立的移动通话网络的特性进行分析,包括网络中节点的度分布、聚类系数以及平均路径长度等。然后确定本实验采用的链路预测算法,包括共同邻居CN指标、AA指标、资源分配RA指标。并且将另外三种适用于无权无向网络的算法Sorenson、Salton、LHN-I扩展至含权形式。 第三部分是对移动通话网络中链路预测过程的实现。为了达到实验目的,保留下己知的联通用户内部通话数据,并且随机选取一定比例的节点作为“移动用户”,去掉这些“移动用户”之间的连边作为测试集,在这里要排除掉孤立节点产生的干扰。其余的包括“联通用户”与“联通用户”以及“联通用户”与“移动用户”之间的连边集合作为训练集。之后采用基于局部信息的相似性算法,通过这几种算法的预测,利用查全率、查准率、F值评价预测结果的准确性。另外通过对权值设置参数,随着参数变化改变权重对预测效果的影响。通过对指标在无权、加权以及参数变化时预测效果所取得最优值的对比,确定通话网络适用的算法。