【博士论文】多层图分析技术研究

多层图分析技术研究

近年来，越来越多的领域都使用“图”来表示和管理数据，称为“图数据”。针对 图数据的分析可以发现其中的结构特征、频繁模式、演变规律等有用的知识，具有 重要的科研意义和应用价值。随着研究的深入，人们发现现实世界的图数据往往 包含数据对象间多种类型的关系。例如，社交网络数据包括多个社交媒体组成的 网络；交通网络数据涵盖了多种交通工具组成的网络。这种图数据称为“多层图”， 其每一层包含了数据对象间某种特定类型的关系。

多层图分析可以发现准确可靠、价值更高的知识。然而，多层图分析面临两 方面的挑战：一方面，单层图上的计算语义在多层图场景下不再适用，多层图上 的计算语义更加复杂；另一方面，多层图分析涉及多个图层上的计算任务，使得 问题的固有计算复杂性大大增加。现有的多层图分析方法在计算语义和算法设计 两个方面都存在缺陷，不能很好的解决多层图分析的有关问题。

本文综合运用数据分析的相关理论、技术和方法，对于多层图分析进行了系统研究。本文同时考虑了无概率的普通多层图和带概率的多层图，从图数据的稠 密性、可靠性、传播性和相似性四方面重要性质出发，对多层图分析领域中的一 系列重要问题进行了深入研究，主要研究成果如下：

1. 本文研究了多层图上的多样化稠密区域发现问题，该问题在生物蛋白复合 体检测和社区发现上具有重要应用。在无概率的普通多层图模型基础上，本文提 出了一种新的稠密区域概念 d-Coherent-Core（简称 d-CC），设计了两种近似比为 1/4 的高效搜索算法来求解该 NP-难问题，算法在结果质量和执行时间两个方面 均优于基于准团的传统算法。d-CC 概念同时刻画了稠密区域的稠密度和支持度两 方面重要特性，满足唯一性、包含性和层次性 3 个重要数学性质。自底向上和自 顶向下两种搜索算法采用了高效的搜索策略和剪枝方法，分别适用于支持度参数 较小和较大两种情况。真实数据上的实验结果表明：自底向上和自顶向下两种搜 索算法是高效、准确的。

2. 本文研究了多层图上的 top-k 可靠顶点搜索问题，该问题在通信网络中具 有重要的研究意义，相比基于阈值的搜索问题自适应性更好。本文给出了一种图 层带概率的多层图模型，提出了一种新的多层图计算框架——共享计算，其可以 有效利用多层图不同图层间的重叠结构以减少搜索代价、提高算法效率。基于此，本文设计了求解 top-k 可靠顶点搜索问题的共享 BFS 精确算法和随机算法。真实 数据上的实验结果表明：共享 BFS 精确算法具有很高的效率和扩展性；共享 BFS 随机算法具有很高的准确率。

3. 本文研究了多层图上的影响力最大化问题，该问题在病毒式营销和舆情控 制中应用广泛。为描述影响力最大化问题中的图数据，本文给出了一种带概率的 多层图模型，其可以表示由于边的不确定性而形成的多层图。针对已有算法的缺 陷，本文设计了一种能够同时达到高时间效率、高结果质量、低内存开销和高健 壮性的影响力最大化算法，具有线性的时间和空间复杂度。该算法采用高质量的 分数估计方法和增量式的分数更新方法，在实际社交网络中表现出良好的性能和 很高的扩展性。

4. 本文研究了多层图上 SimRank 顶点相似性测度问题，该问题是推荐系统、 实体识别等众多应用的基础。在带概率的多层图模型基础上，本文严格给出了符 合其可能世界语义的 SimRank 相似性测度定义，设计了高效、准确的计算顶点间 SimRank 相似性的方法。同时，作为 SimRank 相似性测度的基础，本文提出了多 层图上随机游走的定义，严格证明了这一定义满足马尔可夫性，设计了计算随机 游走概率的高效算法。真实数据上的实验结果表明：本文提出的 SimRank 算法是 高效、准确的；本文提出的 SimRank 测度比传统测度在实际应用中效果更好。