本發(fā)明涉及一種基于社交網(wǎng)絡有向圖的社區(qū)發(fā)現(xiàn)方法，根據(jù)三角形的不同類型，提取出其特征，并將其量化作為點與點之間的邊權值；然后直接將有向無權圖轉化為無向有權圖，再用改進的標簽傳播算法來進行社區(qū)發(fā)現(xiàn)。本發(fā)明不僅能解決社交網(wǎng)絡中傳統(tǒng)社區(qū)發(fā)現(xiàn)算法不適用于有向圖的問題，并且通過算法改進，能極大地提高社區(qū)劃分的準確性。

技術領域

本發(fā)明涉及社區(qū)發(fā)現(xiàn)的技術領域，尤其涉及到一種基于社交網(wǎng)絡有向圖的社區(qū)發(fā)現(xiàn)方法。

背景技術

隨著微博、微信、Facebook等社交網(wǎng)絡的普及，社交網(wǎng)絡在用戶互聯(lián)網(wǎng)生活中占的比重越來越大。對社交網(wǎng)絡產(chǎn)品運營者而言，通過用戶畫像提取用戶特征，為用戶提供個性化服務，是當前的熱門話題。社區(qū)發(fā)現(xiàn)是目前用戶畫像中的一種重要特征提取方法。對用戶的社交網(wǎng)絡進行社區(qū)發(fā)現(xiàn)，劃分出不同好友圈子，就可以知道用戶的社交圈子。對用戶所屬圈子進行特征畫像，又可以反過來反映出用戶的社交屬性，為用戶畫像提供特征支持。比如某個信息不全的用戶，我們?yōu)槠鋭澐殖鐾隆⒂H人、大學同學等圈子，其大學同學圈子全是名校畢業(yè)生，我們同樣也可以推斷出其是名校畢業(yè)生，而其同事圈子里的用戶都是高收入的領域精英，我們可以推斷出該用戶也是高收入群體。而在微博這種靠相互關注形成的社交網(wǎng)絡則更為復雜。如果我們把A關注B定義成A有一條指向B的有向邊，按這種定義方式，A與B之間就可以形成三種可能的邊，分別是A-B(A關注B)、A-B(B關注A)以及A-B(A、B互相關注)。這種方式形成的社交網(wǎng)絡是一個有向網(wǎng)絡，分析的難度會更大。

目前常用的社區(qū)發(fā)現(xiàn)算法有派系過濾算法、CNM算法、標簽傳播算法等，但是這些算法都是基于無向圖的，并不能完美適用于有向圖的社區(qū)發(fā)現(xiàn)。

發(fā)明內容

本發(fā)明的目的在于克服現(xiàn)有技術的不足，提供一種能解決社交網(wǎng)絡中傳統(tǒng)社區(qū)發(fā)現(xiàn)算法不適用于有向圖的問題且能極大地提高社區(qū)劃分準確性的社區(qū)發(fā)現(xiàn)方法。

為實現(xiàn)上述目的，本發(fā)明所提供的技術方案為：

其基于社交網(wǎng)絡中最重要的結構—三角形。若A與B認識，且A、B有共同好友C，則這三人可夠成一個三角形，也代表他們關系較為密切。根據(jù)有向圖的有向特性，三角形如圖1所示共7種，社交網(wǎng)絡中最為重要的三角形為T2，T3，T4、T5及T6。然后，根據(jù)雙向邊的數(shù)目，分為三種類型，分別為一條雙向邊的T4、T5、T6，兩條雙向邊的T3,及三條雙向邊的T2。

根據(jù)三角形的不同類型，本方案提取出其特征，并將其量化作為點與點之間的邊權值；然后直接將有向無權圖轉化為無向有權圖，再用改進的標簽傳播算法來進行社區(qū)發(fā)現(xiàn)。

具體步驟如下：

S1、統(tǒng)計網(wǎng)絡中的三角形；

S2、計算邊權值；

S3、進行加權的標簽傳播算法。

進一步地，步驟S1統(tǒng)計網(wǎng)絡中的三角形的具體步驟為：

遍歷每條邊e_i，j，統(tǒng)計包含該邊的三角形總數(shù)t_i，j；然后分別統(tǒng)計包含該邊的T2，T3，T4、T5及T6三角形分別的數(shù)目

進一步地，步驟S2計算邊權值的具體步驟如下：

S21、根據(jù)三角形含雙向邊的數(shù)目，對三角形進行分類；

S22、對三角形類型重要性進行排序；

S23、根據(jù)三角形總數(shù)，求出重要三角形的占比：

S24、采用sigmoid函數(shù)對占比進行歸一化，公式如下：