基于層次?；纳鐖F(tuán)發(fā)現(xiàn)方法研究.pdf

1、社會(huì)關(guān)系廣泛存在于現(xiàn)實(shí)生活中，它們可以抽象成各式各樣的社會(huì)網(wǎng)絡(luò)。近些年來(lái)，研究者們發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)中存在的社團(tuán)結(jié)構(gòu)是大規(guī)模網(wǎng)絡(luò)分析和挖掘的基礎(chǔ)，對(duì)于分析社會(huì)系統(tǒng)的組織原則與動(dòng)力學(xué)特征以及預(yù)測(cè)系統(tǒng)中實(shí)體的行為具有重要的研究意義，在社會(huì)學(xué)、生物學(xué)和商業(yè)活動(dòng)中具有廣泛的應(yīng)用前景。網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的研究已成為一個(gè)具有重要社會(huì)價(jià)值及應(yīng)用價(jià)值的課題。
　　如何更快更好地發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)或者是發(fā)現(xiàn)更真實(shí)的社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)社團(tuán)研究中的關(guān)鍵問(wèn)題。本文首先研究如

2、何尋求降低社團(tuán)發(fā)現(xiàn)算法的時(shí)間復(fù)雜度和提高社團(tuán)發(fā)現(xiàn)的精確度間的平衡關(guān)系，然后給出精確地發(fā)現(xiàn)網(wǎng)絡(luò)中實(shí)際的社團(tuán)結(jié)構(gòu)的新思路。作者對(duì)上述問(wèn)題進(jìn)行相應(yīng)研究，將層次粒化方法引入社團(tuán)劃分方法中來(lái)，提出基于鄰接粒化的社團(tuán)發(fā)現(xiàn)算法(AGCDA)和基于相容?；纳鐖F(tuán)發(fā)現(xiàn)算法(TGCDA)。
　　本文的主要工作如下:
　　1)首先對(duì)社團(tuán)發(fā)現(xiàn)算法的研究現(xiàn)狀進(jìn)行詳細(xì)地調(diào)研，并分析部分經(jīng)典算法的優(yōu)勢(shì)和不足，同時(shí)將層次?；椒ㄒ氡疚闹衼?lái)更快更好地發(fā)現(xiàn)社

3、團(tuán)結(jié)構(gòu)或者是發(fā)現(xiàn)更真實(shí)的社團(tuán)結(jié)構(gòu)。
　　2)為了獲取社會(huì)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的復(fù)雜度和精確度間的均衡，將層次?；姆椒ㄒ肷鐖F(tuán)發(fā)現(xiàn)，本文提出基于鄰接?；纳鐖F(tuán)發(fā)現(xiàn)算法(AGCDA)。該算法初始時(shí)根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)間的鄰接關(guān)系對(duì)網(wǎng)絡(luò)進(jìn)行初始粒化，然后不斷地對(duì)網(wǎng)絡(luò)進(jìn)行層次粒化，直到不滿(mǎn)足粒化條件為止，最后在該粒度下求解非重疊社團(tuán)結(jié)構(gòu)。該算法有效地解決時(shí)間復(fù)雜度和精確度難以平衡的問(wèn)題。實(shí)驗(yàn)部分在基準(zhǔn)網(wǎng)絡(luò)和應(yīng)用網(wǎng)絡(luò)上進(jìn)行測(cè)試，并與經(jīng)典的社團(tuán)發(fā)現(xiàn)算

4、法進(jìn)行比較?；鶞?zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明了該算法可獲得高于LPA算法7.6％的模塊度和低于NFA算法96％的時(shí)間。因此，AGCDA算法的時(shí)間復(fù)雜度較低，獲取的社團(tuán)模塊度較高，實(shí)現(xiàn)了社團(tuán)發(fā)現(xiàn)時(shí)間和精確度的均衡，總體性能更優(yōu)。
　　3)為了更加準(zhǔn)確地發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)中真實(shí)的社團(tuán)結(jié)構(gòu)，本文提出基于相容?；纳鐖F(tuán)發(fā)現(xiàn)算法(TGCDA)。該算法初始時(shí)根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)間的相容關(guān)系對(duì)網(wǎng)絡(luò)進(jìn)行初始粒化，然后不斷地對(duì)網(wǎng)絡(luò)進(jìn)行層次粒化，直到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)包

5、含在一個(gè)粒子中為止，最后在具有最大相容粒化標(biāo)準(zhǔn)的粒度下求解非重疊社團(tuán)結(jié)構(gòu)。該算法初始?；W(wǎng)絡(luò)時(shí)形成若干個(gè)極大相容粒子，其保證具有高連接密度的社團(tuán)至少要包含一個(gè)極大相容粒子，因而可以更準(zhǔn)確地發(fā)現(xiàn)接近于網(wǎng)絡(luò)中真實(shí)存在的社團(tuán)結(jié)構(gòu)。實(shí)驗(yàn)部分在人工數(shù)據(jù)集和基準(zhǔn)數(shù)據(jù)集上測(cè)試TGCDA算法的有效性，在基準(zhǔn)數(shù)據(jù)集上，TGCDA算法可以獲得高于NFA算法17.55％的NMI精確度，同樣在人工數(shù)據(jù)集上也有所提高。因此對(duì)于具有真實(shí)社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)，TGCDA算