基于PageRank的网络布局算法

(西南科技大学 计算机科学与技术学院，四川 绵阳 621010 )

0 引言

现实世界中，许多复杂的系统都被建模成网络的形式，例如社交网络，生物网络和通讯网络等[1-2]。网络可视化能够让人类利用眼睛这个最高效的信息获取通道，最大化地发挥视觉感知能力，从这些网络数据中获取有用的信息。为了更有效地分析网络，需要设计出一个高性能并且对人类来说可读性强的网络布局方法。过去的数十年，人们设计了许多的网络可视化算法，其中基于力导向模型的节点连接图形式的布局由于其直观并且便于展示数据之间的关系，得到了广泛的应用，促进了各个学科的发展。

现实世界中的网络许多都带有无尺度特性，这类网络的度分布符合幂律，典型特征是在网络中的大部分节点只和很少节点连接，而有极少的节点与非常多的节点连接。然而，目前已存在的网络算法通常在均匀分布的，类似于网格状结构的数据上表现很好。因此目前基于力导向模型的网络布局算法在处理大规模现实世界网络数据时，产生的布局结果往往可读性不够理想，很难从中得到有价值的信息。同时，目前的布局算法在计算节点的位置时往往没有考虑节点的特征参数，如PageRank和中心性等属性。在布局算法的结果中，节点所在的位置只与节点的连接关系有关，而与节点的其他无关，这样的布局结果是不精确的。当前的网络布局算法大部分都使用的是纯CPU计算布局，或者基于GPU计算但是灵活性和稳定性不够，易用性以及性能无法令人满意。当需要对大规模现实世界网络进行可视分析的时候，一个高质量的，计算时间短的网络布局算法的需求越来越高。目前最主要的挑战有两个方面：第一，如何在处理大规模现实世界网络数据时得到一个高质量的布局；第二，在面对大规模网络数据的时候有效减少布局算法的计算时间。接下来文中将阐述如何解决这两个挑战。

1 相关工作

网络可视化在提高布局算法的布局质量和缩短计算时间方面的研究有着显著的进展。

Eades[3]在1984年第一次提出了基于力导向模型的网络布局算法，这个布局算法将网络中的节点看成一个钢环，边是连接钢环的弹簧，整个网络构成了一个弹簧机械系统。该算法可以获得一个具有良好可读性的布局，但是由于时间复杂度为O(N2)，所以很难适应大规模网络的应用。在优化斥力计算方面，Fruchterman和Reingold[4]提出将网络中的所有节点放在平均划分的单元网格中，只计算一个节点相邻的网格中节点的斥力来减少复杂性。但是这种做法忽略了太多的节点，生成的布局精确度不够。Barnes和Hut[15]提出使用物理学中广为人知的N-body模拟来解决斥力计算，主要思想是将远处的一组节点看成是一个超级节点，使得斥力计算的时间复杂度从O(N2)降到了O(Nlog(N))，并且也保证了布局的精确性。在减少迭代次数方面：Kamada和Kawai基于Eades的算法提出了KK[5]算法。该算法遵循了胡克定律的偏微分方程，并以此来优化了节点的布局，提高了算法的收敛速度。为了减少迭代次数一些早期的改进方案包括模拟退火[6]、GEM(Graph EMbedder)[7-8]、美观费校函数(Arsthetic Cost Function)[9]等。但是都容易陷入局部最优。Hadany R[10]首先提出了MultiLevel方法。该方法主要有两个部分，图粗化和图细化。在粗化阶段，算法通过的迭代的执行图粗化算法得到多个层次的粗化图，到达指定的层次后，再在当前层次上进行计算布局，由于此时节点较少，就可以快速地获得布局结果；在细化阶段，也就是递归返回阶段，算法不断的加入上一层粗化图中的节点并且计算布局，最终获得一个完整的布局结果。这种方式减少了布局整体迭代的次数，但是不适合真实世界的网络数据。为了能够有效减少大规模网络布局的计算时间，许多研究人员在布局算法中使用了并行计算技术。其中比较常见的OpenOrd[11]是整合了edge-cutting，和average-link聚类优化方案的并行网络布局算法，但是这个算法不适合小规模网络，并且只能够用于无向图。Arleo[12]提出了Multi-GiLA，它是第一个基于以顶点中心的计算范式的MultiLevel算法。随着GPU计算的流行，Frishman Y[13]提出了将Multilevel运行在GPU上的方法，但是并没有使用成熟的GPU并行框架，算法的性能和鲁棒性都不够理想。

