技术摘要：
本发明公开了一种社交网络布局方法、系统及其存储介质，解决海量节点的复杂社交网络的图形化问题，通过本技术的应用实施，BH算法在社交网络方面的应用可以进一步优化，以提升计算速度，同时提高产率、质量、精度和效率；采用质量距离比控制Node和非叶节点两点距离之间  全部
背景技术：
社交网络由人和人际关系构成，将社交网络图形化，就得到代表人的点和代表关 系的线组成的网络图。 改变图的布局，把存在关系的点拉近，不存在关系的点推远，通过这种变化，可以 让图中的重要点，主要关系，关系网，聚集群等更加明显。 力导向布局图，又叫力学图，是一种建立在力学仿真模型基础上的图，图形中的点 在系统中的各种力的作用下不断运动，达到图形变化的效果。 Links力，连接两个点的边，对两个点存在牵引力，牵引力的大小跟点之间的距离 成正比。 N-Body力来源于N-Body问题，设定了初始位置，质量，速度的N个点(天体或粒子) 在相互作用力下的运动过程，节点间的相互作用力可以是宏观的万有引力， 也可以是微观的库伦斥力。N-Body问题广泛用于天体物理，等离子体物理，分子动 力学等。 由上可知，力导向图同时施加Links力，和N-Body力可以很好的完成社交网络的这 个布局变化。 目前已经有人将力导向图用于社交网络数据的可视化应用上，并取得了不错的效 果，但是在N-Body力上，采用的是PP算法，即计算所有点两两间的作用力，这种算法的优点 是精度高，实现简单，在N的数量小的情况下有不错的效果。而随着N增大，PP算法的时间消 耗成几何增长，让人无法承受。
技术实现要素：
本申请的主要目的在于提供一种社交网络布局方法、系统及其存储介质，通过低 精度高效率Barnes-Hut(BH)算法来实现N-Body力的模拟，以解决目前的问题。 为了实现上述目的，本申请提供了如下技术： 本发明的第一目的在于提出一种社交网络图布局方法，包括如下步骤： S100、数据点初始化处理：初始化社交网络图的的所有点，根据点总数确定图的范 围(W，H)，并将点随机分布到社交网络图中，保证点不重叠，并为每个点设置质量；计算图总 质量M； S101、构造四叉树：利用BH算法将图形空间递归的等分为四个小区域，直到每个区 域仅包含一个点Node；根据上述社交网络图划分原则创造四叉树，树的根节点代表区域，叶 节点代表Node，自下而上计算每个区域的总质量和区域的质心，同时记录在根节点； S102、计算BH四叉树根节点的质量和质心：对BH树，从根节点按照深度优先的顺 5 CN 111597664 A 说　明　书 2/7 页 序，依次计算每个非叶节点的质量m，质心(x，y)，在社交网络图中质量占比Rm； S103、计算每个节点N-Body力：从ROOT开始遍及BH树，对每一个网络连接端点计算 其作用力，从根节点出发遍历四叉树，计算合力；为了判断确定远近不同的Node和非叶节点 两点距离之间是否产生有效作用力，采取质量距离比进行判定，质量距离比为Rml，质量距 离比Rml的计算公式为：Rml＝RM/RL，其中RM为区域质量和图形总质量的比值，RL为点和区 域质心距离和图形宽度的比值，设定其阀值为a；如果Rml>a，则计算区域对点的作用力； S104、计算每个节点的Links力； S105、根据合力移动：在单位时间根据作用力移动每个点； S106、如果得到移动后的社交网络图，即结束，如果没有得到移动后的社交网络 图，则返回S101步骤的前一步，重新构造四叉树。 其中，在步骤S103中，计算合力时：如果Node和非叶节点的质心距离远，则把此非 叶节点包含的分支作为整体，位置为质心，质量为分支总质量，来计算合力；如果Node和非 叶节点的质心距离近，则递归遍历此节点的所有子节点；如果为叶子节点，则直接计算作用 力。 进一步地，在步骤S100中，对任意一个点Node，根据距离远近，可以认为一部分点 距离Node较近，剩余的点距离Node较远：距离较近的点，两点间互相作用力大，直接计算作 用力；距离较远的点，可以认为相互作用力较小，把距离较远的点看作一个整体，联合起来 计算作用力。 进一步地，在步骤S101中，四叉树的构造方法采用四分法，根据步骤S100的图信息 创建一个空的四叉树，根节点为ROOT，依照图划分原则把图上的点依次放到建立的四叉树 上，四叉树建造步骤具体为： 从ROOT节点开始检查； 如果节点不包含节点，也不包含分支，就把新的点放到当前节点； 如果节点包含分支，根据四分法确定新的点属于第几象限，然后递归进入对应的 分支安放新的点； 如果节点包含一个其他的图形点，就将此节点对应的区域划分成四个象限，分别 将原来包含的点和新的点递归的放到对应的分支。 进一步地，质量距离比Rml的范围为0.8-1.2。 进一步地，在步骤S102中，BH四叉树根节点的质量和质心的计算步骤具体为： 在此设：根节点的质量为m，子节点的质量即为m1、m2、m3和m4，x是根节点在x轴上的 坐标，y是根节点在y轴上的坐标，4个子节点的位置坐标分别为(x1，y1)、(x2，y2)、(x3，y3)、 (x4，y4)，质量分布为m1，m2，m3，m4，则有： m＝m1 m2 m3 m4； x＝(x1×m1 x2×m2 x3×m3 x4×m4)/m； y＝(y1×m1 y2×m2 y3×m3 y4×m4)/m； Rm＝m/M。 进一步地，在步骤S103中，计算每个点N-Body力的步骤为： 在此设：点的质量为m0，点在x方向的移动速度Vx，点在y方向的移动速度Vy，计算图 点和数节点的距离r，则有： 6 CN 111597664 A 说　明　书 3/7 页 dx＝x2-x0， dy＝y2-y0， r＝sqrt(dx×dx dy×dy)， RL＝r/W， Rml＝RM/RL， 如果Rml>a，计算区域对点的作用力； 同时，计算库伦系数k：k＝100×w×w/N， Fk＝k×(m0×m)/(r×r)， Vk＝Fk×t/m0， vx＝vx Vk×dx， vy＝vy Vk×dy。 进一步地，在步骤S104中，Links力的计算步骤包括： 胡克系数：h＝0.005×w×w/N， Fh＝h×r， vx＝vx Vh×dx， vy＝vy VK×dy。 进一步地，在步骤S105中，单位时间内根据作用力移动的每个点的位移计算公式 为： x0＝x0 vx×t， y0＝y0 vy×t。 本发明的第二目的在于提出一种社交网络图处理系统，包括：节点初始化模块、构 造四叉树模块、节点质量和质心计算模块、节点N-Body力计算模块、节点的Links力计算模 块和判断模块； 节点初始化模块：初始化社交网络图的的所有点，根据点总数确定图的范围(W， H)，并将点随机分布到社交网络图中，保证点不重叠，并为每个点设置质量； 构造四叉树模块：利用BH算法将图形空间递归的等分为四个小区域，直到每个区 域仅包含一个节点Node； 节点质量和质心计算模块：对BH树，从根节点按照深度优先的顺序，依次计算每个 非叶节点的质量m，质心(x，y)，在社交网络图中质量占比Rm； 节点N-Body力计算模块：从ROOT开始遍及BH树，对每一个网络连接端点计算其作 用力，从根节点出发遍历四叉树，计算合力； 节点的Links力计算模块：用于计算每个节点的Links力； 判断模块：根据合力移动每个节点后，对比是否能够得到移动后的社交网络图，能 够得到即结束，不能得到返回构造四叉树模块，再次重新构造四叉树。 本发明的第三目的在于提出一种社交网络图处理的存储介质，存储有可执行指 令，用于引起处理器执行时，实现权利要求1至10中任一项所述的社交网络图处理方法。 与现有技术相比较，本申请能够带来如下技术效果： 1、通过本技术的应用实施，BH算法在社交网络方面的应用可以进一步优化，以提 升计算速度，同时提高产率、质量、精度和效率； 7 CN 111597664 A 说　明　书 4/7 页 2、采用质量距离比控制Node和非叶节点两点距离之间是否产生有效作用力，降低 了计算精度，减少了计算次数，从而提高了计算效率，使用质量距离比来判断是否计算两点 作用力，可以省略质量很小但距离在距离阈值内的点的作用力计算，同时又能将质量较大， 距离超出距离阈值的点的作用力计算，更加符合实际情况，计算结果让点分布更合理； 3、计算精度和次数的降低，节省了能耗、原材料、工序，使得加工、操作、控制、使用 更为简便。 附图说明 构成本申请的一部分的附图用来提供对本申请的进一步理解，使得本申请的其它 特征、目的和优点变得更明显。本申请的示意性实施例附图及其说明用于解释本申请，并不 构成对本申请的不当限定。在附图中： 图1是本发明的实施流程图； 图2是简单社交网的初始点分布图； 图3是根据算法创建好的四叉树模型图。