[發明專利]一種基于通信時空特征的演變網絡特殊群體挖掘方法及系統

有效

• 申請號: 201710149488.8
• 申請日: 2017-03-14
• 公開（公告）號: CN107145897B
• 公開（公告）日: 2020-01-07
• 發明（設計）人: 姜松浩;宋永浩;李卓堅;趙曉芳
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q50/00
• 代理公司: 11006 北京律誠同業知識產權代理有限公司
• 代理人: 祁建國;梁揮

本發明提出一種基于通信時空特征的演變網絡特殊群體挖掘方法及系統，涉及通訊單社區發現技術領域，該方法包括步驟1，根據通信數據，獲取時間特征數據與空間特征數據，其中所述空間特征數據為產生所述通信數據的地點；步驟2，按照所述時間特征數據與所述空間特征數據及通信關系，構建靜態通信網絡，并構建與所述靜態通信網絡相對應的拉普拉斯矩陣，計算矩陣特征向量，并對矩陣特征向量進行聚類，將聚類分為特殊群體和非特殊群體兩種類簇，并獲取聚類結果；步驟3，根據所述聚類結果，采取投票機制，獲取最終特殊群體聚類結果。

技術領域

本發明涉及通訊單社區發現技術領域，特別涉及一種基于通信時空特征的演變網絡特殊群體挖掘方法及系統。

背景技術

當今社會正處于數據爆發式增長的大數據時代。人們在社交媒體上以一種前所未有的速度交流、分享、聯絡、互動，同時產生極具規模的數據。電話、短信這種傳統社交媒體在當今時代依舊起著溝通聯絡的主導地位。

社交媒體的發展產生了大量的數據，對于社會科學、商業發展、人類進步帶來了巨大潛力，社交媒體挖掘就是一種伴隨著社交媒體高速發展的新型研究領域，它是一種社會學與計算科學的交叉研究型學科，經常使用或綜合研究多個領域如統計學、數據挖掘、機器學習、社會心理學等。

社區也稱為群組(group)、集群(cluster)等，直觀上，是指網絡中的一些密集群體，每個社區內部的結點間的聯系相對緊密，它在社會學領域中已經被廣泛、深入的研究。社區發現主要針對與顯示社區相對的隱式社區挖掘。本發明主要針對于，傳統通信媒體網絡的社區發現，傳統社區發現聚類算法主要有如下幾類：

現有方法一：層次聚類，假設社區是存在層次結構，計算網絡中每對節點的相似程度，根據相似程度進行進一步劃分，主要有如下兩種劃分方法：凝聚法，根據節點對的相似度從強到弱進行連接，形成樹狀圖，然后根據需求對樹狀圖進行橫切，最終獲得社區結構；分裂法，依照得出的相似度，找出節點對中相互關聯最弱的節點，刪除他們之間的邊，反復操作將社交網絡劃分為越來越小的組件，最終連通的網絡構成社區。

現有方法二：劃分聚類，劃分聚類就是典型的機器學習中無監督學習的聚類方法，該種聚類方法很多，K-means算法是最為經典的基于劃分的聚類方法，該方法是將數據依照不同特征標準化后計算相應的距離，往往使用歐式距離進行計算，初始以空間中隨機k個點為中心進行聚類，對最靠近他們的對象歸類，通過迭代的方法，逐次更新各聚類中心，直至得到最好的聚類結果；

現有方法三：譜聚類，建立在譜圖理論基礎上，根據給定的樣本數據集定義一個描述成對數據點相似度的拉普拉斯矩陣，并且計算矩陣的特征值和特征向量，然后選擇合適的特征向量聚類不同的點。其本質是將聚類問題轉化為圖的最優劃分問題，是一種點對聚類算法。

隨著即時通信的不斷發展，演變社交網絡的研究也越來越引起社交媒體挖掘的研究者的關注，主要針對演變網絡的聚類方法有：

現有方法四：演變聚類算法，Chakrabarti在2006年最先提出的演變社交網絡，并提出了一種時間平滑性框架。時間平滑性框架的是使任意時刻聚類表現的盡可能的好，并且使聚類在時間上具有平滑性。演變聚類算法就是將當前時間的聚類，跟歷史的聚類做比較得出偏差，利用時間平滑框架中的時間懲罰因子做計算，最終得出當前時刻的聚類結果。