许多网络布局算法产生的结果只和节点的连接关系有关，而与节点的网络特征参数如PageRank，接近度中心性等没有关系，这样的布局算法造成了一些信息损失。文中根据力导向模型的性能依赖初始布局结果的随机值结论[14]，提出了一个基于节点接近度中心性的初始布局算法来获取一个更加合理的布局在初始布局阶段。初始布局不再完全依赖于随机值。为了能够获得一个质量更高的布局结果，我们引入了节点重要性这一网络拓扑特征参数来改进节点的斥力和重力的计算。文中采用PageRank来表示节点在网络中的重要程度。为了更好地平衡布局的质量与性能，我们提出了基于PageRank的自适应步长，越重要的节点对网络布局结果的影响越大。最后，我们基于成熟的CPU+GPU异构并行架构CUDA设计了一套异构并行计算框架，使我们的算法灵活并且高效的运行在了GPU上进一步减少了算法的执行时间。

2 基于PageRank的网络布局算法

文中所提出的算法是基于力导向模型的算法，对于网络数据来说，力导向模型所得出的节点链接布局，这种布局是对网络关系最直接最经典的可视化表达。力导向模型算法中在计算节点受力情况的时候不需要太复杂的逻辑控制，只需要进行大量的迭代计算，所以非常适合CPU+GPU的异构并行处理。文中会在这部分会从初始布局算法和吸引力算法，以及基于PageRank的斥力，重力和自适应步长几个方面详细讲解文中的布局算法。节点n受到的力F(n)则是由吸引力、斥力和重力产生的合力。文中在斥力计算部分采用了Barnes-Hut的四叉树近似斥力优化[15]，篇幅原因，文中不再详细描述。最后介绍了文中提出的用于加速布局计算的异构并行框架。算法1显示了文中所提出的算法的伪代码。

算法1:基于PageRank的网络布局算法

输入：图G=(N,E), 迭代次数iterations, 重力和斥力系数kg和kr,PageRan和每一个节点的中心性Centrality.

输出：具有位置信息的节点数据

算法开始：

//根据中心性获取节点的初始位置, PN表示所有节点的位置数据。

PN= Initialization_layout_algorithm(G,Centrality);

For 1 → iterations do

BH.rebuild() //重建Barnes-Hut树

For n in nodes do

For v ∈ neighbors(n) do

Fn= Fn+ Fa(n,v);//计算吸引力

End For

Fn= Fn+ kr× BH.force_at(Pn,PR(n)); //计算基于PageRank的斥力

Fn= Fn- kg(PR(n));//计算基于PageRank的重力

End For

UpdateGlobalSpeed();

For n ∈ N do

Pn=local_speed(n,PR(n)) ×Fn; //更新节点位置

End for

End For

算法结束

其中:UpdateGlobalSpeed( )是更新节点的全局速度，local_speed(n,PR(n))是求出节点n的速度。

2.1 基于节点中心性的初始布局算法

如上文所述，大部分基于力导向模型的网络布局算法在生成初始布局的时候大都使用随机布局，导致了布局达到稳定状态所需要的时间依赖于随机布局的结果。初始布局的结果完全取决于随机数。文中引入了节点的Closeness Centrality来计算一个节点在初始布局所处的位置，因为节点的Closeness Centrality反映了节点在网络中居于中心的程度，是衡量节点中心性的指标之一[9]。文中采用了Wasserman 和Faust[16]提出的Closeness Centrality计算公式。

(1)

