空间位置耦合的地理社交网络可视化布局算法
发布时间：2021-01-03 00:48
针对传统力引导布局算法无法兼顾节点初始地理空间位置特征的问题,提出了空间位置耦合的力引导算法（SCFDA）,该算法在节点布局时,使节点除了受到胡克引力和库伦斥力影响外,还受到来自节点隶属的空间社团的中心重力和边界斥力影响,这样节点将在一定地理空间范围约束下实现布局和位置调整.在计算中心重力时顾及节点的内部度因素,使得内部度越高的节点越靠近空间社团的中心,在计算边界斥力时兼顾节点的外部度因素,使得外部度越高的节点越靠近空间社团的边界.利用2组社交网络签到数据集Gowalla和Brightkite进行了实验,通过兼顾内部度和外部度因素的综合评价指标值E（G）对实验结果进行评价,横向对比实验结果表明,SCFDA的E（G）值约为传统力引导布局算法的十分之一,而E（G）值越小则代表布局结果在顾及节点空间位置特征方面越合理;纵向对比实验结果表明, SCFDA在不同数据集和不同数据量上均具有普适性.
【文章来源】：计算机辅助设计与图形学学报. 2020年06期 北大核心
【文章页数】：9 页
【部分图文】：
brf直线型函数形式
?采用直线型函数作为边界斥力brf的具体表现形式,其函数图像如图2所示.图2brf直线型函数形式本文直线型函数形式的brf计算公式为brmaxminmax((,))()()iiiifnxyfdddd(6)其中,f为节点受到的其他所有合力值.2.1.2算法步骤为了能在进行可视化布局时兼顾节点的空间位置特征,本文首先将节点按照空间位置划分至k个SC12{,,,}kRRR,通过FR算法求取节点的引力和斥力;然后按照划分的SC计算其CG和BR,最终在SA算法的基础上实现节点位置布局的稳定(或保持震荡).图3所示为节点in的受力情况分析,其中,in和i1n之间有连边,所以in受到来自i1n的引力af;in与i1n之间没有连边,所以in受到来自i1n图3节点受力分析的斥力rf;CGP为当前节点所属SC的中心,则in受到来自SC中心CGP的cgf;最后,节点in还受到来自社团边界的brf.本文SCFDA的步骤如下:输入.网络G(V,E),SC=12{,,,}kRRR,以及各个社团的中心12{,,,}kccc,初始温度T,最大迭代次数L,引力系数g.输出.每个节点的空间位置数据集合111{n(x,y),222(,),,(,)}nnnnxynxy.Step1.根据输入,将各个节点划归至相应的SC.设网络G(V,E)中某一节点in的空间坐标为(,)iixy,遍历SC的区域空间数据集合,判断区域jR是否包含节点in.如果包含,则节点in隶属于该SC,循环此过程,直至所有节点都被划归至相应的SC.Step2.利用物理原理计算节点与节点之间的引力和斥力:Step2.1.初始化各个节点所受合力f0;Step2.2.遍历各SC,计算其内节点的理想距离jjjkSN;其中,jS为jR的面积,jN为隶属于jR的节点个数;Step2.3.根
第6期张政,等:空间位置耦合的地理社交网络可视化布局算法871a.0t时刻b.1t时刻c.2t时刻d.3t时刻e.4t时刻图4增加CG和BR的FR算法对Gowalla网络的布局效果本文对增加CG和BR的FR算法做了进一步改进,使得内部度越高的节点越靠近SC的中心,外部度越高的节点越靠近SC的边界,最终布局的结果如图5所示,按照节点度的大小对其进行分层设色处理,使得度越高的节点颜色深度越深.从布局的结果可以看出,度较高的节点要么布局在SC图5SCFDA对Gowalla网络的布局效果的中心,要么布局在SC的边界,这与期望的结果是一致的.令分别取0.05,0.25,0.50,0.75,0.95;对应的分别取0.95,0.75,0.50,0.25,0.05.实验共有265个节点、855条连边.由于和的值对应的是综合评价函数E(G)的比例系数,值越大,代表系数对应的分指标越重要.从表1的实验统计结果中可以看出,和的取值对布局结果以及布局速度并不会有直接的影响,即在布局时是内部度优先还是外部度优先对结果无明显影响.此外,本文算法的E(G)值明显小于改进前,而E(G)的值越小,说明布局的结果越合理;同时,在算法耗时方面,本文算法布局速度提升了一倍多.表1算法改进后的实验统计结果对比算法αβ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为了能够更好地体现本文算法的优势,分别与FR算法[6],ForceAtlas算法[7]以及Hu[19]算法进行了对比实验,实验的结果如图6所示.a.FR算法[6]b.ForceAtlas算法[7]c.Hu
【参考文献】：
期刊论文
[1]大规模社交网络社区发现及可视化算法[J]. 赵润乾,吴渝,陈昕. 计算机辅助设计与图形学学报. 2017(02)
[2]基于内容重要性边捆绑的图可视化算法[J]. 路强,马坤乐. 计算机辅助设计与图形学学报. 2016(11)
[3]展示复杂网络社团结构的社团引力导引的布局算法[J]. 吴渝,李藻旭,李红波,温磊. 计算机辅助设计与图形学学报. 2015(08)
[4]大数据时代的人类移动性研究[J]. 陆锋,刘康,陈洁. 地球信息科学学报. 2014(05)
[5]基于复杂网络社区划分的网络拓扑结构可视化布局算法[J]. 朱志良,林森,崔坤,于海. 计算机辅助设计与图形学学报. 2011(11)
本文编号：2953977
【文章来源】：计算机辅助设计与图形学学报. 2020年06期 北大核心
【文章页数】：9 页
【部分图文】：
brf直线型函数形式
?采用直线型函数作为边界斥力brf的具体表现形式,其函数图像如图2所示.图2brf直线型函数形式本文直线型函数形式的brf计算公式为brmaxminmax((,))()()iiiifnxyfdddd(6)其中,f为节点受到的其他所有合力值.2.1.2算法步骤为了能在进行可视化布局时兼顾节点的空间位置特征,本文首先将节点按照空间位置划分至k个SC12{,,,}kRRR,通过FR算法求取节点的引力和斥力;然后按照划分的SC计算其CG和BR,最终在SA算法的基础上实现节点位置布局的稳定(或保持震荡).图3所示为节点in的受力情况分析,其中,in和i1n之间有连边,所以in受到来自i1n的引力af;in与i1n之间没有连边,所以in受到来自i1n图3节点受力分析的斥力rf;CGP为当前节点所属SC的中心,则in受到来自SC中心CGP的cgf;最后,节点in还受到来自社团边界的brf.本文SCFDA的步骤如下:输入.网络G(V,E),SC=12{,,,}kRRR,以及各个社团的中心12{,,,}kccc,初始温度T,最大迭代次数L,引力系数g.输出.每个节点的空间位置数据集合111{n(x,y),222(,),,(,)}nnnnxynxy.Step1.根据输入,将各个节点划归至相应的SC.设网络G(V,E)中某一节点in的空间坐标为(,)iixy,遍历SC的区域空间数据集合,判断区域jR是否包含节点in.如果包含,则节点in隶属于该SC,循环此过程,直至所有节点都被划归至相应的SC.Step2.利用物理原理计算节点与节点之间的引力和斥力:Step2.1.初始化各个节点所受合力f0;Step2.2.遍历各SC,计算其内节点的理想距离jjjkSN;其中,jS为jR的面积,jN为隶属于jR的节点个数;Step2.3.根
第6期张政,等:空间位置耦合的地理社交网络可视化布局算法871a.0t时刻b.1t时刻c.2t时刻d.3t时刻e.4t时刻图4增加CG和BR的FR算法对Gowalla网络的布局效果本文对增加CG和BR的FR算法做了进一步改进,使得内部度越高的节点越靠近SC的中心,外部度越高的节点越靠近SC的边界,最终布局的结果如图5所示,按照节点度的大小对其进行分层设色处理,使得度越高的节点颜色深度越深.从布局的结果可以看出,度较高的节点要么布局在SC图5SCFDA对Gowalla网络的布局效果的中心,要么布局在SC的边界,这与期望的结果是一致的.令分别取0.05,0.25,0.50,0.75,0.95;对应的分别取0.95,0.75,0.50,0.25,0.05.实验共有265个节点、855条连边.由于和的值对应的是综合评价函数E(G)的比例系数,值越大,代表系数对应的分指标越重要.从表1的实验统计结果中可以看出,和的取值对布局结果以及布局速度并不会有直接的影响,即在布局时是内部度优先还是外部度优先对结果无明显影响.此外,本文算法的E(G)值明显小于改进前,而E(G)的值越小,说明布局的结果越合理;同时,在算法耗时方面,本文算法布局速度提升了一倍多.表1算法改进后的实验统计结果对比算法αβ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为了能够更好地体现本文算法的优势,分别与FR算法[6],ForceAtlas算法[7]以及Hu[19]算法进行了对比实验,实验的结果如图6所示.a.FR算法[6]b.ForceAtlas算法[7]c.Hu
【参考文献】：
期刊论文
[1]大规模社交网络社区发现及可视化算法[J]. 赵润乾,吴渝,陈昕. 计算机辅助设计与图形学学报. 2017(02)
[2]基于内容重要性边捆绑的图可视化算法[J]. 路强,马坤乐. 计算机辅助设计与图形学学报. 2016(11)
[3]展示复杂网络社团结构的社团引力导引的布局算法[J]. 吴渝,李藻旭,李红波,温磊. 计算机辅助设计与图形学学报. 2015(08)
[4]大数据时代的人类移动性研究[J]. 陆锋,刘康,陈洁. 地球信息科学学报. 2014(05)
[5]基于复杂网络社区划分的网络拓扑结构可视化布局算法[J]. 朱志良,林森,崔坤,于海. 计算机辅助设计与图形学学报. 2011(11)
本文编号：2953977
本文链接：https://www.wllwen.com/kejilunwen/dizhicehuilunwen/2953977.html
