針對傳統(tǒng)力引導(dǎo)布局算法無法兼顧節(jié)點初始地理空間位置特征的問題,提出了空間位置耦合的力引導(dǎo)算法（SCFDA）,該算法在節(jié)點布局時,使節(jié)點除了受到胡克引力和庫倫斥力影響外,還受到來自節(jié)點隸屬的空間社團的中心重力和邊界斥力影響,這樣節(jié)點將在一定地理空間范圍約束下實現(xiàn)布局和位置調(diào)整.在計算中心重力時顧及節(jié)點的內(nèi)部度因素,使得內(nèi)部度越高的節(jié)點越靠近空間社團的中心,在計算邊界斥力時兼顧節(jié)點的外部度因素,使得外部度越高的節(jié)點越靠近空間社團的邊界.利用2組社交網(wǎng)絡(luò)簽到數(shù)據(jù)集Gowalla和Brightkite進行了實驗,通過兼顧內(nèi)部度和外部度因素的綜合評價指標值E（G）對實驗結(jié)果進行評價,橫向?qū)Ρ葘嶒灲Y(jié)果表明,SCFDA的E（G）值約為傳統(tǒng)力引導(dǎo)布局算法的十分之一,而E（G）值越小則代表布局結(jié)果在顧及節(jié)點空間位置特征方面越合理;縱向?qū)Ρ葘嶒灲Y(jié)果表明, SCFDA在不同數(shù)據(jù)集和不同數(shù)據(jù)量上均具有普適性. 

【文章來源】：計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2020年06期 北大核心

【文章頁數(shù)】：9 頁

【部分圖文】：

brf直線型函數(shù)形式

?采用直線型函數(shù)作為邊界斥力brf的具體表現(xiàn)形式,其函數(shù)圖像如圖2所示.圖2brf直線型函數(shù)形式本文直線型函數(shù)形式的brf計算公式為brmaxminmax((,))()()iiiifnxyfdddd(6)其中,f為節(jié)點受到的其他所有合力值.2.1.2算法步驟為了能在進行可視化布局時兼顧節(jié)點的空間位置特征,本文首先將節(jié)點按照空間位置劃分至k個SC12{,,,}kRRR,通過FR算法求取節(jié)點的引力和斥力;然后按照劃分的SC計算其CG和BR,最終在SA算法的基礎(chǔ)上實現(xiàn)節(jié)點位置布局的穩(wěn)定(或保持震蕩).圖3所示為節(jié)點in的受力情況分析,其中,in和i1n之間有連邊,所以in受到來自i1n的引力af;in與i1n之間沒有連邊,所以in受到來自i1n圖3節(jié)點受力分析的斥力rf;CGP為當(dāng)前節(jié)點所屬SC的中心,則in受到來自SC中心CGP的cgf;最后,節(jié)點in還受到來自社團邊界的brf.本文SCFDA的步驟如下:輸入.網(wǎng)絡(luò)G(V,E),SC=12{,,,}kRRR,以及各個社團的中心12{,,,}kccc,初始溫度T,最大迭代次數(shù)L,引力系數(shù)g.輸出.每個節(jié)點的空間位置數(shù)據(jù)集合111{n(x,y),222(,),,(,)}nnnnxynxy.Step1.根據(jù)輸入,將各個節(jié)點劃歸至相應(yīng)的SC.設(shè)網(wǎng)絡(luò)G(V,E)中某一節(jié)點in的空間坐標為(,)iixy,遍歷SC的區(qū)域空間數(shù)據(jù)集合,判斷區(qū)域jR是否包含節(jié)點in.如果包含,則節(jié)點in隸屬于該SC,循環(huán)此過程,直至所有節(jié)點都被劃歸至相應(yīng)的SC.Step2.利用物理原理計算節(jié)點與節(jié)點之間的引力和斥力:Step2.1.初始化各個節(jié)點所受合力f0;Step2.2.遍歷各SC,計算其內(nèi)節(jié)點的理想距離jjjkSN;其中,jS為jR的面積,jN為隸屬于jR的節(jié)點個數(shù);Step2.3.根

第6期張政,等:空間位置耦合的地理社交網(wǎng)絡(luò)可視化布局算法871a.0t時刻b.1t時刻c.2t時刻d.3t時刻e.4t時刻圖4增加CG和BR的FR算法對Gowalla網(wǎng)絡(luò)的布局效果本文對增加CG和BR的FR算法做了進一步改進,使得內(nèi)部度越高的節(jié)點越靠近SC的中心,外部度越高的節(jié)點越靠近SC的邊界,最終布局的結(jié)果如圖5所示,按照節(jié)點度的大小對其進行分層設(shè)色處理,使得度越高的節(jié)點顏色深度越深.從布局的結(jié)果可以看出,度較高的節(jié)點要么布局在SC圖5SCFDA對Gowalla網(wǎng)絡(luò)的布局效果的中心,要么布局在SC的邊界,這與期望的結(jié)果是一致的.令分別取0.05,0.25,0.50,0.75,0.95;對應(yīng)的分別取0.95,0.75,0.50,0.25,0.05.實驗共有265個節(jié)點、855條連邊.由于和的值對應(yīng)的是綜合評價函數(shù)E(G)的比例系數(shù),值越大,代表系數(shù)對應(yīng)的分指標越重要.從表1的實驗統(tǒng)計結(jié)果中可以看出,和的取值對布局結(jié)果以及布局速度并不會有直接的影響,即在布局時是內(nèi)部度優(yōu)先還是外部度優(yōu)先對結(jié)果無明顯影響.此外,本文算法的E(G)值明顯小于改進前,而E(G)的值越小,說明布局的結(jié)果越合理;同時,在算法耗時方面,本文算法布局速度提升了一倍多.表1算法改進后的實驗統(tǒng)計結(jié)果對比算法αβE(G)耗時/s改進前0.050.9524.4745.760.250.7526.7744.920.500.5023.6946.150.750.2525.1346.680.950.0525.0147.34改進后0.050.9513.2520.550.250.7515.6719.450.500.5011.8921.870.750.2513.5019.650.950.0512.7421.12為了能夠更好地體現(xiàn)本文算法的優(yōu)勢,分別與FR算法[6],ForceAtlas算法[7]以及Hu[19]算法進行了對比實驗,實驗的結(jié)果如圖6所示.a.FR算法[6]b.ForceAtlas算法[7]c.Hu

【參考文獻】：
期刊論文
[1]大規(guī)模社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)及可視化算法[J]. 趙潤乾,吳渝,陳昕.  計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2017(02)
[2]基于內(nèi)容重要性邊捆綁的圖可視化算法[J]. 路強,馬坤樂.  計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2016(11)
[3]展示復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)的社團引力導(dǎo)引的布局算法[J]. 吳渝,李藻旭,李紅波,溫磊.  計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2015(08)
[4]大數(shù)據(jù)時代的人類移動性研究[J]. 陸鋒,劉康,陳潔.  地球信息科學(xué)學(xué)報. 2014(05)
[5]基于復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的網(wǎng)絡(luò)拓撲結(jié)構(gòu)可視化布局算法[J]. 朱志良,林森,崔坤,于海.  計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2011(11)



本文編號：2953977