其中:n-1是u所有可到达的节点的数量，N等于网络中所有节点的数量，d(v,u)是节点v和u之间的最短路径的距离。

为了将节点初步分类，文中提出了Closeness Centrality Level的概念，根据节点的中心性的值的大小，将节点分为3个等级。将值归一化处理之后，值较大的部分节点等级为1，其次是等级2，最后，较小的部分节点等级为3。初始布局算法主要根据节点的等级将节点设置在不同的位置。等级为1的节点设置在布局正中心位置，等级为2的节点相比于1的节点要更边缘一些，以此类推，等级为3的节点在布局的最边缘位置。我们首先计算出所有节点在3个不同半径范围内的极坐标，然后根据极坐标转直角坐标的公式得出每个节点的位置。初始布局算法的伪代码如算法2所示。

虽然文中的初始布局算法依然使用了随机数，但是，该算法没有完全依赖于随机数，而是根据每个节点的中心性给节点的初始位置划定了区间，使其出现在一个合理的范围，从而产生质量更高的初始布局。

算法2:初始布局算法 (Initialization_layout_algorithm)

输入：具有中心性的节点数据

输出：具有位置信息的节点数据

算法开始：

fornin nodes do

//根据节点的中心性计算Closeness Centrality level

if n.cc > maxCC × α then

n.cl = first;

end if

if maxCc ×ε≤ n.cc < maxCc ×αthen

n.cl = second;

end if

if n.cc < maxCc ×εthen

n.cl = third;

end if

// 根据节点的Closeness Centrality level计算半径

if CL(n) == first then

r =(ε× random(0, 1)) × minSize;

end if

if CL(n) == second then

r= (ε+λ× random(0, 1)) × minSize;

end if

if CL(n) == third then

r= (α+γ× random(0, 1)) × minSize;

end if

n.x=r× cos(random(θ)/180) + width ÷ 2;

n.y=r× sin(random(θ)/180) + height ÷ 2;

end for

算法结束

其中:random(0,1)产生是0～1之间的随机数，minSize是指的布局宽高的最小值，α和ε是常数，用来控制节点的初次分类，λ和γ是常数，用来控制节点所在区域。random(θ)是产生一个随机的角度。

2.2 吸引力

节点n1和n2之间的吸引力Fa的计算往往是非常简单的。我们采用了传统的力导向布局的节点之间吸引力计算方法，即线性依赖于两个节点之间距离[17]。

Fa(n1,n2)=d(n1,n2)

(2)

2.3 基于PageRank的斥力

传统的力导向模型的算法中，节点之间的斥力往往只跟两个节点之间的距离有关系。经过这么多的研究发现，网络中不同节点的重要性和影响力是不一样的[18]，计算布局的时候应当考虑节点的重要性所带来的影响。影响力较高的一些节点彼此之间应当有一定的距离，从而形成多个簇，而不是受到重力的影响都聚在布局正中心形成一个较大的混乱的簇，以致于大大降低布局的可读性。PageRank是一个很好的衡量节点重要性和影响力的参数。因此我们设计了一个基于PageRank 的斥力计算公式，节点n1和n2之间的斥力的大小与两个节点的PageRank值的乘积成正比，与距离成反比。斥力计算公式如式(3)所示：

(3)

其中:PR(n1)为节点n1的PageRank值，我们的斥力计算公式中使用PR+1而不是PR是为了避免PR为0时出现斥力为0的情况，斥力系数kr是一个手动设置的常数。d(n1,n2)为n1和n2之间的距离。

2.4 基于PageRank的重力

重力是一种改善力导向模型布局算法的视觉效果的常用方法[19]。部分网络数据中可能包含了大量小型的非连通组件和离散的节点，这些元素在引力和斥力的影响下每次迭代都会被推离布局中心，这将导致会产生一个过于离散的布局。为了防止布局结果中的部分节点偏离布局中心太远，我们使用了重力。重力是一种将节点吸引到布局中心点的力，越重要的节点应该拥有越强的重力。节点n受到的重力的计算公式如公式(4)所示：

