[發(fā)明專利]一種社交網(wǎng)絡(luò)中的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法

有效

• 申請?zhí)枺?/td>: 201410034425.4
• 申請日: 2014-01-24
• 公開（公告）號: CN103729475B
• 公開（公告）日: 2016-10-26
• 發(fā)明（設(shè)計）人: 陳羽中;陳國龍;郭文忠;施松
• 申請（專利權(quán)）人: 福州大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 福州元創(chuàng)專利商標(biāo)代理有限公司 35100
• 代理人: 蔡學(xué)俊

技術(shù)領(lǐng)域

本發(fā)明涉及社交網(wǎng)絡(luò)技術(shù)領(lǐng)域，特別是一種社交網(wǎng)絡(luò)中的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法。

背景技術(shù)

從社會網(wǎng)絡(luò)中檢測社區(qū)結(jié)構(gòu)是社會網(wǎng)絡(luò)分析中的一項重要任務(wù)，無論是理論上還是實際應(yīng)用中都具有十分重要的意義。通過挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，能夠發(fā)現(xiàn)網(wǎng)絡(luò)中隱含的組織結(jié)構(gòu)信息、社會功能以及社區(qū)成員之間隱含的有趣屬性，如共同愛好等。通過研究社會網(wǎng)絡(luò)中社區(qū)之間、個體之間以及個體與社區(qū)之間的關(guān)系，可以挖掘出大量有價值的信息，可應(yīng)用于許多領(lǐng)域。

針對社區(qū)發(fā)現(xiàn)，已經(jīng)出現(xiàn)了很多經(jīng)典的方法。2002年Girvan和Newman基于邊介數(shù)，提出GN方法，并最早提出模塊度Q值作為網(wǎng)絡(luò)社區(qū)劃分結(jié)果好壞的指標(biāo)。?總體上，社區(qū)發(fā)現(xiàn)的經(jīng)典方法包括模塊度優(yōu)化算法、譜分析法、信息論方法以及標(biāo)簽傳播方法等。在上述方法中，節(jié)點只能屬于一個社區(qū)，但是真實的社會網(wǎng)絡(luò)的社區(qū)往往是相互重疊的，即允許節(jié)點屬于多個社區(qū)，如在一個社交網(wǎng)站上，一個用戶會擁有多個朋友圈；科研工作者的研究領(lǐng)域經(jīng)常存在交叉；在生物系統(tǒng)中，一種蛋白質(zhì)通常存在于多種復(fù)合物。Palla,?G.等基于CPM(Clique?Percolation?Method)思想，提出用于重疊社區(qū)發(fā)現(xiàn)的CFinder方法。方法將社區(qū)定義為相互連通的k-派系構(gòu)成的集合，歸屬于多個k-派系社區(qū)的節(jié)點即為社區(qū)間的重疊節(jié)點，之后通過節(jié)點社區(qū)歸屬情況輸出重疊社區(qū)，該方法適用于社區(qū)內(nèi)聚強的網(wǎng)絡(luò)，難以應(yīng)用在情況復(fù)雜的大規(guī)模復(fù)雜網(wǎng)絡(luò)。Ahn等基于邊劃分的思想，將原始網(wǎng)絡(luò)中的邊映射成新的網(wǎng)絡(luò)的節(jié)點，再利用非重疊社區(qū)發(fā)現(xiàn)方法劃分轉(zhuǎn)換后的網(wǎng)絡(luò)，則原始網(wǎng)絡(luò)中連接不同社區(qū)的邊的節(jié)點即為重疊節(jié)點。Lancichinetti等利用局部優(yōu)化及拓展的方法，隨機選取種子節(jié)點集合，種子節(jié)點根據(jù)局部優(yōu)化策略不斷向外擴張，直至獲得評價函數(shù)最大的社區(qū)，但是方法對優(yōu)化函數(shù)以及種子節(jié)點的選擇敏感且算法時間復(fù)雜度在最壞情況下為O(n2)。考慮到節(jié)點與社區(qū)之間的隸屬度，Zhang等利用譜分析法將圖映射到低維的歐幾里得空間，利用模糊C均值聚類進行重疊社區(qū)發(fā)現(xiàn)，該方法需要每個節(jié)點的隸屬向量的維數(shù)做為算法參數(shù)。

