[發明專利]一種兩類基于近似度分布的分層圖抽樣方法

在審

• 申請號: 201911308971.1
• 申請日: 2019-12-18
• 公開（公告）號: CN111046248A
• 公開（公告）日: 2020-04-21
• 發明（設計）人: 賀樑;朱君鵬;吳雯
• 申請（專利權）人: 華東師范大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/906
• 代理公司: 上海藍迪專利商標事務所(普通合伙) 31215
• 代理人: 徐筱梅;張翔

本發明公開了一種兩類基于近似度分布的分層圖抽樣方法，其特點采用k?means聚類算法獲取圖中節點的近似度分布，并給出k?means算法中k的最優值，統計不同層內節點的個數，得出指定比例下某層抽取節點數目的閾值，然后在圖中采用基于邊和基于隨機游走的抽樣策略，利用上述閾值篩選抽出的節點，并根據導出子圖技術獲取完整抽樣子圖，導出子圖技術能夠保證抽樣子圖的局部完整性，最后采用常用指標評價抽樣結果的準確性。本發明與現有技術相比具有快速挖掘大規模圖中隱藏的有價值的信息，抽樣準確度高，有效解決了抽樣有偏性的問題。

技術領域

本發明涉及圖數據分析和應用技術領域，尤其是一種兩類基于近似度分布的分層圖抽樣方法。

背景技術

隨著，現實世界的眾多應用與前所未有的方式和速度產生并積累著大量數據，圖作為一種有效描述大數據的數據結構，扮演者越來越重要的角色。在社交網絡分析、推薦網絡分析等研究領域，許多計算問題都能轉化為一個基于圖的問題，如何準確地建模并高效地分析它們，逐漸成為數據分析領域的研究熱點。在圖模型中，自然界的實體被抽象為點，它們之間的關系被抽樣成邊，如何快速且高效地分析和挖掘圖數據中蘊含的大量有價值的信息成為當前圖數據分析領域的研究重點。不同學科從不同角度入手均進行了有價值地分析，計算機科學的飛速發展使得圖分析與挖掘的研究工作取得了巨大的進展，優秀的研究成果層出不窮。

近幾年，由于大規模圖分析應用領域的飛速發展，致使圖數據規模急劇增長，抽樣技術作為有效地數據規約方法被廣泛應用，這都推動了計算機科學家對圖抽樣算法的研究。目前，圖抽樣算法大致分為三種類型：基于點選擇策略的隨機抽樣算法、基于邊選擇策略的隨機抽樣算法和基于圖拓撲結構的抽樣算法。早期對圖抽樣算法的研究局限于靜態小規模圖的抽樣，它們通常假設圖數據規模較小，并且能夠全部放入主存。直到2006年，Leskovec首次提出了針對大規模圖數據的抽樣算法FFS，文中首次匯總了15個常見的抽樣結果度量標準，同時該文指出，在抽樣過程中，基于點選擇策略的抽樣算法易于偏向抽取低度節點，基于邊選擇策略的抽樣算法易于偏向抽取高度節點，基于拓撲結構的抽樣算法易于偏向抽取高度節點。同時還提出將15％和20％作為最佳的抽樣比例，進一步增強了圖分析領域人員對圖抽樣算法的認識。文中還指出，有偏抽樣大大降低了抽樣結果準確性。2010年，Gjoka提出了MHRW算法，該算法基于Markov-chain Monte Carlo(MCMC)算法，它被證明是實現無偏性圖抽樣的一個較好的解決方案。2016年，Luping Yu的論文總結了現有性能較優的圖抽樣算法，并采用真實世界的圖數據集評估了算法的抽樣性能。圖抽樣技術不僅在理論研究方面發展迅速，而且在圖抽樣應用方面也有諸多成果。Rafiei提出可以在大規模圖中使用抽樣技術高效地實現可視化。Yanhong Wu在2016年提出圖抽樣的可視化觀點，該文指出，抽樣方法應該重視圖數據集中的高度節點，即高度節點應該被作為重要的可視化因子，該文針對高度節點提出了一系列假設，并通過實驗驗證了假設的正確性。

現有技術在一次抽樣過程中存在著抽樣有偏性的問題，抽樣準確度差，想要提高抽樣精確度，只能通過大量重復抽樣，在大數據時代，重復多次抽樣顯得不切實際。

發明內容

本發明的目的是針對現有技術的不足而設計的一種兩類基于近似度分布的分層圖抽樣方法，采用k-means聚類算法獲取圖中節點的近似度分布，利用不同層抽樣節點數閾值篩選節點，以獲取抽樣子圖中的特征參數，并評價抽樣結果的準確性。通過使用圖的度分布特性，自動獲得圖的近似度分布，從而避免通過統計獲得節點的度分布，并給出了近似度分布的計算方法，統計不同層內節點的個數，得出指定比例下某層抽取節點的閾值，在大規模圖中采用基本抽樣算法，實現基于近似度分布的篩選策略，從而達到調整一次抽樣過程中存在的抽樣有偏性問題；接著利用導出子圖技術，得到相對完整的局部子圖，能夠快速挖掘大規模圖中隱藏的有價值的信息。

本發明的目的是這樣實現的：一種兩類基于近似度分布的分層圖抽樣方法，其特點具體包括以下步驟：