Fg(n)=kg(PR(n)+1)

(4)

其中:kg是一个常数，表示重力系数，在算法执行的时候传入，PR(n)和式(3)一样为节点n的PageRank值，下同。

2.5 自适应步长

在力导向模型布局的算法中，速度和精度一直都是一个难以两全的选择，布局中增加步长就会提高布局算法的速度，但是会导致布局精度下降。同理，布局迭代中减小步长会增加布局的精度，但是会降低布局算法的速度。为了平衡精度和速度，文中改进了Jacomy M[20]的自适应的步长。自适应步长的主要思想是观察每一次迭代每个节点的振荡和全局网络振荡来针对每一个节点的每一次迭代计算一个专属的步长。文中通过引入PageRank从而让重要性越高的节点的振荡对布局产生越大的影响力，重要性越低的节点的振荡对全局震荡的影响越小。布局每一次迭代的步长都与当前的状态和全局的状态有关，这一策略有助于平衡算法的精度和速度。因此布局将会以更快的速度达到一个稳定的状态。每一步迭代的步长都要根据节点在当前步的振荡和整个网络在当前步全局的振荡来动态调整。文中定义节点n的第t步迭代的振荡OSCt(n)为第t步与t-1步应用到节点n上的力的差的绝对值。

OSCt(n)=|Ft(n)-Ft-1(n)|

(5)

其中:Ft(n)为节点n在第t步迭代受到的力，此处的力指的是吸引力、斥力和重力的合力。根据基本的物理学公式可以得出节点n当前步的步长D(n)=F(n)S(n), 其中S(n)为节点速度。

(6)

其中速度系数ks为一个常数，GSt为第t步迭代的网络全局速度，将在接下来介绍GSt。为了防止单个节点的速度过快，设置了节点速度最大值。

(7)

其中:ksmax为常数。

为了让重要性高的节点的振荡对网络的全局产生更大的影响力，就必须在计算全局振荡的时候考虑节点的重要性。文中使用节点的PageRank值作为节点的重要性衡量指标，PageRank值越大的节点重要性越高。因此，节点n在第t次迭代的全局振荡GOSC(t)定义为每个节点的振荡与自身PageRank值的乘积的和。

(8)

为了帮助布局收敛，我们引入了牵引力，节点n在第t次迭代的有效牵引力trat(n)是与振荡相反的，定义为第t次迭代的力与t-1次迭代的力的和的一半。

(9)

如果节点n第t次迭代后，返回了t-1次迭代的位置那么trat(n)= 0；如果节点一直保持之前的运动方向，那么trat(n)=Ft(n)。

因为重要性高的节点要在网络全局中具有更大的影响力，因此这些节点也要拥有更大的牵引力。全局有效牵引力GFtra(t)是每个节点的有效牵引力与自身PageRank值的乘积的和。

(10)

全局速度GS(t)为全局有效牵引力与全局网络振荡的比。

(11)

其中:τ是一个调整全局速度的常数。

节点的重要性影响了网络全局振荡和全局牵引力的计算，这两个因素又分别影响了节点的速度和网络的全局速度，进一步影响了当前迭代的步长。每一个节点在每一次迭代都根据自身的参数和网络的整体状态获得一个合适的步长。自适应步长的策略有效的平衡了布局算法的速度和质量。

2.6 异构并行架构设计

最初，计算机只包含用来运行编程任务的CPU。近年来，高性能计算领域中的主流计算机不断添加了其他处理元素，其中最主要的就是GPU。随着时间的推移，GPU从最初是被设计用来专门处理并行图形计算问题到现在已经成了更强大且更广义的处理器，在执行大规模并行计算中有着优越的性能和很高的效率。文中在上面所提出的布局引入网络结构特征参数，来改进布局算法中重力，斥力以及自适应步长并且提出了基于Page- Rank的自适应步长来提高布局算法的效率和质量。可以让布局算法以更少的迭代次数达到一个可读性更高的布局。但是对于大部分的个人电脑来说，当面临节点数量达到十万甚至数百万规模的大型复杂网络的时候，由于力导向布局的需要大量迭代而不需要复杂的逻辑控制，如果要进一步提高布局计算速度，一个很合适的策略就是使用CPU+GPU异构并行计算来加速。CPU上进行复杂的逻辑判断，GPU上进行大量的迭代计算，CPU和GPU通过PCI-E总线进行通信。异构并行计算的效率相比于传统的并行计算拥有显著的优势。图1显示了文中算法的工作流图，A部分运行在CPU上，B部分则运行在GPU上。

