[發(fā)明專利]一種基于邊圖隨機游走的重疊社區(qū)發(fā)現(xiàn)方法

有效

• 申請?zhí)枺?/td>: 201510046401.5
• 申請日: 2015-01-29
• 公開（公告）號: CN104537126B
• 公開（公告）日: 2017-12-01
• 發(fā)明（設計）人: 鄧曉衡;李更好;桂勁松;劉安豐;沈海瀾;李登
• 申請（專利權）人: 中南大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中南大學專利中心43200
• 代理人: 胡燕瑜

技術領域

本發(fā)明屬于復雜網(wǎng)絡領域，具體涉及一種基于邊圖隨機游走的重疊社區(qū)發(fā)現(xiàn)方法。

背景技術

在網(wǎng)絡理論的研究中，復雜網(wǎng)絡是由數(shù)量巨大的節(jié)點和節(jié)點之間錯綜復雜的關系共同構成的網(wǎng)絡結構。用數(shù)學的語言來說，就是一個有著足夠復雜的拓撲結構特征的圖?，F(xiàn)實世界中包含著各種類型的復雜網(wǎng)絡，如社會網(wǎng)絡(朋友關系網(wǎng)絡及合作網(wǎng)絡等)、技術網(wǎng)絡(萬維網(wǎng)以及電力網(wǎng)等)、生物網(wǎng)絡(神經(jīng)網(wǎng)絡、食物鏈網(wǎng)絡以及新陳代謝網(wǎng)絡等)。人以群分，物以類聚，社區(qū)是社會網(wǎng)絡一個非常重要的特征。社區(qū)是從一個中觀的角度來研究網(wǎng)絡，它分析的不是每一個節(jié)點的特性，而是網(wǎng)絡中的某一部分的特性。往往社區(qū)內部成員之間會存在大量的信息和行為的交互，而社區(qū)之間的交互就會比較少。

傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法，大多是將網(wǎng)絡的節(jié)點劃分到某一個社區(qū)里，它認為每個成員在社區(qū)中地位或作用是平等的。然而，真實的網(wǎng)絡中某些節(jié)點可能同時屬于多個社區(qū)，這些重疊節(jié)點在社區(qū)之間的交互中起著一定的連接作用。例如，一個人同時屬于幾個社區(qū)：其中一個是工作中的同事圈，一個是關于家庭的親人圈，還有同一興趣愛好的朋友圈等等。節(jié)點的多尺度特性決定了節(jié)點屬于的社區(qū)數(shù)，因而發(fā)現(xiàn)這些重疊的節(jié)點對于研究整個網(wǎng)絡的結構有重要意義。于是，這種重疊社區(qū)發(fā)現(xiàn)方法就很好的突破傳統(tǒng)方法的局限性，可以更有效地展示出網(wǎng)絡潛在的社區(qū)結構。

但目前的重疊社區(qū)發(fā)現(xiàn)或聚類方法，存在以下問題：(1)目前基于距離的聚類方法都只考慮了當前狀態(tài)下的網(wǎng)絡結構狀態(tài)，沒有考慮時間的變化；(2)大多數(shù)的方法僅僅考慮節(jié)點的屬性，忽略了邊對社區(qū)的影響。

發(fā)明內容

本發(fā)明的目的在于提供一種基于邊圖隨機游走的重疊社區(qū)發(fā)現(xiàn)方法，可以發(fā)現(xiàn)無向網(wǎng)絡中的重疊社區(qū)。

為實現(xiàn)上述目的，本發(fā)明所述的重疊社區(qū)發(fā)現(xiàn)方法包括以下三大步驟：

步驟1)，計算有權邊圖LG的權值矩陣H，具體步驟如下：

步驟1-1)根據(jù)復雜網(wǎng)絡中成員與成員之間的關系構建一個相互連接的無向圖G＝(V，E)，V代表成員節(jié)點的集合，E代表成員間的邊集合。假定網(wǎng)絡圖中總的節(jié)點數(shù)為N,邊數(shù)為M。A＝[a_ij]為無向圖G的鄰接矩陣，若節(jié)點i與節(jié)點j 相連，則a_ij＝1，反之a(chǎn)_ij＝0；W＝[w_ij]則為無向圖G的權值矩陣，其中w_ij表示無向邊(i，j)的權值。節(jié)點i的強度si等于與節(jié)點i相連的所有邊的權值之和，即 s_i＝∑_jw_ij。若網(wǎng)絡為無向無權圖，則W＝A，每條邊權值為1。

步驟1-2)對無向圖G中的邊進行編號，并記錄連接關系及權值，建立圖G 的關聯(lián)矩陣B。關聯(lián)矩陣B＝[b_iα]是一個N×M的矩陣，元素b_iα計算公式為：

步驟1-3)構建有權邊圖LG，計算其權值矩陣H。有權邊圖LG中M個節(jié)點代表初始無向圖G的M條邊,兩點之間的邊表示無向圖G中相應的兩條邊有公共頂點。其權值矩陣H＝[h_αβ]是一個M×M的矩陣，可以通過關聯(lián)矩陣B計算得到，計算公式為：

其中，節(jié)點的強度s_i＝∑_jw_ij＝∑_αb_iα。權值矩陣H是一個對稱矩陣且含有自環(huán)，表明隨機游走者不僅僅可以進行邊到邊的游走，還可以在一條邊的兩個端點間游走，更符合實際情況。

步驟2)，在有權邊圖LG上進行隨機游走，計算LG中節(jié)點之間的距離D，聚類獲得邊社區(qū)C_L，具體步驟如下：

步驟2-1)在有權邊圖LG上進行長度為T的隨機游走，計算并記錄每一步t (1≤t≤T)的轉移概率。其中，一步轉移概率矩陣P＝[p_αβ]由權值矩陣H計算而得，計算公式為：

步驟2-2)對T步內的轉移概率進行累加,得到無向圖G中任意兩邊的相似度σ_αβ，

其中，[P^t]_αβ表示從邊α出發(fā)經(jīng)過t步到達邊β的轉移概率。

步驟2-3)對相似度進行歸一化處理，得到無向圖G中任意兩邊的距離d_αβ，