[發明專利]社區劃分方法及裝置

在審

• 申請號: 201710444988.4
• 申請日: 2017-06-12
• 公開（公告）號: CN107341733A
• 公開（公告）日: 2017-11-10
• 發明（設計）人: 杜翠鳳
• 申請（專利權）人: 廣州杰賽科技股份有限公司
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 廣州三環專利商標代理有限公司44202
• 代理人: 梁順宜,郝傳鑫

技術領域

本發明涉及計算機領域，尤其涉及一種社區劃分方法及裝置。

背景技術

社團結構是社會網絡具有的一個共同的性質，滿足同一社團內部節點連接相對緊密、不同社團節點連接相對稀疏的特點。社團劃分的本質是對社會網絡進行劃分使之成為一個較小的社團，社團內部的成員關系比較緊密，社團與社團之間的成員關系比較稀疏，這與聚類分析的本質很相似。

現有社團劃分的研究算法凝聚算法的典型代表是Newman快速算法，其思想是從空網絡開始，逐步添加相似性的邊，同時在計算相似性的時候通過模塊度來標示社團分割的質量，具體為，去掉網絡中所有的邊，網絡的每個結點都單獨作為一個社區；網絡中的每個連通部分作為一個社區，將還未加入網絡的邊分別重新加回網絡，每次加入一條邊，如果加入網絡的邊連接了兩個不同的社區，則合并兩個社區，并計算形成新社區劃分的模塊度增量，選擇使模塊度增量最大或者減小最少的兩個社區進行合并。上述Newman快速算法僅僅考慮復雜網絡的局部屬性，且只考慮節點自身的信息以及其鄰居的信息，而忽略了鄰居的鄰域信息會對節點與鄰居的連接強度產生大的影響。

發明內容

本發明實施例的目的是提供一種社區劃分方法及裝置，能有效解決現有社區劃分方法忽略鄰居的鄰域信息問題，實現在特定數據下大幅度提高社區劃分的效率和精度。

為實現上述目的，本發明實施例提供了一種社區劃分方法，包括步驟：

接收若干個待劃分用戶的信息，根據所述待劃分用戶的信息建立拓撲結構圖；

計算所述拓撲結構圖中各個節點的度，將所述拓撲結構圖中度數最大的節點作為種子節點，獲取所述種子節點的鄰居節點；

根據每一所述鄰居節點的鄰域屬性，計算所述種子節點對每一所述鄰居節點的投入精力占比；

根據所述種子節點對每一所述鄰居節點的投入精力占比，通過結構洞的網格約束算法獲取所述種子節點對每一所述鄰居節點的約束系數；

將所述約束系數大于預設的關系閾值的鄰居節點和所述種子節點劃分為同一社團，并將所述約束系數大于預設的閾值的鄰居節點和所述種子節點從所述拓撲結構圖中刪除。

與現有技術相比，本發明公開的社區劃分方法通過基于所述待劃分用戶的信息建立拓撲結構圖，然后將所述拓撲結構圖中度數最大的節點作為種子節點，獲取所述種子節點的鄰居節點，根據每一所述鄰居節點的鄰域屬性，計算所述種子節點對每一所述鄰居節點的投入精力占比，再通過結構洞的網格約束算法獲取所述種子節點對每一所述鄰居節點的約束系數，將所述約束系數大于預設的關系閾值的鄰居節點和所述種子節點劃分為同一社團，并將所述約束系數大于預設的閾值的鄰居節點和所述種子節點從所述拓撲結構圖中刪除，本方案將鄰居節點的鄰域屬性引入結構洞的網格約束系數算法中，充分考慮了鄰居節點的鄰域信息對種子節點與鄰居節點的連接強度的影響，解決現有社區劃分方法僅僅考慮自身節點和鄰居節點的關系而忽略鄰居節點的鄰域信息問題，實現在特定數據下大幅度提高社區劃分的效率和精度。

作為上述方案的改進，所述根據每一所述鄰居節點的鄰域屬性，計算所述種子節點對每一所述鄰居節點的投入精力占比具體為：

獲取每一所述鄰居節點的鄰接度，分別計算每一所述鄰居節點的鄰接度占所述每一所述鄰居節點的鄰接度的總和的比例，從而獲得所述種子節點對每一所述鄰居節點的投入精力占比；其中，任一節點的鄰接度為所述節點的鄰居節點的度數總和。利用鄰居節點的鄰接度計算所述種子節點對每一所述鄰居節點的投入精力占比，當存在任一鄰居節點的鄰接度較大時，所述種子節點向該鄰居節點投入更多精力，從而有利于穩定社團的結構。

作為上述方案的改進，所述根據所述種子節點對每一所述鄰居節點的投入精力占比，通過結構洞的網格約束算法獲取所述種子節點對每一所述鄰居節點的約束系數具體為：

通過以下公式獲取所述種子節點對每一所述鄰居節點的約束系數：

其中，C_ij為所述種子節點i對任一所述鄰居節點j的約束系數，P_ij所述種子節點i對所述鄰居節點j的投入精力占比，q為所述種子節點i和鄰居節點j的共同鄰居節點，P_iq和P_qj分別是所述種子節點i對節點q的投入精力占比和節點q對所述鄰居節點j的投入精力占比。上述式子是結構洞的研究機制中用于表征個體網絡的閉合性，同時也表示所述種子節點和每一所述鄰居節點的緊密程度。

作為上述方案的改進，所述預設的關系閾值為最優關系閾值，所述最優關系閾值通過以下步驟獲得：