[發明專利]一種大型社交網絡的快速準確采樣方法

在審

• 申請號: 202210432247.5
• 申請日: 2022-04-22
• 公開（公告）號: CN114896516A
• 公開（公告）日: 2022-08-12
• 發明（設計）人: 盧罡;金晶;李睿琪;谷偉偉
• 申請（專利權）人: 北京化工大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種大規模社交網絡的快速準確采樣方法，其特征在于，包括對用戶ID空間進行均勻劃分對每個區間設定采樣概率，并設定動態規劃閾值對區間進行動態規劃，在DaptUNI+N方法的采樣過程中將樣本節點的鄰居節點加入樣本集中，其中

所述對用戶ID空間均勻劃分對每個區間設定采樣概率，用于區間自適應地進行采樣；

所述動態規劃閾值，用于對所有區間進行動態規劃；

所述樣本節點的鄰居節點加入樣本集中，用于提高采樣子網的代表性。

2.根據權利要求1所述的大規模社交網絡的快速準確采樣方法，其特征是，所述對用戶ID空間均勻劃分對每個區間設定采樣概率，具體為設定合理的區間劃分數，將區間分為一個個等長小區間，對每個區間設定采樣概率，采樣概率由命中率和采樣率決定，具體與命中率正相關、與采樣率負相關，用于對各個區間進行自適應地調整以提高采樣效率。

3.根據權利要求1所述的大規模社交網絡的快速準確采樣方法，其特征是，所述動態規劃閾值，具體包括：

區間調整概率，用于初步判斷該區間需要進行劃分還是進行合并；

最小區間長度，用于規定區間劃分的極限值，各區間的長度不能小于最小區間長度。

4.根據權利要求1所述的大規模社交網絡的快速準確采樣方法，其特征是，所述動態規劃，具體操作如下：

若相鄰兩區間的命中率同時大于區間調整概率，則合并這兩個區間，更新新區間的各項屬性值；

若某區間的命中率小于區間調整概率，且該區間的長度大于最小區間長度，則將這個區間一分為二，更新新區間的各項屬性值。

若無上述兩種情況，那么不對區間進行調整，保留該區間。

5.根據權利要求1所述的大規模社交網絡的快速準確采樣方法，其特征是，所述樣本節點的鄰居節點加入樣本集中，具體是在采樣過程中，根據采樣節點搜尋網絡中該節點的鄰居節點，并將搜尋到的鄰居節點也加入樣本集中，以提高采樣子網的代表性。

6.一種如根據權利要求1所述的大規模社交網絡的快速準確采樣方法其特征在于，包括以下步驟：

步驟1：獲得用戶ID空間范圍，將ID空間均勻劃分為各個區間，初始化各個區間屬性值；

步驟2：根據區間的采樣概率，對于每個區間進行自適應采樣，并對應更新區間的屬性值；

步驟3：將采集到的節點樣本的鄰居節點加入樣本集合，并更新對應區間的各項屬性值；

步驟4：縱觀整體區間進行動態規劃，相鄰密集區間合并，稀疏區間劃分，更新區間的屬性值；

步驟5：重復步驟2至步驟4直至樣本數達到采樣規模為止。