《大規模圖中圖性質求解的低複雜度分散式算法研究》是依託華中科技大學，由華強勝擔任項目負責人的面上項目。
基本介紹
- 中文名：大規模圖中圖性質求解的低複雜度分散式算法研究
- 項目類別：面上項目
- 項目負責人：華強勝
- 依託單位：華中科技大學
中文摘要,結題摘要,
中文摘要
圖的直徑、半徑、圍長(Girth)、中心度(Centralities)及聚類係數(Clustering Coefficient)是大規模圖重要性質。大規模圖由於數據量大(PB級)和數據變化快(如拓撲變化)，如何快速求解這些圖性質是大規模圖套用核心問題。集中式算法求解這些圖性質需要立方或者亞立方時間。本項目旨在為這些圖性質求解設計線性甚至亞線性時間低複雜度分散式算法或分散式近似算法。項目不僅針對無權圖也針對有權圖。算法採用大圖主流處理系統Pregel模型，即同步通信和訊息傳遞。由於網路頻寬有限且大圖處理系統中訊息傳遞主導分散式算法運行時間，本項目採用經典的擁塞模型(CONGEST)，即限定每條鏈路(邊)僅能傳遞O(log n)位(n為大圖節點個數)大小訊息。該擁塞模型的限制是設計低複雜度分散式算法或分散式近似算法最大挑戰。本項目開展不僅對分散式算法理論研究而且對大規模圖實際套用都有重要意義。
結題摘要
圖的直徑、半徑、圍長(Girth)、中心度(Centralities)及聚類係數(Clustering Coefficient)是大規模圖重要性質。大規模圖由於數據量大(PB級)和數據變化快(如拓撲變化)，如何快速求解這些圖性質是大規模圖套用核心問題。集中式算法求解這些圖性質需要立方或者亞立方時間。本項目旨在為這些圖性質求解設計線性甚至亞線性時間低複雜度分散式算法或分散式近似算法。項目不僅針對無權圖也針對有權圖。算法採用大圖主流處理系統Pregel模型，即同步通信和訊息傳遞。由於網路頻寬有限且大圖處理系統中訊息傳遞主導分散式算法運行時間，本項目採用經典的擁塞模型(CONGEST)，即限定每條鏈路(邊)僅能傳遞O(log n)位(n為大圖節點個數)大小訊息。該擁塞模型的限制是設計低複雜度分散式算法或分散式近似算法最大挑戰。本項目開展不僅對分散式算法理論研究而且對大規模圖實際套用都有重要意義。
