[發明專利]圖數據處理方法、裝置、計算機設備和存儲介質

有效

• 申請號: 202110248839.7
• 申請日: 2021-03-08
• 公開（公告）號: CN112597399B
• 公開（公告）日: 2021-07-16
• 發明（設計）人: 許杰;李曉森;歐陽文;肖品;陶陽宇
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F16/9535
• 分類號: G06F16/9535;G06F16/9536;G06N20/00;G06Q50/00
• 代理公司: 廣州華進聯合專利商標代理有限公司 44224
• 代理人: 董慧

本申請涉及一種圖數據處理方法、裝置、計算機設備和存儲介質。所述方法涉及數據挖掘技術，包括：獲取有向圖，有向圖中的有向邊以從起始節點指向目的節點表示；根據起始節點的節點標識與目的節點的節點標識之間的指定順序，將有向邊以統一形式表示；生成用于記錄有向邊的原始邊方向的邊標記，得到標記后的有向圖；基于標記后的有向圖中的節點、節點的鄰居節點、與節點和鄰居節點共同相鄰的共同節點兩兩之間的邊標記，識別節點、鄰居節點與共同節點構成的三角形的類別。采用本方法能夠從有向圖中識別出三角形的類別，同時避免三角形的冗余計算，節省計算資源。

技術領域

本申請涉及大數據處理技術領域，特別是涉及一種圖數據處理方法、裝置、計算機設備和存儲介質。

背景技術

圖（Graph）是一種表示一系列對象之間的關系的數據結構，當圖中相鄰的兩個節點之間存在共同節點時，該兩個節點與共同節點就可以構成三角形，三角形的數量可以在一定程度上反映該圖所表示網絡的稠密程度和質量。例如，近年來，隨著互聯網技術的快速發展，越來越多的用戶加入各式各樣的社區網絡，一個社區網絡可以看做是一張圖，社區網絡中的人對應于圖中的節點（Vertex），社區網絡中的人際關系對應于圖中的邊（Edge），社區網絡圖中三角形的數量可以在一定程度上反映社區網絡的稠密程度。

目前，一些針對圖結構數據的三角形計數方法主要分為兩大類，分別是基于節點匹配的三角形計數方法和基于邊匹配的三角形計數方法。然而，這兩類方法主要應用于無向圖(Undirected Graph)，不適于有向圖（Directed Graph）中由邊的方向性引起的三角形類別的識別，此外，這兩類方法對圖中的每個節點都會重復統計三角形，導致每個三角形都會被統計三次，存在嚴重的冗余計算，占用較多的計算資源。

發明內容

基于此，有必要針對上述技術問題，提供一種能夠高效地識別有向圖中三角形類別的圖數據處理方法、裝置、計算機設備和存儲介質。

一種圖數據處理方法，所述方法包括：

獲取有向圖，所述有向圖中的有向邊以從起始節點指向目的節點表示；

根據所述起始節點的節點標識與所述目的節點的節點標識之間的指定順序，將所述有向邊以統一形式表示；

生成用于記錄所述有向邊的原始邊方向的邊標記，得到標記后的有向圖；

基于所述標記后的有向圖中的節點、所述節點的鄰居節點、與所述節點和所述鄰居節點共同相鄰的共同節點兩兩之間的邊標記，識別所述節點、所述鄰居節點與所述共同節點構成的三角形的類別；

其中，識別的所述三角形的類別，用于生成所述節點的特征向量。

一種圖數據處理裝置，所述裝置包括：

獲取模塊，用于獲取有向圖，所述有向圖中的有向邊以從起始節點指向目的節點表示；

邊表示模塊，用于根據所述起始節點的節點標識與所述目的節點的節點標識之間的指定順序，將所述有向邊以統一形式表示；

邊標記模塊，用于生成用于記錄所述有向邊的原始邊方向的邊標記，得到標記后的有向圖；

識別模塊，用于基于所述標記后的有向圖中的節點、所述節點的鄰居節點、與所述節點和所述鄰居節點共同相鄰的共同節點兩兩之間的邊標記，識別所述節點、所述鄰居節點與所述共同節點構成的三角形的類別；其中，識別的所述三角形的類別，用于生成所述節點的特征向量。

一種計算機設備，包括存儲器和處理器，所述存儲器存儲有計算機程序，所述處理器執行所述計算機程序時實現以下步驟：

獲取有向圖，所述有向圖中的有向邊以從起始節點指向目的節點表示；

根據所述起始節點的節點標識與所述目的節點的節點標識之間的指定順序，將所述有向邊以統一形式表示；