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

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

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

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

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

5、含在一個粒子中為止，最后在具有最大相容?；瘶藴实牧６认虑蠼夥侵丿B社團結構。該算法初始?；W絡時形成若干個極大相容粒子，其保證具有高連接密度的社團至少要包含一個極大相容粒子，因而可以更準確地發(fā)現(xiàn)接近于網絡中真實存在的社團結構。實驗部分在人工數(shù)據集和基準數(shù)據集上測試TGCDA算法的有效性，在基準數(shù)據集上，TGCDA算法可以獲得高于NFA算法17.55％的NMI精確度，同樣在人工數(shù)據集上也有所提高。因此對于具有真實社團結構的網絡，TGCDA算