[發明專利]一種基于決定路徑權重的不確定圖分割方法及系統

在審

• 申請號: 201510046765.3
• 申請日: 2015-01-29
• 公開（公告）號: CN104573730A
• 公開（公告）日: 2015-04-29
• 發明（設計）人: 李紅娜;劉志超;寧立;張涌
• 申請（專利權）人: 中國科學院深圳先進技術研究院
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 深圳中一專利商標事務所 44237
• 代理人: 張全文

技術領域

本發明屬于數據分析技術領域，尤其涉及一種基于決定路徑權重的不確定圖分割方法及系統。

背景技術

不確定圖是特殊的帶權圖,其上每條邊的權值為0到1之間的實數。該權值通常代表對應邊的存在概率。對于圖數據來說，不確定圖的特征不僅圖的邊以一定的概率存在，甚至節點也可以以一定的概率存在。由于不確定性無處不在，相關研究又不能忽略不確定的存在，因此業界普遍認為針對不確定圖的研究具有重要的現實意義。

然而，現有對不確定圖的研究存在以下問題：1)現實中的很多圖數據都是不確定的，不考慮圖數據的不確定性，研究的現實意義和應用價值不大；2)社會網絡中有部分是帶權的網絡，以無權網絡方式進行劃分，聚類不準確；3)大型網絡抽象的圖中節點與邊的數量非常大，計算最短路徑時只考慮一條邊的權值，不精確。

發明內容

鑒于此，本發明實施例提供一種基于決定路徑權重的不確定圖分割方法及系統，以解決現有技術存在的上述問題。

本發明實施例是這樣實現的，一種基于決定路徑權重的不確定圖分割方法，所述方法包括：

建立不確定加權圖；

以鄰接矩陣的形式對所述不確定加權圖進行存儲；

計算存儲后的所述不確定加權圖中各節點之間的決定路徑權重；

基于所述決定路徑權重，利用k-means算法對所述不確定加權圖中的節點進行劃分，獲得多個節點子集。

本發明實施例的另一目的在于提供一種基于決定路徑權重的不確定圖分割系統，所述系統包括：

不確定圖建立單元，用于建立不確定加權圖；

存儲單元，用于以鄰接矩陣的形式對所述不確定加權圖進行存儲；

決定路徑權重計算單元，用于計算存儲后的所述不確定加權圖中各節點之間的決定路徑權重；

聚類單元，用于基于所述決定路徑權重，利用k-means算法對所述不確定加權圖中的節點進行劃分，獲得多個節點子集。

本發明實施例與現有技術相比存在的有益效果是：本發明實施例針對現實網絡數據的不確定性，對現實網絡進行不確定加權圖的建立，根據所述不確定加權圖的決定路徑權重計算各個節點之間的距離并且循環更新各個節點之間的距離，直到達到最小，并利用k-means算法對所述不確定加權圖中的節點進行劃分，獲得多個節點子集。本發明實施例使用不確定圖數據更具有應用價值和現實意義，使用加權的不確定圖更能說明節點之間的關聯程度，使得對不確定圖的分割更準確。而且本發明實施例在實現上述過程中，不需要增加額外的硬件，可有效降低成本，具有較強的易用性和實用性。

附圖說明

為了更清楚地說明本發明實施例中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對于本領域普通技術人員來講，在不付出創造性勞動性的前提下，還可以根據這些附圖獲得其他的附圖。

圖1是本發明實施例一提供的基于決定路徑權重的不確定圖分割方法的實現流程圖；

圖2是本發明實施例一提供的不確定加權圖的示例圖；

圖3是本發明實施例一提供的以鄰接矩陣存儲的不確定加權圖的示例圖；

圖4是本發明實施例二提供的基于決定路徑權重的不確定圖分割系統的組成結構圖。

具體實施方式

以下描述中，為了說明而不是為了限定，提出了諸如特定系統結構、技術之類的具體細節，以便透切理解本發明實施例。然而，本領域的技術人員應當清楚，在沒有這些具體細節的其它實施例中也可以實現本發明。在其它情況中，省略對眾所周知的系統、裝置、電路以及方法的詳細說明，以免不必要的細節妨礙本發明的描述。

為了說明本發明所述的技術方案，下面通過具體實施例來進行說明。

實施例一：

圖1示出了本發明實施例一提供的基于決定路徑權重的不確定圖分割方法的實現流程，該方法過程詳述如下：

在步驟S101中，建立不確定加權圖。

在本發明實施例中，以社會網絡社區發現的經典例子Zachary網絡為起始實例建立不確定加權圖(如圖2所示)，在所述不確定加權圖中每個成員(即節點，如圖2中的V1、V2…V34)之間加上權重(如V1和V2之間的0.9)，所述權重表示各個成員之間的聯系頻繁度，權重越大表示成員之間的聯系越頻繁。

在步驟S102中，以鄰接矩陣的形式對所述不確定加權圖進行存儲。