图1 算法整体流程图

2.6.1 异构架构

如果一个算法有较小的数据规模、复杂的逻辑控制，那么最好选择CPU处理该问题，因为它有处理复杂逻辑和指令级并行性的能力。相反，如果该问题包含较大规模的数据处理并表现出大量的数据并行性，那么使用GPU是最好的选择。因为GPU中有大量的可编程核心，可以支持大规模多线程运算。CPU+GPU的异构并行计算架构可以实现功能互补，使得应用程序获得最佳的运行效果。CUDA是一种通用的异构并行计算平台，通过使用CUDA可以像在CPU上一样使用GPU来进行计算。使用这个平台即避能够免重复造轮子又可以确保算法程序的稳定性。为了进一步提升框架的灵活性，我们设计了一系列组件去实现文中所提出算法的异构并行执行。

2.6.2 组件设计

本算法的不同迭代阶段需要并行计算的数据不是一成不变的。例如，在计算吸引力的时候需要对边数据进行并行处理，当计算斥力的时候需要对节点数据进行并行处理。由于CUDA是基于数据并行而不是基于任务并行，所以程序从CPU拷贝到GPU上的数据是两个数组组成，其中一个存放网络的节点数据，另一个存放网络的边数据。我们设计了5个组件，一部分组件是基于节点数据并行，另一部分基于边数据并行，每个组件内部都包含一个或者多个kernel。通过这些组件，除了可以运行文中所提出的算法之外，还可以通过替换其中某一个组件来灵活的切换成其他的网络布局算法，例如替换吸引力计算的组件来改变吸引力计算的方法等。算法一开始会在CPU上执行初始布局，然后通过PCIE将数据拷贝到GPU上，开始在GPU上迭代执行以下5个组件：

1)GravityComponent：此组件是基于节点数据并行的组件。主要用来计算施加到每个节点上的重力。

2)AttractiveForceComponent：此组件是基于边数据并行的，计算每个节点和他的相连接的节点之间的吸引力，这个力会让相关联的节点位置更近。

3)ReplusiveForceComponent：此组件是基于节点数据并行的。计算每一个节点受到的排斥力。使不直接关联的节点距离远一些，同时各个“影响力者”保持一定的距离从而来减少边交叉和视觉杂乱。

4)SpeedComponent：此组件是基于节点数据并行的，用来控制自适应步长的。

5)DisplacementComponent：此组件是基于节点数据并行的，用来根据以上几个组件的结果来更新每个节点当前的位置。

3 实验评估

文中设计了两个实验来评估前面所提出的算法的质量以及异构并行架构的性能。在布局质量评估实验中，在布局质量评估实验中，使用Crosslessness[21], Edge length variation[22], Minimum angle metric[21]和Normalized Atedge Length[23]这四个美学量化标准测量布局结果的质量。美学指标可以对不同布局的质量进行定量比较[24]，这些指标的详细信息如下：

Crosslessness (AMc)：边交叉最小化是当前最重要的美学指标之一[25-26]。文献[24]中定义Crosslessness如下所示：

(12)

其中:c是实际边交叉的数量，cmax是边交叉的近似上限，计算方式如下：

(13)

其中:E是网络中边的数量，N是节点集合，deg(n)是节点n的度。

(14)

其中:lσ是边长的标准差，lμ是网络布局中边长的平均值。

Minimum angle metric(AMa)：这个度量量化了顶点上入射边之间的最小夹角最大化的准则。文献[24]将其定义为节点n上入射边缘之间的最小角度与理想最小角度θ(n)的平均绝对偏差。

