[發明專利]基于隨機游走邊界域處理的三支決策社團劃分方法及裝置

在審

• 申請號: 201811045237.6
• 申請日: 2018-09-07
• 公開（公告）號: CN109242713A
• 公開（公告）日: 2019-01-18
• 發明（設計）人: 陳潔;李洋;趙姝;段震;張燕平
• 申請（專利權）人: 安徽大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62
• 代理公司: 合肥市浩智運專利代理事務所(普通合伙) 34124
• 代理人: 丁瑞瑞

本發明公開了一種基于隨機游走邊界域處理的三支決策社團劃分方法，方法包括：1)、獲取抽象網絡；2)、對抽象網絡初始?；筮M行聚類?；?，將抽象網絡劃分成多個劃分后社團，并將劃分后社團的結構關系作為第一劃分結果；3)、獲取重疊社團模塊度最大值對應的抽象網絡的第一劃分結果；4)、利用隨機游走算法對邊界域中的所有節點進行劃分；5)、針對更新后的邊界域中的每一個節點，使用三支決策法進行處理，獲得第二劃分結果，并將第二劃分結果作為目標劃分結果。本發明公開了一種基于隨機游走邊界域處理的三支決策社團劃分裝置。應用本發明，可以提高社團劃分的精度，從而有助于分析和了解網絡結構，便于對網絡進行優化和管理。

技術領域

本發明涉及一種社團劃分方法及裝置，更具體涉及一種基于隨機游走邊界域處理的三支決策社團劃分方法及裝置。

背景技術

網絡廣泛存在于我們的現實生活中，如社會系統中的人際關系網，生物系統中的蛋白質交互網絡，計算機網絡中的萬維網和因特網等，這些網絡中的每一個個體通過信息交換通道與其它的個體連接。隨著對網絡的深入研究，人們發現許多實際網絡中都存在著社團結構，即整個網絡由若干個社團構成。例如，可以將現實中存在的網絡，如計算機網絡中的每一臺設備抽象成一個節點，而各個節點之間的網絡通道可以抽象成節點之間的邊，可以發現，每個社團內部的節點/節點之間連接相對緊密而社團之間的連接相對比較稀疏。為了實現對網絡的分析，需要根據節點之間的關聯關系，尋找聯系緊密的小型社團結構，該過程可以被稱為社團劃分或社團發現。近年來，隨著研究的深入，人們發現在進行社團劃分時經常會出現重疊部分，即一個節點可能會屬于多個社團。實際上，將重疊節點劃分到單個社團中更有助于發現社團內存在的規律，并預測網絡的行為和功能。

目前，常用的非重疊社團劃分算法，主要分為以下四種：層次聚類算法、目標函數的優化算法、網絡動力學算法和基于粒計算的社團劃分算法等，其中應用較多的非重疊社團劃分算法有基于層次?；纳鐖F發現算法、GN算法(Grivan-Newman，葛瑞安-紐曼算法)、NFA算法(Newman fast algorithm，紐曼快速算法)和LPA算法(Label PropagationAlgorithm，標簽傳播算法)等。這些現有的非重疊社團劃分算法從不同的角度和應用層面對非重疊社團的劃分進行了研究，并取得了豐碩的研究成果。

但是，這些算法對重疊部分處理時都只應用了傳統的二支決策方法，即根據已有的信息只做出接受或拒絕決策。但重疊部分的節點往往因為信息量不足無法決定其歸屬才會出現在重疊部分，如果強制做出決策，可能會影響最終非重疊社團劃分的結果。因此，現有技術中存在非重疊社團劃分結果精度不高的技術問題。

發明內容

本發明所要解決的技術問題在于提供了一種基于隨機游走邊界域處理的三支決策社團劃分方法及裝置，以提高非重疊社團劃分結果的精度。

本發明是通過以下技術方案解決上述技術問題的：

本發明實施例提供了一種基于隨機游走邊界域處理的三支決策社團劃分方法，所述方法包括：

1)、將獲取的待進行社團劃分的網絡抽象成由節點連接成的抽象網絡；

2)、針對所述抽象網絡中的每一個節點，根據所述節點的連接屬性，對所述抽象網絡初始粒化后進行聚類?；?，將聚類粒化后抽象網絡的結構關系作為第一劃分結果，其中，所述連接屬性，包括：所述節點與其它節點的連接關系；

3)、計算每一粒層分別對應的重疊社團模塊度，并獲取重疊社團模塊度最大值對應的抽象網絡的第一劃分結果，其中，所述重疊社團為，具有相同節點的社團，且粒層為對應不同的預設?；禂档牡谝粍澐纸Y果；

4)、將所述第一劃分結果中各個劃分后社團的重疊部分作為邊界域；并利用隨機游走算法對所述邊界域中的所有節點進行劃分，更新所述第一劃分結果以及所述邊界域，直至所述第一劃分結果以及所述邊界域的更新次數達到預設次數；