7.2.2 基本可视化方法
1.社团发现算法
社交网络的数据量大和小世界模型的特性,使得普通布局算法在布局的时候无法展示出每个节点的位置,即使展示出来也是线条交织无法有效观察其中的规律。最好的方法就是对网络进行社团发现从而从整体上理解网络的结构。社团发现算法有启发式的GN(girvan-newman)算法、CPM(clique-percolation-method)算法以及基于优化的FN(fastnewman)算法。FN算法由于执行效率高、布局效果好而逐渐被广泛应用。
FN算法工作流程如下。
(1)把所有节点看成社团。根据网络中的边建立矩阵E(eij):
其中,元素eij表示连接两个社区边的比例;aij表示与社区相连的边的比例。
(2)对模块化函数进行优化,沿着Q函数该变量最多的方向合并网络中两个相邻的社团在这个过程中得到一个模块度增量ΔQ:
ΔQ=eij+eji-2aia j
(3)重复执行上一步直到最后只剩一个社团。算法的流程如图7.14所示。
聚类结束后开始记录社团信息。社团数每减少至上次的一半的时候就记录为一个层级,这样就得到层级L 1,…,L 2,每层的节点数大致为M,M/2,…,1,生成一棵网络社团的层次关系树如图7.15所示。
图7.14 FN算法流程图
图7.15 层次树生成图(加深的颜色代表了层次树生成的顺序示意)
分层完成后对每一层节点进行展开布局,展开过程中新加入点的坐标根据质心算法确定,公式如下:
图7.16给出的是用FN算法进行社区发现得出的结果。
图7.16 FN算法布局图
2.力导向布局算法
力导向布局算法始于弹簧算法,在其发展过程中出现过众多的改进算法。但FR的出现才真正地使得力导向布局算法的运算符复杂度有了明显改观,图形布局效果也更加明显。
FR算法实现的基本假设是:任意两个有联系的点对之间应该靠近,同时点和点之间不能过分靠近。给出FR的数学模型如图7.17所示。
定义一个H*W的矩形,给定节点对U、V及其坐标P u和P v,
(https://www.daowen.com)
计算步骤如下:
(1)计算相连节点之间的引力
f r（u,v）=d 2/k
(2)计算所有节点之间的斥力
f r（u,v）=k 2/d
(3)在引力和斥力的共同作用下移动节点
虽然FR算法相比之前的算法已有一定的改观,但经过分析可知其算法复杂度仍然为O(V2+E),所以在对大规模节点进行布局的时候仍然效率比较低。
图7.17 FR算法布局图
Hu-Yifan算法在FR基础上对图形布局质量和数据的计算量进行了优化。首先Hu-Yifan算法在斥力的计算中引入超级节点,使得时间复杂度降低,如从O(V2+E)降到O(|V|log|V|+E),同时在节点之间的力的计算中引入调节系数让图形布局得更加均匀。
超级节点的设计思想是:如果一个节点i和它相邻的一簇节点S之间满足足够远的条件,那么在计算它们之间的斥力的时候节点簇将被视为超级节点。两点间的斥力为:
节点i和超级节点S之间的距离判定公式为:
其中,d s表示超级节点所占区域的边长,θ是临界值,值越小计算代价越大。Hu-Yifan算法在计算斥力的时候引入参数P进行调整:
算法结束之时,计算本次和上次系统的能量值之比决定节点的位移量;Hu-Yifan算法的布局结果如图7.18所示。
图7.18 Hu-Yifan算法布局图
3.用户影响力及意见领袖
用户发布信息来表达自己对各种事情的看法,与此同时他们也能从网页浏览中了解到其他人对事情的态度和看法。这样,个人或者群体之间就以各种方式影响着对方并形成一张“发布→浏览→转发”的传播扩散网。假设在用户X周围围绕着一大批粉丝。在某个社会热点事件发生的情况下,X发布了一条微博,那么X的粉丝之间形成的虚拟群体将有可能进行更深层次、更高频率的沟通。在传播过程中,信息可能传到六层以外,这样就给用户带来更多的关注。因此,我们可以定义用户影响力如下:用户通过发布信息促使他人评论或者转发的潜力。就微博而言,用户之间的关系可以是双向的也可以是单向的,众多的用户由此就形成一个错综复杂的虚拟网络。在这个网络中,每个用户既是信息源又是信息的转发者。因此从传播和交互的角度看,微博的功能主要有:发布、关注、转发和评论。经过上述对微博传播特性和交互模式的简要分析可知,节点在网络中的影响力主要取决于如图7.19所示指标。
图7.19 评价指标体系图
在求出各个微博用户的综合影响力的基础上,绘制用户影响力和时间片的二维平面图可以帮助发现意见领袖类型。在现实生活中,很多拥有高人气的名人在社交网络上吸引了大量粉丝,如姚晨、赵薇、谢娜等在新浪微博上圈粉七千多万人。他们在微博上积极发博或转发博文,这使得他们在微博中的影响力长期处于较高地位,我们把这种用户称作强势型意见领袖。但是,微博网络中大部分用户都属于草根用户,他们只在自己关注的小范围内进行互动。这些用户在亲身经历某件事之后在微博上发表的博文经常会得到广大用户的关注,导致其博文短期时间内得到疯狂地转发和评论并因此引起强大的社会反响。但是等到事件过后其博文受关注的程度又会回归平静。这就是短暂型意见领袖。同时,在微博中存在这样一类用户,他们之前没有感受到微博给他们的作用,平时很少在微博上互动;但是当他们感受到微博给他们带来巨大作用之后就会千方百计地去提高自己的影响力。我们把这类用户称为潜在型意见领袖。
