[發明專利]實現演變點發現的社會網絡演化分析方法及系統

有效

• 申請號: 201010198329.5
• 申請日: 2010-06-11
• 公開（公告）號: CN101872359A
• 公開（公告）日: 2010-10-27
• 發明（設計）人: 楊娟;吳斌;王柏;楊勝琦;柯慶;張雷
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京弘權知識產權代理事務所(普通合伙) 11363
• 代理人: 黃啟行;張文

技術領域

本發明涉及實現演變點發現的社會網絡演化分析方法及系統。

背景技術

目前數據挖掘任務處理的對象主要是單獨的數據實例，這些數據實例往往可以用一個包含多個屬性值的向量來表示，同時這些數據實例之間假設是統計上獨立的。例如，要訓練一個疾病診斷系統，它的任務是診斷一個被試者是否患有某種傳染病，通常的做法是用一個向量來表示一個被試者，同時假設各被試者之間的患病情況是相互獨立的，即知道一個確診病人對于診斷其他被試者是否患病不能提供任何幫助。直觀經驗告訴我們這種假設是不合理的，一個人的親戚、朋友患有此傳染病，則他相對其他人有更大的可能性患病。在社會里，人與人不是簡單的統計上獨立的采樣點，他們之間必然存在著聯系和影響，忽視了這種聯系會對整個診斷系統的性能帶來很大的影響。為了解決這個問題，必須將數據實例之間的關系同時考慮進來，從而提出了社會網絡的概念，可以用圖結構來刻畫社會結構。

社會網絡包括很多節點和連接這些節點的一種或多種特定的鏈接。其中，節點往往表示了個人、團體、人、文章和/或服務器等物理存在的實體；鏈接則表示節點之間存在的各種關系，如朋友關系、親屬關系、貿易關系、引用關系等。社會網絡除了圖結構表示之外，還有其他社會學形式和代數形式的表示方式。

在很多情況下，鏈接隨著時間不斷改變，那么對社會網絡的分析需要對一段時間內的社會網絡變化情況進行分析，目前，主要是將分析的時間段等分后進行分段分析即增量分析。然而，在實際情況中，事物的發生發展不是均勻的，增量分析方法無法準確分析出社會網絡中的噪聲和事件，其中，噪聲是指與社會網絡分析主題無關的聯系，主要由具有社會化特征的個體行為的隨機性和不確定性造成的，例如撥錯電話號碼而造成的無效通話；事件是指與社會網絡分析主題相關的異常聯系，例如人們在春節期間的通話。增量分析方法，一方面，可能會在分析過程中放大噪聲，或者往往無法捕捉該時間段中對事物發展產生重大變化的演變點(即事件)，從而無法提供準確的分析結果。

發明內容

因此，本發明的目的在于提供實現演變點發現的社會網絡演化分析方法及系統，從而可以提供準確的分析結果。

為實現本發明的上述目的，提供一種實現演變點發現的社會網絡演化分析方法，包括：

按照時間順序計算相鄰兩個社會網絡之間的相似度；

根據計算結果求出相似度的突變點，即演變點；

將相鄰突變點之間的社會網絡快照選擇疊加，形成相應時間段的社會網絡拓撲圖，其中，所述相應時間段的社會網絡拓撲圖與相鄰突變點的平均距離最小，社會網絡快照為根據最小粒度劃分的一系列社會網絡；

根據所述社會網絡拓撲圖進行聚類和關聯分析。

優選地，其中，所述計算相鄰兩個社會網絡之間的相似度包括：

計算相鄰兩個社會網絡之間的距離，所述兩個社會網絡之間的距離與所述兩個社會網絡之間的相似度成反比。

優選地，其中，所述計算相鄰兩個社會網絡之間的距離還包括：

在計算過程中忽略噪聲節點，所述噪聲節點為只在單一時刻出現過的節點

優選地，其中，所述計算相鄰兩個社會網絡之間的相似度包括：

采用滑動窗口對社會網絡中的節點進行分類，分別得到離網節點、入網節點和穩定節點，其中，所述離網節點為變化點后不再出現的節點，所述入網節點為變化點后新入網的節點，所述穩定節點為變化點前后均出現的節點；

根據離網節點相似度的變化情況，計算變化點兩側離網節點的變化值；

根據入網節點相似度的變化情況，計算變化點兩側入網節點的變化值；

根據穩定節點相似度的變化情況，計算變化點兩側穩定節點的變化值；

累計離網節點的變化值、入網節點的變化值和穩定節點的變化值，得到變化點及對應的變化值。

優選地，所述根據計算結果求出相似度的突變點包括：

根據所有變化點及對應的變化值形成時間軸；

根據所述時間軸求出相似度的突變點，即得到演變點。

優選地，其中，所述將相鄰突變點之間的社會網絡快照選擇疊加包括：

對所述時間軸歸一化處理，產生用于線性分段的基準；

采用所述滑動窗口找出相對于所述基準的較高值和較低值；

裁剪所述較高值以及平滑所述較低值得到平穩時間段的社會網絡。

本發明還提供一種實現演變點發現的社會網絡演化分析系統，其特征在于，該系統包括：

計算單元，用于按照時間順序，計算相鄰兩個社會網絡之間的相似度；

突變單元，用于根據計算結果，求出相似度的突變點；