基于虚拟坐标的社交网络距离估计改进算法研究

摘要

随着互联网技术的不断发展，社交网络的发展也如火如荼，衍生出一系列社交网络应用。这些应用大多以网络节点之间的距离信息为基础，社交网络中的距离是对用户之间逻辑关系的一种描述，与物理距离无关，一般使用节点间最短路径的长度表示。随着现代社交网络的规模日渐庞大，使用传统方法对网络中节点间距离进行精确计算所花费代价已难以承受。现有的大规模社交网络中节点间距离估计算法大多采用将社交网络嵌入低维空间的技术，也就是利用参考节点进行坐标分配的方法实现距离估计。但现有的方法中存在一个共性问题，在为普通节点分配坐标时，仅仅使用了参考节点中的一少部分用于坐标分配，影响了距离估计算法的精度。
　　本文针对现有方法的不足进行研究，提出了基于坐标嵌入技术的距离估计算法SDE（ShortestPath Distance Estimation）。该算法选择将社交网络嵌入不受对称性约束的内积空间，使其能同时适用于无向图与有向图进行距离估计。为提高距离估计的精确度，该算法使用全部的参考节点信息为节点分配坐标，但这就存在会过多增加计算压力的问题。为了解决这一问题，本文提出了基于组矩阵分解的坐标分配算法RGMD（Robust Group Matrix Decomposition）。RGMD借鉴了鲁棒性主成分分析提取低秩矩阵、去除异常值的思想，将坐标分配过程转化为抽取低秩矩阵的优化问题。RGMD算法采用把所有参考节点分成若干组的方式，通过组与组之间并行计算完成对其它节点的坐标分配。这种方法将坐标分配算法的优化过程由对单一变量的优化转化为对一组变量的同时优化，不仅将坐标分配算法的计算压力从指数增加降低到常数倍增加，而且将坐标分配与坐标校正两个过程合二为一，进一步提高了距离估计算法的精确度。
　　本文在6个开源的真实社交网络数据集上对算法的性能进行了验证，主要从算法的精确度、收敛速度以及对参数的敏感性等方面展开。除此之外，还实现了4个社交网络中常用的基于距离计算的应用，从应用的角度对算法的性能进行验证。实验结果表明，相较于已有的算法，本文提出的算法虽然时间开销略有增加，但在精确度方面有大幅度提升。

目录

第1章 绪论

1.1 研究背景及意义

1.2 国内外研究现状及分析

1.3 本文的主要研究内容

1.4 本文的结构安排

第2章 社交网络中距离估计算法研究

2.1 引言

2.2 基于欧式空间的估计算法

2.3 基于双曲空间的估计算法

2.4 基于内积空间的估计算法

2.5 现有距离估计算法的分析

2.6 本章小结

第3章 基于坐标嵌入的距离估计算法研究

3.1 引言

3.2 问题描述

3.3 基于内积空间的距离估计算法

3.4 坐标分配算法

3.5 算法的时间复杂度分析

3.6 本章小结

第4章 模拟实验与分析

4.1 模拟实验环境及实验数据介绍

4.2 算法基本性能评测

4.3 算法参数敏感性评测

4.4 实际应用模拟实验

4.5 本章小结

结论

参考文献

声明

致谢