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

【文章來(lái)源】：計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào). 2020年06期 北大核心

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

【部分圖文】：

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

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

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

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



本文編號(hào)：2953977