[發(fā)明專(zhuān)利]一種面向有向-加權(quán)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410631672.2
• 申請(qǐng)日: 2014-11-11
• 公開(kāi)（公告）號(hào): CN104391889A
• 公開(kāi)（公告）日: 2015-03-04
• 發(fā)明（設(shè)計(jì)）人: 安健;桂小林;鄧昕宇;楊建偉;鐘華劍;陳立;田仕偉
• 申請(qǐng)（專(zhuān)利權(quán)）人: 西安交通大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 西安通大專(zhuān)利代理有限責(zé)任公司 61200
• 代理人: 陸萬(wàn)壽

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

本發(fā)明屬于群智感知服務(wù)領(lǐng)域，特別涉及一種面向有向-加權(quán)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方法。

【背景技術(shù)】

社交網(wǎng)絡(luò)的出現(xiàn)拓寬了網(wǎng)絡(luò)的邊界，使其與真實(shí)生活更加緊密地融合在一起，同時(shí)也賦予虛擬網(wǎng)絡(luò)更多和真實(shí)社交環(huán)境極為相近的特性與特征，社區(qū)結(jié)構(gòu)的存在就是比較典型的一個(gè)例子。在真實(shí)社交網(wǎng)絡(luò)中，我們每個(gè)人都有自己的社會(huì)屬性，比如職業(yè)、居住地或與他人親緣關(guān)系等等，具有相同社會(huì)屬性的人會(huì)建立更為緊密的社交關(guān)系。我們稱(chēng)這種群體內(nèi)成員之間的社會(huì)關(guān)系值遠(yuǎn)大于群體內(nèi)成員與群體外成員之間社會(huì)關(guān)系值的現(xiàn)象為存在社區(qū)結(jié)構(gòu)，符合這樣特性的群體則被稱(chēng)為社區(qū)。

相似地，社交網(wǎng)絡(luò)中也有類(lèi)似的現(xiàn)象，也存在社區(qū)結(jié)構(gòu)。社區(qū)結(jié)構(gòu)的意義在于能夠幫助我們更加清晰的認(rèn)識(shí)到人與人社交的本質(zhì)。通過(guò)深入挖掘社交網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，我們能夠提供更為精準(zhǔn)有效的移動(dòng)感知服務(wù)。

目前已有很多關(guān)于社交網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)算法的研究。有針對(duì)全局整體的算法，如經(jīng)典的GN算法和利用堆結(jié)構(gòu)的貪婪算法，分析整個(gè)網(wǎng)絡(luò)得到劃分但是社交網(wǎng)絡(luò)龐大帶來(lái)巨大開(kāi)銷(xiāo)而且通常情況下其實(shí)只需要?jiǎng)澐志植?；也有針?duì)局部的劃分方式，如BB算法，時(shí)間空間復(fù)雜度都有降低但是因此也具有一定局限性。此外還有基于時(shí)序的算法，將互聯(lián)網(wǎng)數(shù)據(jù)和時(shí)序數(shù)據(jù)相結(jié)合，進(jìn)行區(qū)間模糊處理，基于邊鏈接系數(shù)進(jìn)行劃分等等。但是大部分的算法都是基于無(wú)向無(wú)權(quán)圖或者無(wú)向加權(quán)圖的社會(huì)關(guān)系網(wǎng)進(jìn)行研究的，而通過(guò)終端感知實(shí)際獲取到的感知信息繪制成的網(wǎng)絡(luò)是有向加權(quán)圖，這方面成熟的算法還比較少。

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

本發(fā)明的目的在于提出了一種面向有向-加權(quán)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方法，融合凝聚和搜索的思想，通過(guò)將有向圖轉(zhuǎn)換為無(wú)向圖進(jìn)行處理和分析。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用入下技術(shù)方案：

一種面向有向-加權(quán)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方法，包括以下步驟：

步驟一：根據(jù)已知社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)集合N和不同節(jié)點(diǎn)邊的方向權(quán)重w，構(gòu)造有向-加權(quán)網(wǎng)絡(luò)圖G；

步驟二：將有向-加權(quán)網(wǎng)絡(luò)圖G轉(zhuǎn)換為無(wú)向-加權(quán)網(wǎng)絡(luò)圖G'；

