论文部分内容阅读
随着互联网时代的到来,社交网络已得到了极大的普及，用户通过社交网络可享受各类社交服务，如豆瓣为用户提供图书、电影、音乐分享服务，知乎提供问答服务，微博提供自媒体广播服务，用户为满足不同的服务需求，往往不会局限于单一社交网络中，而是参与到多个社交网络活动之中。因此，跨社交网络用户识别问题逐渐引起了学者的关注，跨社交网络用户识别将有效集成分散于各个网络中的用户资源，大大提高用户推荐、广告投放、用户组形成等以用户为中心的服务质量。
在传统的基于结构的跨社交网络用户识别方法中,现有方法大多通过提出有效的用户相似性函数，以评价用户是否匹配，主要存在以下不足:(1)现有方法大多利用用户局部结构信息或全局结构信息作为用户识别指标,难以实现用户识别精度与计算时间代价的平衡;(2)现有方法大多为启发式算法，仅针对特定跨网络用户识别问题进行研究，适用性受到限制，无法保证算法在不同类型网络中的普适性。为此，本文从四个方面对基于结构的跨社交网络用户识别方法进行改进:
(1)提出了基于SimRank的跨社交网络用户识别方法。首先,提出了基于SimRank的跨网络用户相似性，精准衡量跨网络用户相似性，通过参数调节可有效平衡识别精度与时间代价。其次，构建了两阶段的迭代式匹配算法，第一阶段，计算候选匹配用户相似性，第二阶段,构建最优匹配策略，识别新匹配用户。在该算法中，着重针对算法复杂度过高的问题进行了优化，提出了增量式的用户相似性计算方法，并讨论了候选匹配用户过滤条件。最后，使用真实数据集进行实验评估，结果表明，基于SimRank的跨社交网络用户识别方法明显优于现有其他基于结构的跨网络用户识别方法。
(2)提出了基于双向验证的跨社交网络用户识别方法。首先，提出了三种不同的相似度算法CPS、CPS+和CCS，并利用对齐网络模型,证明了具有最高CPS或CPS+相似性的候选用户大概率为匹配用户,以及具有较低CCS的已匹配用户大概率为错误匹配用户，保证了算法的适用性。其次，利用CPS+和CCS，提出了基于双向验证的迭代式跨网络用户识别方法,在每次迭代过程中，利用CPS+进行新用户识别,利用CCS检测错误匹配用户。同时，研究了迭代收敛性以及迭代终止条件的问题，有效平衡识别结果的准确率与召回率。最后，实验结果表明,该算法识别准确率与召回率优于基于SimRank的跨社交网络用户识别方法。
(3)提出了基于最大公共子图的社交网络用户识别方法。首先，将社交网络用户识别问题抽象为最大公共子图问题α-MCS,并结合对齐网络模型,提出求解自适应参数α的方法，相比于传统基于启发式定义参数α的方法，该方法可有效区分不同类型网络中匹配用户与非匹配用户。其次,为快速准确地解决α-MCS，提出了基于最大公共子图的迭代式社交网络用户识别方法,该方法每次迭代过程包含两个阶段，第一个阶段，分别在两个社交网络中选取各自的候选匹配用户，第二个阶段，针对候选匹配用户进行识别,相比于其它算法，该算法时间代价低，且依据不同网络特征，通过参数估计，可保证较高识别精度与适用性。最后,实验结果表明,该算法在保证准确率与召回率的基础上,大幅度地提升了处理速度。
(4)提出了基于生成概率的社交网络用户识别方法。首先，依据对齐网络模型，提出了社交网络生成概率的概念，并认为生成概率最大的用户匹配策略为最优匹配用户。其次,利用该思想，提出了基于生成概率的迭代式社交网络用户识别方法,在每次迭代过程中,仅针对可提高生成概率的用户进行匹配，有效提升了识别精度与效率。最后,实验结果表明，该算法处理时间代价略高于基于最大公共子图的社交网络用户识别方法，但识别准确率与召回率明显优于大部分方法。
在传统的基于结构的跨社交网络用户识别方法中,现有方法大多通过提出有效的用户相似性函数，以评价用户是否匹配，主要存在以下不足:(1)现有方法大多利用用户局部结构信息或全局结构信息作为用户识别指标,难以实现用户识别精度与计算时间代价的平衡;(2)现有方法大多为启发式算法，仅针对特定跨网络用户识别问题进行研究，适用性受到限制，无法保证算法在不同类型网络中的普适性。为此，本文从四个方面对基于结构的跨社交网络用户识别方法进行改进:
(1)提出了基于SimRank的跨社交网络用户识别方法。首先,提出了基于SimRank的跨网络用户相似性，精准衡量跨网络用户相似性，通过参数调节可有效平衡识别精度与时间代价。其次，构建了两阶段的迭代式匹配算法，第一阶段，计算候选匹配用户相似性，第二阶段,构建最优匹配策略，识别新匹配用户。在该算法中，着重针对算法复杂度过高的问题进行了优化，提出了增量式的用户相似性计算方法，并讨论了候选匹配用户过滤条件。最后，使用真实数据集进行实验评估，结果表明，基于SimRank的跨社交网络用户识别方法明显优于现有其他基于结构的跨网络用户识别方法。
(2)提出了基于双向验证的跨社交网络用户识别方法。首先，提出了三种不同的相似度算法CPS、CPS+和CCS，并利用对齐网络模型,证明了具有最高CPS或CPS+相似性的候选用户大概率为匹配用户,以及具有较低CCS的已匹配用户大概率为错误匹配用户，保证了算法的适用性。其次，利用CPS+和CCS，提出了基于双向验证的迭代式跨网络用户识别方法,在每次迭代过程中，利用CPS+进行新用户识别,利用CCS检测错误匹配用户。同时，研究了迭代收敛性以及迭代终止条件的问题，有效平衡识别结果的准确率与召回率。最后，实验结果表明,该算法识别准确率与召回率优于基于SimRank的跨社交网络用户识别方法。
(3)提出了基于最大公共子图的社交网络用户识别方法。首先，将社交网络用户识别问题抽象为最大公共子图问题α-MCS,并结合对齐网络模型,提出求解自适应参数α的方法，相比于传统基于启发式定义参数α的方法，该方法可有效区分不同类型网络中匹配用户与非匹配用户。其次,为快速准确地解决α-MCS，提出了基于最大公共子图的迭代式社交网络用户识别方法,该方法每次迭代过程包含两个阶段，第一个阶段，分别在两个社交网络中选取各自的候选匹配用户，第二个阶段，针对候选匹配用户进行识别,相比于其它算法，该算法时间代价低，且依据不同网络特征，通过参数估计，可保证较高识别精度与适用性。最后,实验结果表明,该算法在保证准确率与召回率的基础上,大幅度地提升了处理速度。
(4)提出了基于生成概率的社交网络用户识别方法。首先，依据对齐网络模型，提出了社交网络生成概率的概念，并认为生成概率最大的用户匹配策略为最优匹配用户。其次,利用该思想，提出了基于生成概率的迭代式社交网络用户识别方法,在每次迭代过程中,仅针对可提高生成概率的用户进行匹配，有效提升了识别精度与效率。最后,实验结果表明，该算法处理时间代价略高于基于最大公共子图的社交网络用户识别方法，但识别准确率与召回率明显优于大部分方法。