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

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

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

3、團(tuán)結(jié)構(gòu)或者是發(fā)現(xiàn)更真實的社團(tuán)結(jié)構(gòu)。
　　2)為了獲取社會網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的復(fù)雜度和精確度間的均衡，將層次粒化的方法引入社團(tuán)發(fā)現(xiàn)，本文提出基于鄰接?；纳鐖F(tuán)發(fā)現(xiàn)算法(AGCDA)。該算法初始時根據(jù)網(wǎng)絡(luò)中節(jié)點間的鄰接關(guān)系對網(wǎng)絡(luò)進(jìn)行初始?；缓蟛粩嗟貙W(wǎng)絡(luò)進(jìn)行層次?；钡讲粷M足?；瘲l件為止，最后在該粒度下求解非重疊社團(tuán)結(jié)構(gòu)。該算法有效地解決時間復(fù)雜度和精確度難以平衡的問題。實驗部分在基準(zhǔn)網(wǎng)絡(luò)和應(yīng)用網(wǎng)絡(luò)上進(jìn)行測試，并與經(jīng)典的社團(tuán)發(fā)現(xiàn)算

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

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