不確定圖上極大團(tuán)枚舉算法研究.pdf

1、給定一個(gè)數(shù)據(jù)圖G，團(tuán)是G中的一個(gè)子圖，滿足任意兩節(jié)點(diǎn)之間存在邊，極大團(tuán)是不被其他團(tuán)包含的團(tuán)。極大團(tuán)枚舉問題研究如何從給定圖中挖掘所有極大團(tuán)，廣泛應(yīng)用于通信網(wǎng)絡(luò)，蛋白質(zhì)交互網(wǎng)絡(luò)，生物系統(tǒng)調(diào)控網(wǎng)絡(luò)以及社交網(wǎng)絡(luò)等領(lǐng)域。隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，數(shù)據(jù)來源存在差異，圖數(shù)據(jù)往往具有不確定性。
　　本研究主要內(nèi)容包括：⑴通過深入分析現(xiàn)有基于不確定圖的極大團(tuán)枚舉方法，發(fā)現(xiàn)現(xiàn)有算法存在效率低及擴(kuò)展性差的問題。⑵提出一種基于子圖劃分的不確定圖上極大團(tuán)

2、枚舉算法 EUMC。該算法首先將給定的不確定圖當(dāng)成確定圖進(jìn)行處理，得到其中的極大團(tuán)，然后基于得到的每個(gè)極大團(tuán)，結(jié)合圖中的不確定信息，枚舉其中的不確定極大團(tuán)集合。最后對枚舉得到的所有不確定極大團(tuán)按照頂點(diǎn)規(guī)模降序排序，依次驗(yàn)證每個(gè)極大團(tuán)是否被前邊的某個(gè)團(tuán)包含，剔除其中的偽極大團(tuán)，得到最終的所有不確定極大團(tuán)。⑶提出一種高效的偽極大團(tuán)驗(yàn)證算法 DPMC。在對枚舉得到的極大團(tuán)進(jìn)行排序的基礎(chǔ)上，DPMC在檢查每個(gè)極大團(tuán)是否被前邊的某個(gè)團(tuán)包含時(shí)，無需