(15)

其中:θmin(n)是节点n的入射边的最小夹角。

Normalized Atedge Length (AMn)：Nocak[23]提出的“Normalized Atedge Length”适用于无尺度网络，定义如下：

(16)

其中:E是网络中的边集合，N是节点集合。|E|和|N|分别为边的数量和节点的数量，d(n1,n2)是节点n1和n2之间的欧式距离。 由于Qnoack的值越小越好，为了避免理解偏差，文中将指标反转以使其更加的清晰。

(17)

文中测量了三个基于力导向模型的算法作为控制组，分别是OpenOrd，Yifan Hu和Fruchterman Reingold算法。其中OpenOrd和Yifan Hu都是具有出色的质量和性能的力导向模型的布局，Fruchterman Reingold是最经典的力导向模型布局之一。在另一个实验中，我们在15种不同类型和规模的网络数据上比较了文中提出的布局算法的两个实现版本的计算时间。该算法的两个版本分别基于纯CPU实现版本和基于前文所提出的CPU + GPU的异构并行计算的实现版本。

3.1 实验数据

文中使用了各种不同类别和不同大小的现实世界网络数据，用来评估我们算法的可靠性，如表1所示。这些数据来自三个数据集KONECT[27]，SNAP[28]和SuiteSparse Matrix Collection[29]。其中facebook和twitter与Slashdot都是社交网络，Blogs是美国2004年大选期间博客之间的超链接网络。commanche_dual是一个来自NASA的结构性问题网格。1138_bus是一个电力系统总线数据，fe_4elt2是流体力学相关的结构性网格数据，3elt是一个2D有限元问题网格数据，web- NotreDame是圣母大学nd.edu域名内的页面之间的超链接网络，web-Stanford是来自斯坦福大学stanford.edu页面之间的超链接。Web-Google是Google公司在2002年举办的Google Programm- ing Contest中的一部分数据，节点代表web页面，边代表它们之间的超链接，baidu relatepages是百度百科文章之间的链接网络。文中将从性能和视觉效果两个方面分析我们的算法。文中将从算法质量和异构架构的性能两个方面来分析我们的工作。

表1 实验数据集

3.2 实验环境

我们的机器使用的是英特尔Core i7-6700k @4 GHz 四核处理器(四核心八线程)，32 GB DDR4 2133 MHz内存，Nvidia GeForce GTX 1080 8 GB显卡。我们使用了cuda 10.0版本，gcc/g++版本是7.3.0，操作系统是Ubuntu Linux 18.04。

3.3 算法配置

在初始布局阶段，我们设置常数α和ε分别为0.3和0.6，λ和γ分别为0.3和0.4，这样做的目的是可以使节点坐标的半径r为绘制区域长宽最小值的[0,0.3)倍，以及[0.3,0.6)和[0.6,1)倍三个环形区域。从而生成初始布局各个节点的坐标。我们设置重力系数kg的值为1，斥力系数kr设置为5。

3.4 实验结果

3.4.1 布局质量

文中使用以上4个美学指标(AMc,AMl,AMa,AMn)，测量了文中所提出的算法和Yifan Hu,OpenOrd与Fruchterman Reingold 4个算法在不同类型和不同规模的网络数据中的布局质量。图2采用堆叠条形图可视化了我们的实验结果，图中从左往右数据的规模依次增大，第二行的网络数据规模都要大于第一行。每一组条形图表示一个网络数据，其中每一个条，代表一个算法在这个网络数据的布局结果的美学指标得分状况，条中不同的颜色代表了不同的美学指标，从上到下依次是AMc,AMl,AMa,AMn。通过实验我们可以明显地发现，总体上，文中的算法所计算出的布局质量一直都优于其他三种布局算法。在小规模网络网络上，文中的算法质量虽然优于另外三个布局算法，但是差距并不大。特别是在小规模的社交网络上，FR算法的布局质量十分优秀，接近于文中的算法。在大规模网络上，文中所提出的算法在质量上就开始和其他算法拉开差距。Fruchterman Reingold算法的质量要远低于其在小规模网络上的质量。OpenOrd算法和Yifan Hu算法的质量也产生了较大的波动，但是整体上也是低于它们在小规模网络上的质量。我们的算法则保持了稳定的高质量，并且文中所提出的算法的美学指标分数也高于另外三个算法。文中的算法在面对大规模现实世界网络数据的时候，能够稳定地得出一个高质量的布局。

