基于子结构感知的社交网络Graphlets采样算法研究

摘要

Graphlets(图元)是指大规模网络中那些节点数目较少的连通诱导子图，在社交网络和生物信息学等领域有着广泛的应用。随着graphlets节点数目的增多，graphlets的种类数增长迅速且结构变化复杂，快速估计大规模社交网络中所有graphlets的频率是一项挑战。由于精确计数的计算成本较高，目前大多用基于随机游走的采样算法来近似估计graphlets的频率，而这些算法大多只能估计不超过5个节点的graphlets，很难扩展到高阶graphlets。因此，设计一个估计精度高且能扩展到估计高阶graphlets频率的采样算法具有重要的研究意义。
　　本文中，我们提出了一种基于最大公共子结构感知的社交网络graphlets采样算法CSRW(Common Substructure based graphlets sampling via Random Walk)。给定graphlets的节点数k，CSRW首先感知并游走一个所有k-graphlets都共享的最大公共子结构2-path((±))，再从多个节点的邻居中随机生成下一跳节点，直至得到k-graphlets样本，从而以统一的方式估计所有类型k-graphlets的频率。
　　此外，当graphlets节点数目k增加时，k-graphlets呈现出更复杂的拓扑结构。那些结构更稠密的graphlets在真实社交网络中很少出现，采样相对困难。为此，本文提出了一种基于两种子结构感知调和的社交网络graphlets采样算法CSRW2，以提升那些较少出现、结构更稠密的graphlets的估计精确度。给定阶数k（k=4，5），CSRW2首先分别采样子结构(k-1)-path和3-star((÷))，再扩展得到两种样本，然后用比例放大法调和两种样本，从而可以适应graphlets结构的复杂变化并高效估计graphlets的频率。
　　综合性实验表明，CSRW能统一地估计所有k-graphlets类型，其算法精确性优于当前代表性算法SRW2CSS和WRW;6，7-graphlets的估计结果也证明了CSRW的可扩展性。CSRW2也以统一的框架估计所有k-graphlets的频率(k=4，5)，且相对CSRW来说，CSRW2更有利于估计那些出现较少、结构较稠密的graphlets。

目录

声明

摘要

第1章 绪论

1．1 在线社交网络及其应用

1．2 在线社交网络的数据挖掘

1．2．1 网络数据挖掘及其应用

1．2．2 社交网络的常用挖掘指标：Graphlets

1．2．3 社交网络的常用挖掘手段：采样方法

1．3 社交网络中Graphlets挖掘的研究状况与发展趋势

1．4 本文的研究内容和主要贡献

1．5 本文组织结构

第2章 社交网络中Graphlets采样算法的相关研究

2．1 社交网络中Graphlets采样的背景知识

2．1．1 社交网络图模型

2．1．2 Graphlets

2．1．3 随机游走

2．1．4 图上的随机游走采样

2．2 社交网络中Graphlets采样的相关研究

2．3 本文的研究意义

2．4 本章小结

第3章 基于最大公共子结构感知的Graphlets采样算法CSRW

3．1 引例

3．1．1 基于SRW的Graphlets采样算法示例及其不足

3．1．2 Graphlets统一采样思路的形成

3．2 CSRW的算法思想

3．3 CSRW的偏差校正

3．3．1 CSRW的重复系数计算

3．3．2 CSRW的无偏估计

3．4 CSRW估计Graphlets频率值的算法框架

3．5 实验分析

3．5．1 算法精确度分析

3．5．2 算法扩展性验证

3．5．3 时间性能分析

3．6 本章小结

第4章 基于两种子结构感知调和的Graphlets采样算法CSRW2

4．1 改进思路的形成

4．2 CSRW2的算法思想

4．3 CSRW2的偏差校正

4．3．3 CSRW2的无偏估计

4．4 CSRW2估计Graphlets频率值的算法框架

4．5 实验分析

4．5．1 算法精确度分析

4．5．2 时间性能分析

4．6 本章小结

第5章 总结与展望

5．1 总结

5．2 展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果