動態異質大圖匹配模型及算法研究

《動態異質大圖匹配模型及算法研究》是依託武漢大學，由祝園園擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：動態異質大圖匹配模型及算法研究
• 項目類別：青年科學基金項目
• 項目負責人：祝園園
• 依託單位：武漢大學

項目摘要

圖結構被廣泛套用於多種領域，以描述事物之間的複雜關係。隨著圖的大量產生和積累，圖處理技術成為眾多學者和業界人士的研究熱點。圖匹配問題是圖處理技術中的重要研究內容，其目標是確定兩個圖頂點之間的對應關係，以儘可能地保留它們的公共部分。目前很多套用領域的圖數據呈現異質、大規模、動態變化的特性，而現有的圖匹配算法主要針對靜態同質圖且計算複雜度過高，無法解決具有上述特性的異質大圖匹配問題，這給研究者帶來新的挑戰和機遇。為此，本項目圍繞動態異質大圖匹配問題，從語義模型、匹配算法、動態更新三個方面，採用逐步推進的方式，依次研究異質大圖匹配語義模型、語義模型約束下異質大圖分散式匹配算法、異質大圖匹配結果的動態更新方法，並研製動態異質大圖匹配原型系統以驗證基礎理論研究成果的有效性和可行性。本項研究對於推動圖處理技術的進一步發展以及滿足套用領域對動態異質大圖匹配的需求，具有重要的科學意義和套用價值。

結題摘要

隨著信息技術的產生和發展，越來越多的領域產生並積累了大量的圖數據。圖數據因其固有的結構複雜性，在計算上面臨許多挑戰，成為眾多學者和業界人士的研究熱點。圖匹配以建立圖頂點之間的對應關係且最大化其公共部分為目標，是圖數據處理技術中的重要研究內容。針對目前套用領域中的圖數據呈現的異質、大規模、動態變化的特性，本項目圍繞動態異質大圖匹配問題，從語義模型、匹配算法、動態更新三個方面，採用逐步推進地方式，依次研究異質大圖匹配語義模型、語義模型約束下異質大圖分散式匹配算法、異質大圖匹配結果的動態更新方法，並將上述模型和算法在生物信息、社交網路等圖數據上進行了測試，證明了我們提出的理論和方法的可行性和有效性。在本項目的執行過程中，我們培養了兩名博士，一名碩士，並發表十餘篇論文於ICDE、DASFAA、BIBM等重要的國際學術會議和期刊上。