[發(fā)明專利]一種社交網(wǎng)絡(luò)中的動態(tài)社區(qū)檢測方法

有效

• 申請?zhí)枺?/td>: 201310725401.9
• 申請日: 2013-12-25
• 公開（公告）號: CN103678671A
• 公開（公告）日: 2014-03-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ò)中的動態(tài)社區(qū)檢測方法。

背景技術(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)域。

現(xiàn)有的社區(qū)檢測方法多是基于靜態(tài)社會網(wǎng)絡(luò)，即認(rèn)為社會網(wǎng)絡(luò)中節(jié)點集合和邊集合是不變的，社區(qū)結(jié)構(gòu)也是穩(wěn)定不變的。這些方法可以大致分為兩大類：基于優(yōu)化的方法和啟發(fā)式的方法。前者通過最優(yōu)化預(yù)定義的目標(biāo)函數(shù)來檢測社區(qū)結(jié)構(gòu)，如譜方法將社區(qū)檢測問題轉(zhuǎn)化為二次型優(yōu)化問題。啟發(fā)式方法是將問題轉(zhuǎn)化為預(yù)定義啟發(fā)式規(guī)則設(shè)計問題，如Girvan-Newman的啟發(fā)式規(guī)則是尋找邊界數(shù)最大的邊，然后依次刪除；MFC則是通過計算最小截集識別社區(qū)間連接，HITS的啟發(fā)式規(guī)則是基于權(quán)威-中心頁面間相互指向的連接關(guān)系。此外，社區(qū)檢測的另一個思路是采用K-MEANS、DBSCAN等經(jīng)典聚類方法對網(wǎng)絡(luò)進(jìn)行聚類，形成社區(qū)結(jié)構(gòu)。這類方法對參數(shù)敏感，且需要社區(qū)數(shù)量的先驗知識。隨著社會網(wǎng)絡(luò)規(guī)模日益龐大，傳統(tǒng)社區(qū)檢測方法的時間復(fù)雜度過高，難以滿足社區(qū)檢測的應(yīng)用要求，出現(xiàn)了一種較為高效的社區(qū)檢測方法：標(biāo)簽傳播方法。標(biāo)簽傳播方法初始階段給每個節(jié)點賦予唯一標(biāo)簽，在每一輪迭代中，每個節(jié)點根據(jù)其最多鄰居擁有的標(biāo)簽更新自己的標(biāo)簽。標(biāo)簽傳播方法可以獲得接近線性的時間復(fù)雜度，運(yùn)行效率高，但是應(yīng)用于大規(guī)模網(wǎng)絡(luò)中還存在穩(wěn)定性問題。

實際中的社交網(wǎng)絡(luò)呈動態(tài)特性，即社交網(wǎng)絡(luò)的結(jié)構(gòu)是隨時間的變化而變化的，不斷有節(jié)點加入、退出，因此動態(tài)社區(qū)檢測在實際應(yīng)用中具有更重要的價值。如果當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化時都采用靜態(tài)方法進(jìn)行社區(qū)檢測，不僅容易在相鄰時刻網(wǎng)絡(luò)上產(chǎn)生具有較大差異的社區(qū)發(fā)現(xiàn)結(jié)果，而且對大量節(jié)點進(jìn)行沒有必要的重復(fù)檢測，導(dǎo)致較高的時間復(fù)雜度Yu-Ru等提出一種成為FacetNet的動態(tài)社區(qū)劃分框架，將社區(qū)檢測和社區(qū)進(jìn)化融為一體，時刻的社區(qū)結(jié)構(gòu)由歷史社區(qū)劃分提供先驗分布結(jié)合當(dāng)前時刻網(wǎng)絡(luò)拓?fù)錄Q定當(dāng)前社區(qū)結(jié)構(gòu)，生成社區(qū)采用stochastic?block模型，在不同時刻網(wǎng)絡(luò)劃分中社區(qū)之間的匹配問題采用一種迭代的EM方法，但FacetNet依賴網(wǎng)絡(luò)社區(qū)數(shù)目的先驗知識，而社區(qū)數(shù)目在實際情況中很難準(zhǔn)確獲取。FacetNet在大型網(wǎng)絡(luò)中，需要多次迭代才能使矩陣收斂，不適合大規(guī)模數(shù)據(jù)的處理。

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

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

本發(fā)明的目的在于提供一種社交網(wǎng)絡(luò)中的動態(tài)社區(qū)檢測方法，該方法有利于提高社區(qū)檢測的精度和效率。

為實現(xiàn)上述目的，本發(fā)明的技術(shù)方案是：一種社交網(wǎng)絡(luò)中的動態(tài)社區(qū)檢測方法，包括以下步驟：

步驟A：獲取社交網(wǎng)絡(luò)一時刻t_i-1的快照數(shù)據(jù)，作為初始的社交網(wǎng)絡(luò)快照，并構(gòu)造以社交網(wǎng)絡(luò)用戶為節(jié)點、用戶關(guān)系為邊的社交網(wǎng)絡(luò)圖G_i-1=(V_i-1,?E_i-1)，V_i-1表示時刻t_i-1的社交網(wǎng)絡(luò)圖G_i-1的節(jié)點集合，E_i-1表示時刻t_i-1的社交網(wǎng)絡(luò)圖G_i-1的邊集合；

步驟B：對于時刻t_i-1的社交網(wǎng)絡(luò)圖G_i-1，進(jìn)行社區(qū)劃分，獲得社交網(wǎng)絡(luò)在時刻t_i-1的社區(qū)結(jié)構(gòu)；