一种面向大规模网络的社区布局可视化方法

摘要

本发明请求保护一种面向大规模网络的社区布局可视化方法，涉及信息可视化领域。本发明在力导引布局的基础上，引入层次空间分解模型，降低节点之间斥力的计算时间复杂度。节点度数控制节点斥力的大小，使得度数大的节点之间相互远离，社区结构更加清晰。优化社区引力建模，降低社区引力的计算时间复杂度，方法能够适用于大规模网络的社区布局。针对节点重叠问题，对重叠节点之间的斥力和引力做调整，防止节点过度聚拢。本发明不但可以展示大规模网络的社区结构信息，还有简单、易于实现和布局速度快等优点。

说明书

技术领域

本发明属于信息可视化领域，具体是一种能够展示大规模网络中社区结构的可视化布局算法。

背景技术

可视化布局是信息可视化中的重要组成部分，通过研究可视化布局算法来最大化呈现清晰的网络结构，是目前提高可视化绘制效果和方便人们理解数据信息的有效途径。社区结构是网络的重要特性，同时也是分析和研究大规模数据的突破口。通过布局算法展示社区结构信息，有利于人们分析和理解大规模网络数据。现有力导引方法没有考虑网络的社区结构信息，无法展示网络中的社区信息。为了解决力导引可视化布局方法大都无法展示复杂网络具有社区结构这一特性，研究者们通过结合社区划分算法，提出了具体的解决方案。

朱志良等人在《计算机辅助设计与图形学学报》第23卷第11期上发表了题为“基于复杂网络社区划分的网络拓扑结构可视化布局算法”的文章，该文提出了一种基于社区划分的网络布局算法。该算法首先利用复杂网络社区发现算法对网络中的节点进行社区划分，将每个社区抽象为一个节点，以社区间的关联为边构建新的网络。根据物理类比方法确定社区中心位置，同时依赖社区规模确定社区的布局范围，之后通过条件择优的方式填充社区内的网络拓扑布局。

公开号为CN101741623A的中国发明专利公开了一种网络技术领域的网络可视化方法。该方法采用基于模块度指标的社区划分方法对网络进行层次划分，依据现有的社区划分方法优先对网络进行聚类，根据划分结果进行布局。公开号为CN104217073A的中国发明专利公开了一种网络社区引力导引的可视化布局方法。该方法在力导引算法的基础上加入了社区引力，将K-means算法引入社区引力中，实现在布局的同时完成节点的聚类。

现有社区布局方法存在以下缺点：(1)算法中社区引力建模复杂，计算效率低；(2)算法步骤复杂，不适用于大规模网络布局。

发明内容

针对以上技术的不足，提出了一种优化社区引力建模，降低社区引力的计算时间复杂度的面向大规模网络的社区布局可视化方法；本发明的技术方案如下：一种面向大规模网络的社区布局可视化方法，其包括以下步骤：

101、获取社区网络中节点的空间位置，将节点进行空间分解，同时计算节点的度数；

102、根据步骤101得到的节点的度数和空间位置，确定节点之间的引力和斥力；

103、根据社区发现算法得到的社区划分结果，计算同一社区内有边相连的节点之间的社区引力；

104、根据步骤102得到的节点引力、斥力和和步骤103得到的社区引力，计算节点的位置，使得同一社区内的节点相互聚拢，不同社区内的节点相互分离，当系统温度达到最小值时完成社区布局。

进一步的，步骤101利用层次空间分解法将节点进行空间分解，每个空间中包含限定数量的节点，空间内的所有节点对外视为一个超级节点，超级节点的度数为该层次空间内所有节点的度数之和。

进一步的，步骤101计算计算节点的度数具体为：根据网络的结构信息计算节点的出度和入度，节点的度数为节点出度和入度之和。

进一步的，步骤102计算节点所受的节点引力和节点斥力的公式具体为：根据节点的度数deg(n)、节点之间的距离d(n₁,n₂)和边的权重w(n₁,n₂)，调用公式(1)计算节点之间的引力f_a和斥力f_r，斥力存在于所有的节点对，引力只存在于结构相邻的节点对之间；

其中k为可调节常数。

进一步的，步骤103中计算社区引力具体为：社区引力只存在于同一社区且有边相连的节点之间，根据节点之间的距离d(n₁,n₂)和边的权重w(n₁,n₂)，调用公式(2)计算社区引力，使得同一社区内的节点相互聚拢，形成社区结构；

