[發明專利]一種基于MapReduce架構的大規模圖數據聚類算法

在審

• 申請號: 201510346735.4
• 申請日: 2015-06-19
• 公開（公告）號: CN104991912A
• 公開（公告）日: 2015-10-21
• 發明（設計）人: 張海仙;章毅;王鈺
• 申請（專利權）人: 四川大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 成都弘毅天承知識產權代理有限公司 51230
• 代理人: 楊保剛;劉賢科

技術領域

本發明涉及圖數據處理技術領域，具體涉及一種基于MapReduce架構的大規模圖數據聚類算法。

背景技術

云，是對于網絡的一種比喻叫法。云計算作為一種增加和交付的模式主要應用在網絡及其相關服務方面。云計算能夠通過網絡提供虛擬化資源，這些資源不僅是動態的而且能夠被它人擴展。云計算可以提供非常強大的運算能力，其速度甚至能夠達到10萬億次/s，如此強大的計算能力對于那些需要分析大型數據的項目是非常有幫助的。例如可以將云計算應用在檢測氣候的變化和股票交易中。對于普通的用戶，云計算也很有幫助，他們可以通過網絡與云計算提供的數據中心進行連接，根據自己的需求處理他們自己的數據。云計算的特點

(1)超大規模：“云”的規模可能非常大，在全世界的IT公司中，Google的云計算資源屈指可數，據悉大約有它擁有超過100萬臺服務器。而其他如Yahoo、微軟、IBM等一些公司擁有的服務器則相對少一些，但也有幾十萬的云服務器。這些大型的IT公司擁有這么多的服務器與云計算的優點是密不可分的，正因為云計算能夠用戶提供非常強的運算能力，這些公司才如此重視這項服務。

(2)虛擬化：云計算提供的服務非常方便，用戶可以在自己的電腦或筆記本上得到該項服務。這些資源卻并不在自己的終端上，而是來自于“云”。云的存在給我們提供了極大的方便，有時我們需要完成非常龐大的計算，在以前我們可能必須通過連入超級計算機才能完成這項任務，而現在，通過云，我們只要在自己的終端上提交請求，便可以通過云計算完成任務。雖然在運行過程中，用戶可能不知道自己運行程序的詳細位置，但這絲毫不會有什么不利的影響，因為用戶同樣也可以在自己的終端上收到最后的結果。

(3)高可靠性：云計算的優點還體現在更高的可靠性方面，相對于個人計算機，云計算有著更為可靠的計算能力。

(4)通用性：云計算的應用方面非常廣，我們不必擔心云計算只提供給我們有限的特定服務。在同一個時間，云能夠同時運行多個不同的應用，并且這些應用都能夠正常運行，這是一個非常大的優點。

(5)按需服務：云提供的資源非常巨大，因此計費可能會是一個問題，但這已得到很好地解決，因為目前云服務可以像話費和網費那樣收費。

(6)極其廉價：“云“相比于其他的技術，有它特有的容錯措施。我們在構建云的時候可以使用非常廉價常用的節點，但是在它的構建如此便宜的同時，它處理任務所花費的時間又相當的短暫。作為用戶，可是充分的享受到”云“的低成本，花費少量金錢、較少時間就能完成以前消耗巨大的資源才能夠完成的任務。

圖是結構和語義方面比樹和線性表更復雜的一種數據結構。與圖相關的場景應用隨處可見，現實應用中許多情況下都需要用圖來表達。而近幾年對于一些較新的應用，如社交網絡的分析(計算實體與實體的關系)，語義的Web分析(關于Web鏈接及其結構的分析，內容的挖掘和Web日志搜索等)，生物信息分析(基因組分析及蛋白質結構分析)等，這些應用需要建立的圖的規模日漸增大，導致對大規模頂點級別圖的處理能力需求則更加急迫。所以，對大規模圖數據的處理成為目前高性能計算領域開發研究的熱點。

而在大規模圖數據的處理過程中，如何高效地發現大圖中聯系緊密的點，找出具有相似功能的功能團或者社區，這些問題更是當前研究的一個熱點。但是直接針對大規模圖數據進行聚類，對于普通用戶來說，目前還存在很多局限性，因為我們沒有google的高效系統，沒有高性能的計算機，然而MapReduce的并行架構給我們提供了更加高效的可能。

發明內容

針對上述現有技術，本發明要解決的預測群體行為并對未來趨勢進行模擬和預測，網絡中具有某種共同愛好的社區發現從而進行精準的廣告推廣等大數據而普通PC機難以處理的技術問題

為了解決上述技術問題，本發明采用如下技術方案：

一種基于MapReduce架構的大規模圖數據聚類算法，其特征在于，包括如下步驟：

①計算圖數據的鄰接矩陣A；

②計算圖的度對角矩陣D；

③計算傳遞因子；

④得到源節點傳遞一次信息后的高維表示；

⑤傳遞次數小于T時，返回第四步，否則結束并輸出結果。

所述步驟②具體包括以下步驟：

a、作為無向圖數據的度對角矩陣，相當于每行對角元素代表此行標號節點的度數，這樣的話將度對角元素直接存入一維數組中方便后續計算。