[發明專利]一種量化評價MSV的邊級視覺混雜程度指標計算方法

有效

• 申請號: 201810922471.6
• 申請日: 2018-08-14
• 公開（公告）號: CN109101628B
• 公開（公告）日: 2021-11-26
• 發明（設計）人: 趙穎;蔣昊瑾;佘燕敏;陳文江;劉家瑋;周芳芳
• 申請（專利權）人: 中南大學
• 主分類號: G06F16/958
• 分類號: G06F16/958
• 代理公司: 長沙市融智專利事務所(普通合伙) 43114
• 代理人: 歐陽迪奇

本發明公開了一種量化評價MSV的邊級視覺混雜程度指標計算方法，包括以下步驟：1)獲取MSV中的任意一條邊e，并計算其不可區分的像素距離值IPD，從邊e的中心位置向左右方向分別擴展IPD的寬度，形成不可區分的像素區域IPA；2)將IPA中與邊e相互交錯的邊加入交錯邊集合；3)對交錯邊集合按節點順序進行分解，得到若干等距且相鄰的節點對集合，利用并集操作消除重疊覆蓋，得到消除重疊覆蓋的交錯邊集合；4)根據消除覆蓋的交錯邊集合與節點對集合計算邊e的視覺混雜程度指標。本發明對MSV中邊的視覺混雜程度進行定量評價，有助于為后續邊采樣工作提供可靠依據，進而有助于減少MSV中的視覺混雜程度，提高其可讀性。

技術領域

本發明涉及動態網絡可視化中大規模序列視圖(MSV)的可視優化領域，特別涉及一種量化評價MSV的邊級視覺混雜程度指標的計算方法。

背景技術

網絡(Network)也稱作圖(Graph)，通常一切具有關系的實體都可以抽象成一個網絡(圖)，即實體被抽象成節點，實體之間的關系被抽象成邊。根據網絡是否會隨著時間發生變化，可分為靜態網絡和動態網絡。

動態網絡主要用來表示網絡中的節點及節點間關系隨時間變化的情況。為高效、直觀地幫助人們理解時變網絡的行為信息，常見的做法是通過可視化技術對動態網絡中的數據實現符合美學標準的視覺映射和布局設計。MSV是一種經典的動態網絡可視化技術，被廣泛應用于分析動態社交網絡和程序執行跟蹤。在MSV中，用水平線表示動態網絡的節點，其在縱軸上等距；用橫軸表示網絡存在的時間。當時刻t存在從節點a到b的瞬時關系，則在t的垂線位置作以a為起點，b為終點的垂線。由于MSV支持任意細粒度的可視化并可保留用戶的心理地圖，所以易于用戶從節點對到全局網絡對通信趨勢進行觀察與分析。然而，MSV容易受到可視混雜的影響。在動態網絡中，當多條邊出現在相近但不完全相同的時刻，在進行邊的繪制時，如果屏幕橫向空間無法提供足夠的像素，就會導致邊重疊引起的視覺混雜。視覺混雜會使MSV的整體可讀性下降，造成人們對網絡通信的時變趨勢理解困難。為解決該問題，一些技術對MSV做出改進。過濾技術和縮放技術提供細節和像素化的視圖來顯示選定的時間和節點，但無法對全局進行清晰描述。反鋸齒技術可以減少由于過度繪制邊緣而導致的視覺混亂，但無法優化重疊邊。彎曲連接技術可避免邊緣重疊，但是會造成邊的交叉。到目前為止，節點排序策略是改進MSV的最佳技術，但是當節點之間的通信密集且不規律時，很難得到滿意結果。并且，動態網絡的網絡結構是動態演化的，而不是如靜態網絡一樣固定不變。現有的邊采樣技術的關注點為如何均勻隨機地對靜態圖進行采樣，即采樣過程中考慮保留的是重要的靜態屬性。因此，這些邊采樣技術不適用于動態網絡，更不能在采樣后有效保留動態網絡的結構。

發明內容

為了解決現有邊采樣技術大多考慮的是靜態圖采樣，極少有考慮動態圖采樣的算法。并且，現有MSV改進技術都不是利用采樣來完成的，且改進后的結果都會引入新的缺陷(如引入邊交叉等)的問題。本發明提供一種量化評價MSV的邊級視覺混雜程度指標計算方法，能夠實現在MSV中對動態網絡直接進行邊級評估，并且能夠定量的衡量MSV中一條邊所在屏幕位置的視覺混雜程度。利用該指標作為MSV邊采樣的依據，可有效降低MSV視圖的混雜程度，極大程度的提高視圖的可讀性，從而幫助工作人員理解網絡通信的時變趨勢，節省其網絡探索的時間。

本發明為解決上述問題所采用的技術方案為：

一種量化評價MSV的邊級視覺混雜程度指標計算方法，包括以下步驟：

步驟1)：將動態網絡描述為一個有向圖并以MSV視圖的形式實現可視化，選取其中任意一條邊e，求出e在橫軸上的位置，然后從中心位置分別向左右各擴展一個不可區分的像素距離的寬度，以MSV視圖高度為高度，形成一個矩形區域，即不可區分的像素區域IPA；

步驟2)：以MSV視圖左上角為坐標系原點，且以邊e在縱軸偏上的端點所在的節點作為起始節點，偏下的端點所在的節點作為終點節點，然后找出所有部分或全部處于邊e的IPA內且與邊e產生了重疊的其他邊，將這些邊歸類于邊e的交錯邊并置于交錯邊集合EOS中；