[發明專利]基于圖數據生成N跳子圖的方法和系統

在審

• 申請號: 202210023951.5
• 申請日: 2022-01-11
• 公開（公告）號: CN114048355A
• 公開（公告）日: 2022-02-15
• 發明（設計）人: 敬斌
• 申請（專利權）人: 支付寶（杭州）信息技術有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903;G06F16/904
• 代理公司: 成都七星天知識產權代理有限公司 51253
• 代理人: 袁春曉

1.一種基于圖數據生成N跳子圖的方法，其中，圖數據包括節點數據和邊數據，N≥2，所述方法包括：

獲取起始節點的節點標識；

基于起始節點的節點標識以及所述邊數據，經過一輪搜索或多輪迭代搜索，獲取所述起始節點的N-1跳子圖所包含的外圍節點的節點標識；

基于節點標識獲取所述起始節點以及各外圍節點的1跳子圖，并基于所述起始節點以及各外圍節點的1跳子圖得到所述起始節點的N跳子圖；其中，1跳子圖包括該子圖的中心節點與第1跳節點的節點數據及節點間的邊數據。

2.如權利要求1所述的方法，其中，所述方法還包括：基于所述節點數據和所述邊數據，生成圖數據中各節點的1跳子圖；

所述基于節點標識獲取所述起始節點以及各外圍節點的1跳子圖，包括：

基于所述起始節點以及各外圍節點的節點標識，從所述各節點的1跳子圖中選出所述起始節點以及各外圍節點的1跳子圖。

3.如權利要求1所述的方法，其中，節點數據包括節點標識以及節點屬性；邊數據包括邊對應的兩個節點的節點標識以及邊屬性。

4.如權利要求1所述的方法，其中，一輪迭代搜索，包括：

根據起始節點的各第i-1跳節點的節點標識，從所述邊數據中確定所述各第i-1跳節點的第1跳節點的節點標識，以獲得所述起始節點的第i跳節點的節點標識，其中，2≤i≤N-1。

5.如權利要求4所述的方法，其中，生成的N跳子圖為入邊子圖；所述邊數據指示邊的方向；

所述根據起始節點的各第i-1跳節點的節點標識，從所述邊數據中確定所述各第i-1跳節點的第1跳節點的節點標識，以獲得所述起始節點的第i跳節點的節點標識，包括：

對于起始節點的任一第i-1跳節點，根據該第i-1跳節點的節點標識，確定以該第i-1跳節點為目的節點的邊數據，并將該邊數據中的源節點的節點標識確定為該第i-1跳節點的第1跳節點的節點標識。

6.如權利要求4所述的方法，其中，生成的N跳子圖為出邊子圖；所述邊數據指示邊的方向；

所述根據起始節點的各第i-1跳節點的節點標識，從所述邊數據中確定所述各第i-1跳節點的第1跳節點的節點標識，以獲得所述起始節點的第i跳節點的節點標識，包括：

對于起始節點的任一第i-1跳節點，根據該第i-1跳節點的節點標識，確定以該第i-1跳節點為源節點的邊數據，并將該邊數據中的目的節點的節點標識確定為該第i-1跳節點的第1跳節點的節點標識。

7.如權利要求4所述的方法，其中，生成的N跳子圖為出入邊子圖；所述邊數據指示邊的方向；

所述根據起始節點的各第i-1跳節點的節點標識，從所述邊數據中確定所述各第i-1跳節點的第1跳節點的節點標識，以獲得所述起始節點的第i跳節點的節點標識，包括：

對于起始節點的任一第i-1跳節點，根據該第i-1跳節點的節點標識，確定包含該第i-1跳節點的節點標識的邊數據，并將該邊數據中的另一節點的節點標識確定為該第i-1跳節點的第1跳節點的節點標識。

8.如權利要求1所述的方法，其中，所述得到所述起始節點的N跳子圖，包括：

合并所述起始節點以及各外圍節點的1跳子圖，得到所述起始節點的N跳子圖。

9.一種基于圖數據生成N跳子圖的系統，其中，圖數據包括節點數據和邊數據，N≥2，所述系統包括：

第一獲取模塊，用于獲取起始節點的節點標識；

搜索模塊，用于基于起始節點的節點標識以及所述邊數據，經過一輪搜索或多輪迭代搜索，獲取所述起始節點的N-1跳子圖所包含的外圍節點的節點標識；

子圖生成模塊，用于基于節點標識獲取所述起始節點以及各外圍節點的1跳子圖，并基于所述起始節點以及各外圍節點的1跳子圖得到所述起始節點的N跳子圖；其中，1跳子圖包括該子圖的中心節點與第1跳節點的節點數據及節點間的邊數據。