上述重疊社區(qū)發(fā)現(xiàn)算法通常存在參數(shù)敏感或者時間復(fù)雜度高的問題，難以應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，Raghavan等提出標(biāo)簽傳播方法用于社區(qū)發(fā)現(xiàn)，該算法具有線性時間復(fù)雜度，但是只能用于非重疊社區(qū)發(fā)現(xiàn)。LPA的一些擴展方法如COPRA、SLPA、MLPA等允許一個節(jié)點擁有多個標(biāo)簽，可用于重疊社區(qū)發(fā)現(xiàn)，但是上述方法的魯棒性有待提高，當(dāng)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)不明顯或社區(qū)之間的重疊程度較高時，社區(qū)挖掘精度大大降低

綜上，現(xiàn)有的社會網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法從發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)質(zhì)量以及時間效率上看都尚有很大的提升空間。面對大規(guī)模社交網(wǎng)絡(luò)的場景，現(xiàn)有方法無論實在效果和效率上都難以滿足要求。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種社交網(wǎng)絡(luò)中的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法，該方法有利于提高社區(qū)檢測的精度和效率。

為實現(xiàn)上述目的，本發(fā)明的技術(shù)方案是：一種社交網(wǎng)絡(luò)中的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法，包括以下步驟：

步驟A：讀取社交網(wǎng)絡(luò)數(shù)據(jù)，構(gòu)造以社交網(wǎng)絡(luò)用戶為節(jié)點，用戶關(guān)系為邊的社交網(wǎng)絡(luò)圖；

步驟B：初步社區(qū)劃分：根據(jù)社交網(wǎng)絡(luò)圖，采用綜合考慮節(jié)點中心度以及標(biāo)簽度分布約束的標(biāo)簽傳播方法進行社區(qū)發(fā)現(xiàn)，獲得非重疊社區(qū)結(jié)構(gòu)；

步驟C：節(jié)點層級標(biāo)記：根據(jù)初步社區(qū)劃分獲得的非重疊社區(qū)結(jié)構(gòu)以及節(jié)點在所屬社區(qū)的中心度值，標(biāo)記節(jié)點所屬的層級；

步驟D：重疊社區(qū)細(xì)化：根據(jù)節(jié)點所屬的層級，計算不同層級節(jié)點之間的標(biāo)簽傳播增益，并利用多標(biāo)簽傳播進行重疊節(jié)點挖掘，得到社交網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)。

進一步地，所述步驟B中，社交網(wǎng)絡(luò)的初步社區(qū)劃分具體包括以下步驟：

步驟B1：根據(jù)社交網(wǎng)絡(luò)圖，進行節(jié)點標(biāo)簽初始化，為社交網(wǎng)絡(luò)圖中的每個節(jié)點分配一個全局唯一的標(biāo)簽號；

步驟B2：根據(jù)標(biāo)簽更新規(guī)則，對社交網(wǎng)絡(luò)圖中的每個節(jié)點進行標(biāo)簽更新，同時根據(jù)鄰居節(jié)點信息更新節(jié)點的中心度值，反復(fù)迭代，直到滿足迭代終止條件；

步驟B3：根據(jù)迭代終止時節(jié)點所分配的標(biāo)簽，將具有相同標(biāo)簽的節(jié)點歸屬到同一社區(qū)，輸出非重疊社區(qū)結(jié)構(gòu)。

進一步地，所述步驟B2中，綜合考慮了節(jié)點中心度與標(biāo)簽度分布差異約束條件，進行標(biāo)簽更新，標(biāo)簽更新規(guī)則為：