不確定圖上極大團枚舉算法研究.pdf

1、給定一個數(shù)據(jù)圖G，團是G中的一個子圖，滿足任意兩節(jié)點之間存在邊，極大團是不被其他團包含的團。極大團枚舉問題研究如何從給定圖中挖掘所有極大團，廣泛應(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)有基于不確定圖的極大團枚舉方法，發(fā)現(xiàn)現(xiàn)有算法存在效率低及擴展性差的問題。⑵提出一種基于子圖劃分的不確定圖上極大團

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