一种快速探索大规模图数据网络结构的可视化方案

未分类

本文是对论文思路的梳理。包含了大部分已经做完的和准备要做的事项，基本按照论文的格式来对整个思路做了一下总结，核心问题就是：如何快速的得到大规模图数据的网络结构。

前言

图数据是一类具有关系的节点的集合，包括但不限于社会网络、网页链接、文献引用等等；
可视化工作可以让问题更好的呈现，使用户更直观的发现问题；
大数据时代的来临使许多已有技术失效；
规模过大时更多的是追求速度，而非精度；
图数据变得越来越大，许多内容亟待挖掘；
降低时间复杂度，加速返回结果时间是问题的核心；

相关工作

布局算法方面：力导向，魔改力导向，基于能量方式的最优化导向
图计算架构方面：GraphLib，Giraph，GraphX
OLAP/TP方面：偏向存储，离线计算在线游览，或在线分析，Neo4j，TiTan

面向数据

真实的社会网络，实验表明在生活中构建出的网络结构大都符合幂律分布，下面实验综合分析了SNAP数据集中全部九个数据集，对度分布进行分析后发现基本都符合幂律分布。

社会网络分析的一项重要任务就是揭示社会的结构.在社会网络分析学中,社会网络是指社会行动者
(actor)及其间的关系的集合5,凝聚子群(cohesive subgroup)则是一个行动者子集合,该集合中的行动者之间具
有较强的、直接的、紧密的、经常的或者积极的关系6.进行子群的划分、比较,甚至进一步对行动者在子群内
的角色、影响进行分析,有助于分析社会网络结构,对于发现潜在关系与目标、分析团伙行为、关注与布控关
键目标等实际应用都具有重要意义.

为了验证度分布符合幂律的特点，可以分别将XY轴取ln底，那么图像会呈现一条斜率为负的倾斜直线，此斜率的大小正是（Y=cX^(-r)）中的幂r的大小，由上面的叙述可知，可以通过对数底坐标轴的呈现图像是否为一条直线来判断度分布是不是符合幂律分布的特性。下面三组是上述九个数据集中度分布十分符合幂律分布的图像。

另外，由于数据及场景的特殊性，度分布并不一定完全符合幂律分布，或者说不可能完全符合，只是接近幂律的程度有大有小，下面三组就是九中数据集中符合幂律分布程度较差的图像。

尽管这些数据在最短路径长度（最长值）、90%有效直径，平均聚集系数，闭合三角个数的程度上各不相同，且差异较大，但仍然可以看到度分布呈现偏幂律的特性，这本质上是一个社会学问题。

所以，在这里，面对幂律分布的节点，其实只有大约20%节点是重要的，且影响全局的。剩余八成节点往往是混乱和迷失的起因，
【实验|只布局20%重要节点和全部局的差异，视觉上】
这时如果我们只对这20%节点进行布局，则会产生精度问题，很明显，混乱迷失和精度有一定的反作用关系，虽然可以采用节点调整等微操作来避免，但当规模巨大时，这种方案显得十分无力，所以，真正的需要关系的问题是，精度和布局质量的权衡
【实验|视觉上或数据上的采样比效果】

方向明确
在上一章中各部分均可以对图计算进行优化，缩短计算的时间，但针对于图的布局，这是个多迭代，偏上层应用的需求，且具有一定的动态特性，其本身就需要大量的工作去优化解决，所以本文在方向上选择了从布局算法入手，试图寻求一种高效的布局算法来更直接的降低整个过程的计算代价。
现在，OpenOrd已经为我们提供了一定的解决思路，其本身可以处理规模十分惊人的图数据，当然其还是存在单机的局限，还有改进的空间.
图计算本身更多的从系统上关注计算过程，偏计算过程的底层，这里虽然也可以进行优化，但就布局算法本身而言，应用到大数据的就比较少，所以在大规模图数据的布局方面，还是应该从布局本身下手、

选择稳定的图计算框架就显得尤为重要，Spark之上的GraphX由于其出色的存储模式（2种）和继承Spark的优异性能的原因而被我们使用。

问题切入点

由上述分析，真实的网络结构会有很大的度差异性，即极易造成数据倾斜，且如果进行全图计算，在Spark集群内很容易造成计算不均匀，试想对微博内容可视化时一个partition内被随机划分进了大部分大V，而另一个partition内都是一般人，这种情况第一个partition内的负载会严重拖累整个job的进行。

