[發明專利]一種基于知識圖譜的家族布局方法

在審

• 申請號: 202111505757.2
• 申請日: 2021-12-10
• 公開（公告）號: CN114218353A
• 公開（公告）日: 2022-03-22
• 發明（設計）人: 付彬彬;賀珊
• 申請（專利權）人: 武漢眾智數字技術有限公司
• 主分類號: G06F16/33
• 分類號: G06F16/33;G06F16/36
• 代理公司: 北京匯澤知識產權代理有限公司 11228
• 代理人: 吳靜

一種基于知識圖譜的家族布局方法，包括：計算家族關系圖譜中節點代差；設置層級間距和節點間距；根據節點代數確定層級并排序，對相同層級的節點進一步排序和劃分；從根層級開始依次計算節點位置。本發明通過家族布局可最大程度減少節點重疊，邊交叉的問題，對關系圖譜一目了然。解決了現有技術中，對于一些特殊的數據，力導向算法生成的圖布局并不能達到理想的效果的問題。

技術領域

本發明涉及的是數據挖掘領域，特別涉及一種基于知識圖譜的家族布局方法。

背景技術

知識圖譜以圖的形式描述客觀世界中實體及其之間的關系，通過圖形和色彩將關鍵數據和特征直觀地傳達出來，從而實現對于相當稀疏而又復雜的數據集的深入洞察，通過一目了然的方式，幫助開發者或用戶獲得客觀數據層面的引導或者驗證。

隨著數據量爆炸式增長，數據類型增多，數據間關系越來越復雜，針對各式各樣的數據生成合理的圖布局的難度逐漸變大，圖可視化的質量也受到影響，在圖形可視化中會出現節點重合、邊交叉等問題，使布局不美觀，易造成視覺負擔，因此圖可視化領域中的很多研究內容是圖布局算法，最具代表性的是力導向算法，還有很多改進算法都是以力導向算法為基礎進一步發展的。雖然大多數的數據都適用力導向算法的圖布局，但對于一些特殊的數據，力導向算法生成的圖布局并不能達到理想的效果。因此，針對特殊數據的布局算法具有很高的研究價值。

發明內容

鑒于上述問題，提出了本發明以便提供一種克服上述問題或者至少部分地解決上述問題的一種基于知識圖譜的家族布局方法。

為了解決上述技術問題，本申請實施例公開了如下技術方案：

一種基于知識圖譜的家族布局方法，包括：

S100.計算家族關系圖譜中節點代差；

S200.設置層級間距和節點間距；

S300.根據節點代數確定層級并排序，對相同層級的節點進一步排序和劃分；

S400.從根層級開始依次計算節點位置。

進一步地，計算家族關系圖譜中節點代差的具體方法為：從起點出發遍歷圖中每一個節點，并根據起點和上一個節點之間的家族關系匹配數據字典，以此來確定節點代數關系。

進一步地，若遍歷查找到的節點C與上一個節點P是長輩關系，節點C代數＝節點P代數-1，如果節點C和節點P是同輩關系，節點C代數＝節點P代數，如果節點C和節點P是長幼關系，節點C代數＝節點P代數+1。

進一步地，根據節點代數確定層級并排序，對相同層級的節點進一步排序和劃分，具體包括：對于根層級節點，查找當前層級有直接連線的節點，并修改其排序屬性值，使兩節點相鄰，對于其它層級節點的排序規則，包括先按照上一層級節點順序在當前層級查找有直接連線的節點，使這些節點在有連線的上一層節點正下方，再在這些節點中查找有直接連線的節點，使兩節點相鄰，最后將與上層節點無連線的節點調整到與當前層級有連線的節點相鄰。

進一步地，查找有直接連線的節點，使其排序相鄰的具體方法包括：

定義新的節點數組N和標記數組F；遍歷給定的所有節點，判斷該節點A是否被訪問標記過，若沒有則添加進數組N中，并初始化該節點左、右直接連接點數為0，且在數組F中標記節點A；獲取與節點A層級相同的入度和出度節點數組R，從節點A的下一個節點開始二次遍歷所有節點，若節點數組R中包含該節點B，則表示節點B與節點A有直接連線，則節點B按照節點A左、右連接點數插入數組N中，如果節點A左邊連接點數小于右邊，則節點B插入節點A的左邊，反之插入節點A右邊，并使節點A和節點B的左邊或右邊連接點數增加1，且在標記數組中標記節點B；全部遍歷完成后對節點數組N按照順序修改排序屬性值。