步驟三：對(duì)無(wú)向-加權(quán)網(wǎng)絡(luò)圖G'進(jìn)行初始化：使用權(quán)重矩陣的形式存儲(chǔ)無(wú)向-加權(quán)網(wǎng)絡(luò)圖G'中鄰居節(jié)點(diǎn)及與鄰居節(jié)點(diǎn)邊的權(quán)重，得到權(quán)重矩陣A；

步驟四：對(duì)權(quán)重矩陣A進(jìn)行歸一化處理；

步驟五：計(jì)算社區(qū)發(fā)現(xiàn)決策因子：基于歸一化后權(quán)重矩陣A，計(jì)算社區(qū)發(fā)現(xiàn)決策因子，包括節(jié)點(diǎn)活躍度，記為：H_i；社區(qū)關(guān)系強(qiáng)度，記為：I(S_k)；社區(qū)關(guān)系密度，記為：D(S_k)；社區(qū)耦合度，記為：F(S_k)；

步驟六：社區(qū)發(fā)現(xiàn)：從活躍度最大的節(jié)點(diǎn)開(kāi)始作為初始社區(qū)的起點(diǎn)，依次計(jì)算加入社區(qū)外某節(jié)點(diǎn)后社區(qū)的耦合度F'，若存在節(jié)點(diǎn)j使得F'>F或F-F'<ε，則選擇使F'-F最大或F-F'最小的節(jié)點(diǎn)加入該社區(qū)，并更新節(jié)點(diǎn)j的社區(qū)標(biāo)號(hào)以及該社區(qū)的耦合度；

步驟七：社區(qū)發(fā)現(xiàn)終止條件判斷：當(dāng)社區(qū)加入任何節(jié)點(diǎn)都會(huì)使耦合度出現(xiàn)下降時(shí)，停止擴(kuò)展該社區(qū)，認(rèn)定該社區(qū)已穩(wěn)定；選擇活躍度次之的節(jié)點(diǎn)作為新社區(qū)的起點(diǎn)，重復(fù)步驟六，直到所有節(jié)點(diǎn)均判決完畢；

步驟八：孤立節(jié)點(diǎn)處理：尋找與孤立節(jié)點(diǎn)j在原始加權(quán)-有向圖G中存在關(guān)聯(lián)的節(jié)點(diǎn)集，從關(guān)聯(lián)節(jié)點(diǎn)集中選擇與孤立節(jié)點(diǎn)邊權(quán)重差最小的節(jié)點(diǎn)作為其有效關(guān)聯(lián)節(jié)點(diǎn)，并將該孤立節(jié)點(diǎn)加入該有效關(guān)聯(lián)節(jié)點(diǎn)所屬社區(qū)。

優(yōu)選的，步驟二具體包括：節(jié)點(diǎn)i指向節(jié)點(diǎn)j的有向邊的權(quán)值記為w_ij，節(jié)點(diǎn)j指向節(jié)點(diǎn)i的有向邊的權(quán)值記為w_ji，簡(jiǎn)化后加權(quán)圖中節(jié)點(diǎn)i和節(jié)點(diǎn)j之間無(wú)向邊權(quán)值記為w_ij'或w_ji'；對(duì)于有向-加權(quán)網(wǎng)絡(luò)圖G中任意兩個(gè)節(jié)點(diǎn)i和j，若去掉節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的兩條有向邊；若則將兩條有向邊變?yōu)闊o(wú)向邊，令其中，i、j表示社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)，其中，i∈N，j∈N；S_k表示網(wǎng)絡(luò)中的不同社區(qū)，其中k∈C，C為網(wǎng)絡(luò)中社區(qū)數(shù)集合；w為節(jié)點(diǎn)間邊的權(quán)重，節(jié)點(diǎn)i指向節(jié)點(diǎn)j的有向邊的權(quán)值記為w_ij，節(jié)點(diǎn)j指向節(jié)點(diǎn)i的有向邊的權(quán)值記為w_ji。

優(yōu)選的，步驟三中使用權(quán)重矩陣的形式存儲(chǔ)無(wú)向-加權(quán)網(wǎng)絡(luò)圖G'中鄰居節(jié)點(diǎn)及與鄰居節(jié)點(diǎn)邊的權(quán)重，如下表示形式：A＝(a_ij)，其中a_ij＝a_ji＝w_ij'；