[發明專利]一種低空間開銷的大規模圖中三角形計數方法及系統

在審

• 申請號: 202010920564.2
• 申請日: 2020-09-04
• 公開（公告）號: CN112131444A
• 公開（公告）日: 2020-12-25
• 發明（設計）人: 肖儂;牟者斌;盧宇彤;陳志廣
• 申請（專利權）人: 中山大學
• 主分類號: G06F16/9035
• 分類號: G06F16/9035;G06F16/901
• 代理公司: 深圳市創富知識產權代理有限公司 44367
• 代理人: 李思坪

本發明公開了一種低空間開銷的大規模圖中三角形計數方法及系統，該方法包括：獲取數據集并根據數據集構建有向圖，得到圖數據；遍歷圖數據中的所有頂點并將頂點按預設規則放入預設的布隆篩；根據圖數據中的邊得到該邊對應的兩個頂點；判斷到這兩個頂點存在于布隆篩中，計算這兩個頂點的鄰居頂點集合的交集，得到該邊對應三角形的數量。該系統包括：圖數據模塊、放入模塊、頂點模塊和交集模塊。通過使用本發明，可以在保證低空間開銷的情況下從大規模的數據中快速計算出三角形的數量。本發明作為一種低空間開銷的大規模圖中三角形計數方法及系統，可廣泛應用于大規模數據處理領域。

技術領域

本發明涉及大規模數據處理領域，尤其涉及一種低空間開銷的大規模圖中三角形計數方法及系統。

背景技術

隨著我們在生活中使用互聯網的次數日益增多，各類數據的增加速度與總量也與日俱增，甚至用“指數性增長”“海量”等詞都難以描述數據的增量和增速。然而人們對數據進行分析和處理的速度卻未能跟上數據的增長規模和速度，大規模的數據中隱藏的信息與價值被我們所挖掘和利用的還只是冰山一角。所以近幾年，針對互聯網的研究方向和趨勢便是朝著如何分析處理大規模數據的方向發展。作為常見并且重要的數據結構之一，圖數據可以更好的表達個體與個體以及個體與群體之間的聯系，因此也越來越引發科研工作者以及企業的關注。

對圖數據分析中，三角形可以表示其中的關聯關系，三角形計數問題已有很多解決方案.其基本方法主要有兩類。一類是通過遍歷圖中的所有頂點，在其所有的鄰居節點間查找存在的不重復邊的數量，該數量之和即為該圖的三角形的數量的三倍。另一類方法是通過遍歷圖中所有邊，對其兩頂點的鄰居頂點集取交集，每條邊的該交集的元素數量之和即為該圖的三角形數量的三倍。如何從大規模的數據中快速計算出所有的三角形，是目前的應用瓶頸。雖然針對大規模數據集，已有許多成熟的方法，如基于MapReduce計算平臺的分布式方法等等。但是針對現實世界中的各類大規模的稀疏圖，如社交網絡，交通路網等，往往存在著或空間開銷過大(例如單機方法無法處理大規模的圖)或時間開銷過大(例如隨機訪問內存或在分布式方法中通信過于頻繁)等問題。

發明內容

為了解決上述技術問題，本發明的目的是提供一種低空間開銷的大規模圖中三角形計數方法及系統，可以在保證低空間開銷的情況下從大規模的數據中快速計算出三角形的數量。

本發明所采用的第一技術方案是：一種低空間開銷的大規模圖中三角形計數方法，包括以下步驟：

獲取數據集并根據數據集構建有向圖，得到圖數據；

遍歷圖數據中的所有頂點并將頂點按預設規則放入預設的布隆篩；

根據圖數據中的邊得到該邊對應的兩個頂點；

判斷到這兩個頂點存在于布隆篩中，計算這兩個頂點的鄰居頂點集合的交集，得到該邊對應三角形的數量。

進一步，還包括：

遍歷圖數據中所有的邊并得到所有邊對應參與構成三角形的數量；

將所有邊對應參與構成三角形的數進行加和，得到圖數據的三角形總數量。

進一步，所述獲取數據集并根據數據集構建有向圖，得到圖數據這一步驟，其具體包括：

獲取數據集并將數據集重新組織成有序的邊集數組；

根據邊集數組構建大小為頂點數量并儲存有索引信息的索引數組；

根據邊集數組和索引數組得到圖數據。

進一步，所述遍歷圖數據中的所有頂點并將頂點按預設規則放入布隆篩這一步驟，其具體包括：

依次遍歷圖中所有的頂點并將該頂點的鄰居頂點中所有不相同的兩頂點構成頂點對；

將頂點對按照頂點編號小的在前、大的在后的形式加入布隆篩中。