[發明專利]一種基于偏移調節和競價的混合社交網絡聚類方法及系統

有效

• 申請號: 201710029428.2
• 申請日: 2017-01-16
• 公開（公告）號: CN106909619B
• 公開（公告）日: 2020-04-10
• 發明（設計）人: 盛益強;顏川力;王玲芳
• 申請（專利權）人: 中國科學院聲學研究所
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q50/00
• 代理公司: 北京億騰知識產權代理事務所(普通合伙) 11309
• 代理人: 陳霽

1.一種基于偏移調節和競價的混合社交網絡聚類方法，其特征在于，包括：

將社交網絡用戶數據整理為用戶ID及用戶關注的ID列表的組合形式，得到節點關注關系的數據列表，其中，所述節點為具有自己的ID和所關注的ID列表的個體用戶；

根據所述節點關注關系，計算節點間相似度，獲得偏移調節后的相似度矩陣；

根據偏移調節后的相似度矩陣識別出核節點，為其分配簇號，并創建對應的簇列表；所述核節點為與其直接可達的節點數量超過一個閾值的節點，所述直接可達為兩個節點相似度大于相似度閾值的視為兩個節點是直接可達的；

根據識別出的核節點，以競價的方式進行聚類；其中，所述競價方式包括：第一輪競價，由所有核節點對所有未分類節點進行，將節點劃分到競價高的核節點的簇列表中；第二輪競價，由第一輪競價中被分類的節點對所有離群點進行，通過表內競價和表間競價將節點劃分到與之具有最高競價結果的簇中。

2.根據權利要求1所述的混合社交網絡聚類方法，其特征在于，所述根據所述節點關注關系，計算節點間相似度，獲得偏移調節后的相似度矩陣，具體為：運用相似度偏移調節計算公式計算節點間相似度：

計算節點1和節點2間的相似度，其中，節點1關注的ID數量為A，節點2關注的ID數量為B，則：

對于A，相似度為：

對于B，相似度為：

其中，為現有技術中的節點1和節點2間相似度計算結果。

3.根據權利要求1所述的混合社交網絡聚類方法，其特征在于，所采用的競價方式，具體包括：

統一競價：將所有核節點對所有未分類節點進行競價，將未分類節點加入到具有最大相似度且大于相似度閾值的核節點簇列表中，競價后最大相似度小于相似度閾值的將節點暫時設置為離群點；

表內競價：先讓每個簇列表中的節點對所有離群點進行競價，每個列表內選出與該離群點所具有的最大的相似度；

表間競價：所有簇列表內選出的與該節點所具有的最大相似度進行表間競價，選出所有列表所具有的最大相似度；

若最大相似度大于或等于相似度閾值，則將該離群點設置為已分類節點并將簇號設置為具有該最大相似度的節點的簇號，若最大相似度小于相似度閾值，則對該離群點不做處理。

4.一種基于偏移調節和競價的混合社交網絡聚類系統，其特征在于，包括：

整理模塊，用于將社交網絡用戶數據整理為用戶ID及用戶關注的ID列表的組合形式，得到節點關注關系的數據列表，其中，所述節點為具有自己的ID和所關注的ID列表的個體用戶；

計算模塊，用于根據所述節點關注關系，計算節點間相似度，獲得偏移調節后的相似度矩陣；

識別模塊，用于根據偏移調節后的相似度矩陣識別出核節點，為其分配簇號，并創建對應的簇列表；所述核節點為與其直接可達的節點數量超過一個閾值的節點，所述直接可達為兩個節點相似度大于相似度閾值的視為兩個節點是直接可達的；

聚類模塊，用于根據識別出的核節點，以競價的方式進行聚類；其中，所述競價方式包括：第一輪競價，由所有核節點對所有未分類節點進行，將節點劃分到競價高的核節點的簇列表中；第二輪競價，由第一輪競價中被分類的節點對所有離群點進行，通過表內競價和表間競價將節點劃分到與之具有最高競價結果的簇中。

5.根據權利要求4所述的混合社交網絡聚類系統，其特征在于，所述計算模塊，具體用于運用相似度偏移調節計算公式計算節點間相似度：

計算節點1和節點2間的相似度，其中，節點1關注的ID數量為A，節點2關注的ID數量為B，則：

對于A，相似度為：

對于B，相似度為：

其中，為現有技術中的節點1和節點2間相似度計算結果。

6.根據權利要求4所述的混合社交網絡聚類系統，其特征在于，所述聚類模塊所采用的競價方式，具體包括：

統一競價：將所有核節點對所有未分類節點進行競價，將未分類節點加入到具有最大相似度且大于相似度閾值的核節點簇列表中，競價后最大相似度小于相似度閾值的將節點暫時設置為離群點；

表內競價：先讓每個簇列表中的節點對所有離群點進行競價，每個列表內選出與該離群點所具有的最大的相似度；

表間競價：所有簇列表內選出的與該節點所具有的最大相似度進行表間競價，選出所有列表所具有的最大相似度；

若最大相似度大于或等于相似度閾值，則將該離群點設置為已分類節點并將簇號設置為具有該最大相似度的節點的簇號，若最大相似度小于相似度閾值，則對該離群點不做處理。