社交網(wǎng)絡(luò)中結(jié)構(gòu)洞檢測(cè)算法設(shè)計(jì)與實(shí)現(xiàn).pdf

1、社交網(wǎng)絡(luò)中連接多個(gè)不同社團(tuán)的節(jié)點(diǎn)稱為結(jié)構(gòu)洞節(jié)點(diǎn)。部分已有的結(jié)構(gòu)洞檢測(cè)方法雖然可以檢測(cè)到結(jié)構(gòu)洞節(jié)點(diǎn)，但存在一些不足。比如，已有基于網(wǎng)絡(luò)拓?fù)涞慕Y(jié)構(gòu)洞檢測(cè)算法存在精確度低，時(shí)間復(fù)雜度高、可擴(kuò)展性差的問題;在檢測(cè)結(jié)構(gòu)洞的過程中只考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)而沒有考慮網(wǎng)絡(luò)動(dòng)作日志的問題。為了高效準(zhǔn)確的檢測(cè)社交網(wǎng)絡(luò)中的結(jié)構(gòu)洞節(jié)點(diǎn)，本文的主要研究?jī)?nèi)容如下:
　　一、首先，本文提出了基于二步鄰居拓?fù)浣Y(jié)構(gòu)的一種新結(jié)構(gòu)洞檢測(cè)方法。在傳統(tǒng)有效規(guī)模度量基礎(chǔ)上提出了新

2、的結(jié)構(gòu)洞度量E-Butt，利用節(jié)點(diǎn)與其二步鄰居構(gòu)成的拓?fù)潢P(guān)系來計(jì)算節(jié)點(diǎn)的有效規(guī)模，用該結(jié)果作為結(jié)構(gòu)洞節(jié)點(diǎn)重要性的評(píng)價(jià)指標(biāo)，計(jì)算每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)洞度量值。針對(duì)結(jié)構(gòu)洞度量E-Butt，提出并實(shí)現(xiàn)結(jié)構(gòu)洞檢測(cè)算法E-B算法。E-B算法每次模擬迭代將選中的結(jié)構(gòu)洞節(jié)點(diǎn)度量值置為零，下一次迭代只計(jì)算該節(jié)點(diǎn)二步鄰居的有效規(guī)模，大大降低了時(shí)間復(fù)雜度。對(duì)算法的正確性進(jìn)行了證明，驗(yàn)證了算法的時(shí)間效率，分析算法的精確度，并與存在的經(jīng)典結(jié)構(gòu)洞檢測(cè)算法進(jìn)行對(duì)比。

3、r>　　二、其次，結(jié)構(gòu)洞占據(jù)者不僅具有控制優(yōu)勢(shì)，還有信息優(yōu)勢(shì)?；谶@種思想，本文提出了基于動(dòng)作日志的結(jié)構(gòu)洞挖掘算法，主要分為三個(gè)步驟:1、在真實(shí)數(shù)據(jù)集上收集統(tǒng)計(jì)給定網(wǎng)絡(luò)的歷史動(dòng)作日志記錄，采用關(guān)聯(lián)矩陣和動(dòng)作日志聯(lián)合建模;2、在模型學(xué)習(xí)過程中，采用擴(kuò)展的期望最大GEM算法。在真實(shí)數(shù)據(jù)集上迭代更新參數(shù)，直至收斂;通過執(zhí)行GEM算法，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)獲得一對(duì)參數(shù)，該參數(shù)對(duì)分別表示節(jié)點(diǎn)在社團(tuán)的積極參與得分和消極參與得分。3、根據(jù)參數(shù)對(duì)執(zhí)行Top