一種提高遺傳算法子圖挖掘效率的數據結構.pdf

1、目前復雜網絡上的數據挖掘大多結合子圖挖掘的算法進行分析。為了適應復雜網絡數據量大、結構復雜等特點，使用具有隨機性質的多目標遺傳算法進行子圖挖掘是一個比較理想的策略。然而，使用多目標遺傳算法進行復雜網絡的子圖挖掘存在著一個不可忽視的問題:數據量巨大導致運行速度慢，硬件資源利用效率低。過往的改進方案多數集中在算法本身，但對于不同的類型的復雜網絡，則很難有同樣的改進效果。
　　針對以上問題，本文從數據結構作為切入點，提出一種新型圖數據結

2、構:鄰接樹。鄰接樹是在鄰接表的基礎上改進而來的圖數據結構，即把鄰接表的所有頭結點和所有表結點都改用AVL樹的方式組織，從而加快數據操作的效率。基本思想可如下簡述:
　　1、頭結點用AVL樹組織后，稱為樹頭結點;表結點則稱為樹尾結點。
　　2、每一個樹頭結點都有一個指針，指向相應樹尾結點組成的樹的根結點。
　　3、樹頭結點和樹尾結點都有對應圖中頂點的相關信息，而邊權信息存放在樹尾結點。
　　4、每當有增加或刪除數據

3、的操作時，鄰接樹都進行平衡維護。
　　本文將對鄰接樹的可行性進行分析，并證明其相對于經典的圖數據結構:鄰接矩陣、鄰接表、十字鏈表，在時間和空間上的綜合效率都有明顯提高。其中時間復雜度為O(log(n2))，空間復雜度為O(n)。本文設計兩類實驗，一是隨機圖的增加、刪除、查找、修改四種操作實驗;二是針對用于子圖挖掘的多目標遺傳算法實驗。兩類實驗的結果數據和相關分析可驗證鄰接樹具有更優(yōu)的綜合效率。最后，本文總結鄰接樹的優(yōu)勢所在，并提出