[發明專利]一種結構聚類的生成方法及系統

有效

• 申請號: 201710232898.9
• 申請日: 2017-04-11
• 公開（公告）號: CN107103333B
• 公開（公告）日: 2020-06-30
• 發明（設計）人: 陳亞中;李榮華;代強強;李振軍;張偉鵬
• 申請（專利權）人: 深圳大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 深圳市恒申知識產權事務所(普通合伙) 44312
• 代理人: 王利彬

本發明適用于數據處理技術領域，提供了一種結構聚類的生成方法，包括：接收待處理的無向無權簡單圖并遍歷得到所有未處理的結點，按照結構相似性并行算法判斷當前未處理的結點是否為核心結點，若是則生成新的聚類并編號，并將當前未處理的結點所有未處理且直接可達的鄰居插入預置隊列，判斷預置隊列是否為空，若不為空則彈出預置隊列的隊首元素，將隊首元素劃分至新的聚類，并將隊首元素的所有可達且未處理的鄰居插入預置隊列中；判斷無向無權簡單圖中是否存在未處理的結點，若不存在，則結束算法，得到目標聚類。本發明實施例通過并行算法，提高了計算的時間效率。

技術領域

本發明屬于數據處理技術領域，尤其涉及一種結構聚類的生成方法及系統。

背景技術

隨著信息技術的快速發展，各種真實的網絡所形成的圖數據隨處可見。例如社交網絡、通信網絡以及生物網絡。每種網絡中都包含對應的社區結構，發現這些隱含的社區結構在現實生活中意義重大并且有很多的應用。如在生物網絡中，一個社區可能代表具有相同性質的分子。在社交網絡中，一個社區可能代表著關系比較緊密的團體。

另外，隨著硬件技術的發展，硬件在大多數應用上已經不是主要的瓶頸，尤其是各種高性能計算機的快速發展。如何利用這些高性能計算機設計高效的算法(高性能計算)已經吸引了眾多學者的研究，尤其是對大數據的處理。這其中主要包括基于多臺計算機的MapReduce算法和基于openMP以及MPI框架的多核算法的研究。

圖的聚類是發現這些社區的一個重要的手段。在過去十年里，針對圖的聚類，研究人員提出了大量的模型和相關的算法。向我們展示了一個圖的聚類和社區的檢測算法。在這些算法中，SCAN算法(Structural Clustering Algorithm on Networks，圖的結構聚類算法)是一個非常卓越的模型，并且在實際應用中取得了很好的效果。相對于其他的圖的聚類算法，SCAN不僅能夠找到圖中的社區還能發現邊界點(outliers)和橋結點(hubs)。

SCAN算法思想和基于密度聚類的DBCSAN算法(Density-Based SpatialClustering of Applications with Noise，基于密度的聚類算法)很相似。具體地說，SCAN算法首先定義了圖中邊的兩個結點的結構相似性。如過一條邊的結構相似性大于給定的閾值ε，就會保存它，若否則刪除。最終，當與某個結點相關聯的并且滿足結構相似性的邊的個數為設置的閾值k時，稱該結點為一個核心點。然后該算法從該核心點出發，不斷的擴展，從而得到其中一個聚類。從這個過程可以發現，在算法的執行過程中，需要計算這個圖中所有邊的結構相似性。在現實世界的網絡中，一個圖有上億條邊甚至超過十億條邊，處理如此大的圖數據，現有技術采用的方法為使用基于多臺機器的MapReduce算法實現。MapReduce主要是基于分布式存儲的方式，讓多臺計算機共同完成一個龐大的任務，多臺計算即處理同一事物，必然涉及到不同計算機之間的數據交換，同時，因為圖的邊的數量龐大，SCAN算法在大規模圖數據中計算每條邊的結構相似性時存在耗時的問題。

發明內容

本發明所要解決的技術問題在于提供一種結構聚類的生成方法及系統，旨在解決現有SCAN算法在大規模圖數據中計算每條邊的結構相似性時存在耗時的問題。

本發明是這樣實現的，一種結構聚類的生成方法，包括：

接收待處理的無向無權簡單圖，遍歷所述無向無權簡單圖得到所有未處理的結點；

按照結構相似性并行算法判斷當前未處理的結點是否為核心結點，若否，則判斷下一未處理的結點是否為核心結點；

若是，則生成新的聚類并編號，并將所述當前未處理的結點的所有未處理且直接可達的鄰居插入預置隊列；

判斷所述預置隊列是否為空，若為空，則執行所述按照結構相似性并行算法判斷當前未處理的結點是否為核心結點的步驟；