[發明專利]一種用于向社會網絡演化規律異常節點判定及影響評估方法

在審

• 申請號: 201711244961.7
• 申請日: 2017-11-30
• 公開（公告）號: CN107909217A
• 公開（公告）日: 2018-04-13
• 發明（設計）人: 胡文斌;王歡;蔡新宇;楊軒;過冰峰;王思琪
• 申請（專利權）人: 武漢大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/00
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙)42222
• 代理人: 魯力

技術領域

本發明涉及計算機科學和社會網絡，定義演化規律異常節點為網絡演化過程中演化規律發生劇烈變化的節點，提出了演化規律異常節點判定方法(ANIM)和演化規律異常節點影響評估方法(EEM)。

背景技術

隨著各種在線社交應用的迅速發展，社會網絡的研究引起了越來越多的學者的關注。社會網絡是用來刻畫不同個體之間的社交關系體系(如朋友關系、郵件聯系、科研領域合作關系等)?，F有的社會網絡研究通常把目標社會網絡抽象成圖的形式，用節點表示個體，邊表示交互關系，主要目的是揭示社會網絡的結構特征、形成機制及演化規律。其中，網絡演化規律分析是社會網絡研究中的一個重要方向。在社會網絡演化的過程中，個體之間的交互關系變化往往遵循一定的演化規律，反映為社會網絡拓撲結構的變化。如今，已經有很多被廣泛接受的社會網絡演化規律，比如三元閉包、優先連接、互惠原則、同質性等。然而，在社會網絡演化過程中，各種潛在事件的發生都有可能造成社會網絡演化偏離原有的演化規律，引起社會網絡結構的重大改變，稱之為社會網絡演化異常。分析社會網絡演化異常有助于更好地了解當前社會網絡的狀態，制定經濟有效的策略應對潛在的危機、引導社會網絡健康穩定地發展。

現有的社會網絡演化異常分析方法主要有基于文本分析的方法和基于網絡特征統計的方法兩大類?；谖谋痉治龅姆椒ǎ饕菑牟煌木S度對文本數據進行挖掘，提取有價值的異常相關信息。該類方法主要面向以微博、Twitter、Facebook等文本內容充實的社交應用為基礎構建的社會網絡。然而，社交關系具有多樣化的表現形式，在許多情況下由于社交關系本身的特性或者出于保護用戶隱私考慮，無法獲取有效的文本信息，比如朋友關系網或者電話通信網。不同于基于文本分析的方法，基于網絡特征統計的方法通過計算大量的潛在的網絡特征參數，選擇合適的參數，通過分析參數的變化來分析網絡的演化狀態。該方法主要是從宏觀的角度分析整體網絡的演化，忽視了微觀節點演化的差異性。當社會網絡的宏觀演化表現異常時，部分節點的演化規律異常的同時，往往會有部分節點依然遵循原有的演化規律正常演化。Akoglu等人基于單個網絡快照，利用網絡的冪律性質發現網絡中的異常節點，由于沒有考慮社會網絡演化的連續性，不利于動態地描述節點的演化規律。Henderson等人提出了結構角色的概念，對網絡中的節點進行劃分、分析預測節點的演化行為。結構角色是指某類結構特征的組合，如星形結構的中心、完全圖的成員等就是兩種不同的角色，它們有各自獨特的節點度分布、聚集系數等特征表現。隨后，Rossi等人從潛在的網絡特征參數中選取代表性參數，通過考察節點結構角色的變化，提出了一種分析網絡及節點結構變化模式的方法，檢測結構變化、發現異常節點。然而，他們的方法的表現依賴于代表性特征參數和節點角色的選取，并且無法反映節點的演化規律的變動。受到個體的性格、教育、工作等內在屬性的影響，節點在演化過程中遵循的演化規律往往在一段時間內保持穩定。節點演化規律是節點演化行為的內在驅動力，表現為個體節點連邊的變化。當節點內在演化規律發生劇烈改變時，往往受到了某些重要事件的影響，具有寶貴的異常分析價值。在我們先前的研究中，已經嘗試從鏈路預測算法的角度去宏觀上擬合社會網絡的演化規律，通過定量地評估社會網絡不同時段的演化波動，來檢測網絡的宏觀演化規律異常。基于先前的研究工作，本發明希望進一步從微觀節點的角度分析社會網絡演化異常。本發明定義演化規律異常節點為社會網絡演化過程中演化規律發生劇烈變化的節點，提出面向社會網絡的普適方法，判定演化規律異常節點、評估演化規律異常節點的影響。

發明內容

本發明的上述技術問題主要是通過下述技術方案得以解決的：

一種用于向社會網絡演化規律異常節點判定及影響評估方法，其特征在于，包含以下步驟：

步驟1：演化規律異常節點判定方法利用鏈路預測算法間接地描述節點的演化規律，提出演化規律擬合指標，衡量不同鏈路預測算法對節點演化規律的描述程度。構建節點在不同時段的演化規律描述向量，動態全面地描述節點的演化規律，檢測節點在演化過程中的異常，判定演化規律異常節點；

步驟2：基于演化規律異常節點判定方法判定的演化規律異常節點，演化規律異常節點影響評估方法將演化規律異常節點的行為看作是對當前網絡結構的擾動，通過網絡對應的鄰接矩陣進行一階近似擾動分析，提出結構擾動指標，定量地評估演化規律異常節點對當前社會網絡結構的影響。在上述的一種用于向社會網絡演化規律異常節點判定及影響評估方法，步驟1的具體實現包含以下子步驟：