图2 布局质量测试结果

3.4.2 性能对比

表2显示了文中所提出的算法的两个版本在不同规模和不同类型的现实世界网络数据上的计算时所消耗的时间。其中CPU+GPU一列是该算法基于CPU+GPU的异构并行计算框架的实现版本在各种不同的网络数据上的布局计算所消耗的时间，CPU一列是该算法基于纯CPU的实现版本所消耗的时间。文中的布局算法计算时间包含了初始布局的时间。从表2中可以看出，CPU+GPU的实现在不同规模和不同类型的网络数据上的性能都超过了纯CPU的版本。该算法的异构并行架构版本相对于纯CPU计算的实现版本达到1倍到58倍的加速；在拥有325729个节点1497134条边web-Notre- Dame数据上，纯CPU版本的计算时间是482.167秒，然而CPU+GPU算法的时间是8.215秒，极大地缩短了布局计算时间。根据CPU+GPU列与CPU的实验数据结果的对比可以发现，我们提出的CPU+GPU的异构并行计算框架在减少各种规模网络布局算法的计算时间方面，效果非常显著。

表2 性能对比 s

4 结束语

由于当前主流的基于力导向模型网络布局算法在面对大规模现实世界网络时出现布局质量不佳，计算时间过长的问题，文中提出了一个基于PageRank的新的力导向模型的算法和一个基于CUDA的CPU+GPU异构并行计算框架。文中引入了两个拓扑特征参数，节点中心性和PageRank。文中设计了一个基于节点中心性的网络初始布局算法来让网络节点获得一个较好的初始位置，以减少达到最优布局所需要迭代的次数，同时也可以削弱力导向模型的网络布局算法对初始布局随机值的依赖性。

PageRank是衡量节点重要性的关键指标。文中创造性的提出了基于PageRank的重力，斥力和自适应步长。重力是用来防止一部分离散的节点推离布局中心太远。因为越重要的节点应当距离布局重心越近，所以基于节点重要性的重力的计算公式中，节点的重力与节点在网络中的重要程度成正比。节点的PageRank值越大，节点的重力也就越大。为了防止重要性较高的节点都集中在布局中心靠的太近从而造成视觉遮挡，文中提出了基于节点重要性的斥力，使得重要程度较高的节点彼此之间拥有一定的距离，不至于在布局中心形成一个又大又密的簇，而是形成多个清晰的小型的簇。我们也使用了四叉树斥力优化来降低斥力计算部分的时间复杂度，提升了布局性能。为了平衡布局的精度和速度，我们提出了基于节点重要性的自适应步长，越重要节点的产生的振荡对网络全局造成的影响越大，每一个节点每一次迭代的步长都是综合考虑和网络全局和节点自身情况所计算出来的。

最后，文中通过选取4个美学指标来评估布局结果，根据实验发现了文中的算法在面对不同规模的网络上都能够得到不错的布局质量。特别是在大规模网络数据上，文中的算法依然能够获得一个高质量的布局结果。文中为了测试文中提出的异构并行计算框架的性能，选取了不同类型，不同规模的网络数据，进行了大量的实验。实验结果表明了文中的异构并行计算框架能够显著的减少布局计算的时间。

未来我们会继续完善现在的工作，使其应用到大规模网络可视化系统中，从而提升此类系统对大规模网络的处理能力，使得研究人员可以更加便利地通过可视化系统来分析大规模网络数据。此外，我们将研究进一步改进节点重要性的计算方法，并且改进算法可以根据不同的网络类型，去自动选取合适的节点重要性计算方法。