一种拒绝率可控的Metropolis-Hastings图抽样算法

摘要

本发明公开一种拒绝率可控的Metropolis-Hastings算法，首先在图上随机游动采集样本；其次，根据采集得到的样本构造无偏估计。能够有效地解决从一个“隐藏”的在线社交网络中提取均匀样本的问题。该方法很好地平衡了RW算法的“大偏差”问题，以及MH算法的“样本拒绝”问题，该算法适用性非常广泛，如社交网络分析，图数据管理、和图数据挖掘等相关技术领域。

主权项

一种拒绝率可控的Metropolis‑Hastings图抽样算法，包含以下步骤：S1、在图上随机游动采集样本，得到的样本点集S；在图中随机选择节点u设为初始节点，并且将节点u加入点集S，从节点u的邻接节点中等概率随机选取一个节点v,并生成一个均匀分布的概率值q∈[0,1]；如果q≤(d_u/d_v)^α则将节点v作为下一步的节点u，并将节点v加入点集S，否则不做任何操作；S2、根据采集得到的样本构造无偏估计，并通过以下公式构造无偏估计：$E_{{\pi }^{\mathrm{rcmh}}}\left(f\right)=\frac{{\Sigma }_{u\in S}f\left(u\right)w^{\mathrm{rcmh}}\left(u\right)}{{\Sigma }_{u\in S}{w}^{\mathrm{rcmh}}\left(u\right)}$其中，$w^{\mathrm{rcmh}}\left(u\right)=d_u^{(\alpha -1)}.$