进一步的，步骤104节点布局的布局原则为：相邻节点之间靠近，不相邻节点之间远离，在此基础上，同一社区内相邻节点之间靠近，系统温度的调整采用模拟退火原则，系统温度降到最低时，布局完成。

本发明的优点及有益效果如下：

本发明解决社区布局算法不适用于大规模网络布局的局限性，简化算法步骤和力的计算，优化社区引力建模，提出了一种面向大规模网络的社区布局可视化方法。该方法在力导引布局的基础上，引入空间分解模型，降低节点之间斥力的计算时间复杂度。节点度数控制节点斥力的大小，使得度数大的节点之间相互远离，社区结构更加清晰。同时优化社区引力建模，降低社区引力的计算时间复杂度，能够适用于大规模网络的社区布局。

附图说明

图1是本发明提供优选实施例面向大规模网络的社区布局方法流程图；

图2本发明的布局方法在Advogato数据集上的布局效果。

具体实施方式

以下结合附图，对本发明作进一步说明：

参见图1所示，整个系统在节点斥力、节点引力和社区引力的作用下达到平衡。方法在力导引布局的基础上，引入空间分解模型，降低节点之间斥力的计算时间复杂度。节点度数控制节点斥力的大小，使得度数大的节点之间相互远离，社区结构更加清晰。同时优化社区引力建模，降低社区引力的计算时间复杂度，能够适用于大规模网络的社区布局。最后针对节点重叠问题，对重叠节点之间的斥力和引力做调整，防止节点过度聚拢。

设G为一个网络，用节点和边表示为G(V,E)，其中V为n个节点的集合{v₁,v₂,...,v_n}，E为m条边的集合{e₁,e₂,...,e_n}，G被划分为了k个社团{C₁,C₂,...,C_n}。如果将布局问题等价于物理中物体的受力情况，那个节点将在三个力的作用下达到平衡：节点间的斥力、节点间的引力和社区引力。具体的实施步骤如图1所示为：

A1：在初始阶段，根据网络的结构信息计算节点的度数，节点的度数由节点出度和入度决定。

A2：根据节点现有的位置，对所有节点进行空间分解，如利用层次空间分解法。每个空间中包含限定数量的节点，空间内的所有节点对外视为一个超级节点，超级节点的度数由该层次空间内所有节点的度数决定。

A3：计算节点所受的节点引力和节点斥力，引力和斥力主要用来维持系统的平衡和减少边交叉。根据节点的度数deg(n)、节点之间的距离d(n₁,n₂)和边的权重w(n₁,n₂)，调用公式(1)计算节点之间的引力f_a和斥力f_r。斥力存在于所有的节点对，引力只存在于结构相邻的节点对之间。

$>\left(\begin{array}{c}{f}_a=k*d(n_1,n_2)*w(n_1,n_2)\\ f_r=\frac{k^2*\mathrm{deg}\left(n_1\right)*\mathrm{deg}\left(n_2\right)}{d(n_1,n_2)}\end{array}\right)---\left(1\right)$>

A4：计算社区引力，社区引力只存在于同一社区且有边相连的节点之间。根据节点之间的距离d(n₁,n₂)和边的权重w(n₁,n₂)，调用公式(2)计算社区引力，使得同一社区内的节点相互聚拢，形成社区结构。

A5：根据上述计算得到的节点斥力、节点引力和社区引力，结合系统温度，计算节点移动的位置。每次布局迭代节点的移动范围会随着系统温度的降低而逐步减小，当温度降低到一定程度时，布局达到稳定状态。对于重叠的节点对，调整节点之间的斥力和节点之间的引力，防止节点过于聚拢。

A6：当系统的温度达到给定的最小值时节点调整结束，否则执行步骤A2。对于温度的调整，可使用模拟退火原则，系统初始状态时温度较高，再慢慢降低温度，直到温度达到最小值。

图2本发明的布局方法在Advogato数据集上的布局效果。选择了公开数据集Advogato进行试验。Advogato网络描述了社交网络中的信任网络，顶点代表用户，边代表用户之间的信任信息。该数据集包含5042个顶点和39227条边。布局效果如图2所示，可以看出该算法能够明显反映出网络的社区结构特性。

以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。