大致思路

如何避免上述的问题就是需要解决的主要问题之一，思路是划分时预先预估计算代价，然后大致划分。
第二个问题是如何预估计算代价，通常有几个方面的考虑：度，邻居的度
第三个问题是如何结合幂律分布。

针对计算代价预估，主要是判断节点在结构中的重要性，由于布局算法本身的因素（全部点两两计算斥力，相连点两两计算引力），可以发现度数在计算中影响很大。

故基于度，可以过滤得到粗略结构（大致图结构）

首先根据度对全部节点进行重要性标记，
然后对节点进行重要性传播，主要考虑保留关键连接点，得到整体更新值
PageRank辅助

其次，对于过滤时筛掉的顶点，需要在合适时机给用户呈现，在粗图阶段，基本上20%的点对显示区域没有要求，即完全显示即可，但如果我们要继续显示那80%的点，显然直接显示会是2+8=10，跟从一开始效果完全一样，且不可避免的造成呈现图像的混乱和主结构的迷失。

本文的思路：按XX学说，幂律分布不仅存在于整体，同样也适用于局部，即同样对于微博，刨除大V的影响，剩余的人中仍然有少部分的意见领袖，即80%内部的20%还是起主要作用的一部分。

现在，对于粗略结构的进一步探索可以用剩余部分的20%来增量补全

如何补全？什么时机补全？这里我们假设用户在放大粗略图的局部时进行下一级别布局的补全，

如果用户选择完之后，顶点ABC三个在此区域内，那么我们返回他们到计算服务，
这里，需要一个【算法】人为限定ABC的布局落点，即如果ABC为连接的三角形
那么，在添加完第二层节点后的布局中三个点的位置应该相对保持不变，

【注意】
上述整个流程并不是离线处理形式，离线处理形式可以拿到数据后，完成一个批次的计算，得到20%数据的结构、剩余的20%数据的结构、当前剩余的20%数据的结构... 然后，在展示层每次传得坐标，服务端查找到相应的坐标的信息，然后返回，显示。
整个过程非常类似谷歌地图的格栅层级放大
但是，这里本文偏向于对类似大数据的实时可视探索，即除了第一层结构是全局结构以外，剩余结构均按用户所移动的窗口区域来实时计算。

假设10w节点200w边，第一层节点只布局2w节点，且这部分节点大部分都是互相联通的

A 0.2 + 0.8×0.2×random 大致图结构
B 局部 + 发散节点度分布×0.2 + 发散节点度分布0.8×random
C 局部 + 发散节点度分布×0.2 + 发散节点度分布0.8×random

就是通过

• ODL思想为基础
• 力导向算法为实现底层【①】
  
  • 首先，基于改进的ODL（度+邻居度）进行排序【②】，选取前20%，并标注A
  • 然后，对这20%的邻居节点按X采样比进行采样，采出节点标注为B
  • 用A+B作为第一层的骨架抽样图，进行最大空间占比【③】（不知道如何求顶点引出的全部点的个数）的力导向布局，（并近似确定图的中心O，没用到）
  • 此时可显示
  • 第二层布局时，对于剩余节点取前20%，同样对其邻居采样后共同作为此层的布局
  • 此层布局，斥力近似计算【④】（即只考虑第一层的A部分，A并不是随意动的，只在斥力大于x时就要移动）
  • 此时可显示
  • 依次类推，直到剩余节点集小于一个阈值百分比，这时把剩余的全部进行布局【⑤】
• 以上，用户可以随时在某一步终止布局，最细粒度是原数据中的点到点

问题：

• 现有的力导向算法不高效
• 如何在开始就确定该顶点发散出的总结构的占比
• 可视区域的限定如何加入

一些思考 2018.5.28

今天被老师叫去讨论，再次明确了一下思路，这里记录一下

首先是大致思路，明确了两种思路

思路一：第一次采样布局 + 第二次剩余布局（或算法一致的分批剩余布局）

思路二：第一次采样布局 + 缩放视界内的部分剩余点的布局

http://7xl5fb.com1.z0.glb.clouddn.com/mandelbrot.gif

数据集：Vike-vote
Directed graph (each unordered pair of nodes is saved once): Wiki-Vote.txt
Wikipedia voting on promotion to administratorship (till January 2008). Directed edge A->B eans user A voted on B becoming Wikipedia administrator.
Nodes: 7115 Edges: 103689
FromNodeId ToNodeId