[發明專利]一種對關系網絡圖中的節點進行聚類的方法及裝置

在審

• 申請號: 201910060474.8
• 申請日: 2019-01-22
• 公開（公告）號: CN110032603A
• 公開（公告）日: 2019-07-19
• 發明（設計）人: 崔卿
• 申請（專利權）人: 阿里巴巴集團控股有限公司
• 主分類號: G06F16/28
• 分類號: G06F16/28
• 代理公司: 北京億騰知識產權代理事務所(普通合伙) 11309
• 代理人: 陳霽;周良玉

1.一種對關系網絡圖中的節點進行聚類的方法，所述關系網絡圖包括多個節點和多個連接邊，所述方法包括：

獲取所述關系網絡圖的鄰接信息，所述鄰接信息記錄了各個節點之間是否具有連接邊，以及連接邊的邊長；

根據所述鄰接信息，確定以各個節點為中心節點的各個鄰居節點集合，以及各個鄰居節點集合中節點之間的最短連接邊；其中，所述鄰居節點集合包括對應的中心節點，以及與該對應的中心節點的連接階數不超過預定階數k的鄰居節點，k為大于1的整數；

確定各個最短連接邊中邊長小于預設閾值的至少一個第一邊；

對于各個第一邊，將第一邊連接的兩個節點聚為同一類簇，并將所述兩個節點進行合并；

根據合并之后的節點，更新所述鄰接信息，更新后的所述鄰接信息用于再次進行節點合并。

2.根據權利要求1所述的方法，其中，所述關系網絡圖中的節點對應于樣本，所述連接邊的邊長對應于樣本之間的相似度或關聯緊密度。

3.根據權利要求2所述的方法，其中，所述樣本包括用戶樣本，所述關聯緊密度基于以下中的至少一項確定：用戶之間的交互類型，交互頻次，來往資金數額。

4.根據權利要求1所述的方法，其中，所述獲取所述關系網絡圖的鄰接信息包括：

獲取所述關系網絡圖的鄰接矩陣，通過所述鄰接矩陣確定相互連接的節點；

獲取各個節點的嵌入向量；

根據各個節點的嵌入向量計算所述相互連接的節點之間的連接邊的邊長。

5.根據權利要求1所述的方法，其中，所述獲取所述關系網絡圖的鄰接信息包括：

獲取所述關系網絡圖的距離矩陣，所述距離矩陣用作所述鄰接信息。

6.根據權利要求1所述的方法，其中，所述確定以各個節點為中心節點的各個鄰居節點集合包括：

遍歷所述關系網絡圖的鄰接信息，以得到各個節點的1階鄰居節點；

對于各個節點，將其n階鄰居節點的1階鄰居節點中的第一鄰居作為各個節點的n+1階鄰居節點，添加到該節點對應的鄰居節點集合中，直到n達到k-1；其中，第一鄰居為各個節點的n階鄰居的1階鄰居中排除了各個節點的n-1階鄰居后的鄰居節點。

7.根據權利要求1所述的方法，其中，所述至少一個第一邊的數目為1時，所述方法還包括：

根據更新后的鄰接信息，確定更新后的關系網絡圖中的最短邊；

當所述最短邊小于所述預設閾值時，合并所述最短邊所連接的兩個節點；

根據合并后的節點，再次更新所述鄰接信息。

8.根據權利要求1所述的方法，其中，所述第一邊連接的兩個節點分別為第一節點和第二節點，第一節點和第二節點同時與第三節點連接，所述將所述兩個節點進行合并包括，將第一節點和第二節點合并為第四節點；

所述根據合并之后的節點，更新所述鄰接信息包括：根據第一節點與第三節點的連接邊的第一邊長，以及第二節點與第三節點的連接邊的第二邊長，確定第四節點與第三節點的邊長。

9.根據權利要求1所述的方法，其中，所述第一邊連接的兩個節點分別為第一節點和第二節點，第一節點與第三節點連接，第二節點未與第三節點連接，所述將所述兩個節點進行合并包括，將第一節點和第二節點合并為第四節點；

所述根據合并之后的節點，更新所述鄰接信息包括：將第一節點與第三節點的連接邊的邊長，作為第四節點與第三節點的連接邊的邊長。