基于自我中心线的动态自我网络可视分析方法(Egocentric Analysis of Dynamic Networks with Egolines)

动态网络,其结构随着时间不断发生变化,是个应用领域相当广泛的数据结构,比如社交媒体交流网络,学者之间的合作网络等。相关的研究相当的丰富(图1)。基本的展示形式有两种,点边形式(Node-link Diagram)和矩阵形式 (Matrix Diagram);时间映射方式主要有两大类,基于时间轴的映射和基于动画的映射。这些方法,关注的往往是整个网络。另一种重要的动态图研究方法,是自我网络分析(egocentric analysis)。相比于关注整个网络的分析,自我网络分析关注的是中心点(ego)及其相关联的节点(alters)构建的子图。

egolines-p1

图1 动态图基本可视分析方法

可视分析自我网络的动态变化,对探索中心节点与周边节点之间的相互影响,有重要作用。为更好地分析、总结自我网络相关的可视分析任务,作者们采访了三个网络分析专家,并将相关问题总结整理成三大类,如下所示:

A: 动态自我网络的演变

       A1: 出现,消失和重现。比如,特点节点的生存周期有多长?

       A2: 聚集和分裂。比如,是否存在多个群簇聚集成一个群簇的现象?

       A3: 稳定和替代。比如,节点在自我网络中稳定么?

       A4: 属性变化趋势。比如,整体上,自我网络的大小变化趋势是怎样的?

B: 特定时间步的自我网络分析

       B1: 可通性。比如,哪些节点与中心节点直接相连?

       B2: 连接性。比如,哪些节点是两个不同节点的共同连接点?

       B3: 连接属性。比如,节点的介数中心性(betweenness centrality)是多少?

C: 自我网络

       C1: 总览图,关注区域及其上下文。比如,自我网络的结构特点是什么?

       C2: 分布。比如,自我网络中节点的数量随时间的变化情况是怎样的?

为更好地可视分析这些问题,结合地铁图中得到的启发,他们设计了EgoLines(图2)展示动态自我网络。在这个可视化中,自我网络中每个节点用类似地铁线的形式表示。每个时间步的自我网络拓扑结构,用矩阵形式表示,采用类似地铁图中站点的方式,用白色圆点映射两节点之间的关联关系。线段的颜色与节点在自我网络中的群簇对应。此外,为支持用户更便捷地分析特定节点的行为,采用直角矩形块表示节点初次进入网络,采用虚边矩形和虚线表示节点的暂时离开。

egolines-p2

图2 EgoLines的可视展示形式

图3是EgoLines系统界面图,主要包括四大部分:EgoLines主界面,展示当前用户选择的中心节点及其自我网络(图3(a));点边形式展示数据集中整个动态网络的超图(图3(b));列表形式展示数据集中所有可能的自我网络及网络的属性,比如采用直方图展示自我网络中的节点数随时间的变化等(图3(c));系统支持丰富的交互方式,具体交互面板如图3(d)所示。

egolines-p3

图3 EgoLines系统界面图

接下来,我将通过真实数据分析案例,阐述系统的使用方法及其有效性。该案例分析的是因财务造假破产的安然公司内部邮件数据,涉及142个员工在1998年11月到2002年6月的邮件交流。首先,我们通过总览图,观察邮件交流网络的整体结构(图4(a))。调整滑块,查看每个时间步,交流网络的拓扑结构,我们发现网络节点和边的数量越来越大(图4(a)中,2001年6月的网络比1999年6月的网络,在节点数量和点边密度上,大很多),说明142个员工之间的交流越来越频繁。随后,在列表中查看所有节点自我网络的统计属性(图4(b))。根据网络的点边密度排序,发现排在前两位的是Delainey和Lavorato(两位都曾是安然公司的ceo)的自我网络。通过查询方式,可以快速获取Skilling和Lay(两位是曾是安然公司的ceo)的自我网络统计属性。我们发现,四位ceo在安然公司的工作时间,基本一样(图4(b),统计直方图,x轴上的数据分布基本一样);但他们的自我网络活跃程度非常不一样(图4(b),统计直方图,y轴上的数值分布差异大)。

之后,我们查看了Skilling的自我网络(图4(c))。Skilling的自我网络在2001年4月和2001年8月急剧变大(图4(c-i)和图4(4-ii),矩阵大,涉及的节点多)。前者可能与Skilling口头攻击华尔街一位质疑公司财务的分析师事件相关;后者跟Skilling从ceo岗位辞职相关。KL线(图4(c-v))描述的是Lay与Skilling的交流随事件的变化情况。我们发现二者之间的交流非常少,Lay只在2001年4月和2001年8月与Skilling有直接的邮件交流。但如果分析Skilling自我网络其它节点与Lay的交流,我们可以发现在2001年4月,虽然只有五个节点与Lay有交流(图4(c-v)中,KL线上只有5个白点),但其中4人通过Lay与安然公司的高层进行交流(图4(c-i)中黑色的曲线,高亮了其它节点与KL的交流),比如DD安然公司前董事长(图4(4-vi))。

egolines-p4

图4 案例分析结果示意图

随后,我们查看了Lay的自我网络(图4(d)),发现2001年8月,Lay担任安然公司CEO的第一个月,与Lay直接邮件交流的员工急剧增多(图4(d-i),矩阵非常的大)。但随后,网络急剧减小,在2002年6月(Lay离职),直接通过邮件与Lay交流的员工,几乎没有。

如果我们比较Skilling和Lay早期的自我网络结构(图4(c)左侧图和图4(d)右下角图),可以发现他们与SK(副董事长)和LK(董事长)都保持着长期的交流。这从某个角度说明,Skilling和Lay的交流可能远比邮件数据显示的交流频繁。

作者们还通过一个控制类实验,分析EgoLines表现形式的性能。他们将EgoLines与另外两种可视化形式进行了比较(图5)。实验要求参与者采用三种可视化形式,完成两大类任务。然后根据用户完成任务的时间,准确率以及使用体验,分析三种可视化形式的性能。

egolines-p7

图5 控制实验使用的,三种基于时间轴的动态图表示形式

图6展示了实验分析结果。我们可以发现,EgoLines表现形式在分析时序类任务和部分拓扑类任务上,性能非常的好;但在查找起桥梁作用的节点任务上,EgoLines的表现非常差。这可能是因为EgoLines采用矩阵形式,展示网络的拓扑结构,不够直观。

 

egolines-p6

图6 实验分析结果。整体上,EgoLines表现优于另两种表现形式。但在拓扑结构类任务,查找起桥梁作用的节点上,EgoLines的表现最差。

总体上,EgoLines[4],是一种新颖的分析动态自我网络随时间演变的可视化形式。这种表现形式采用类地铁图的映射方式,直观新颖。但EgoLines不适用于处理较大的动态图数据。当时间步多,每个时间步网络大的时候,EgoLines不能給用户一个很好的总览图。也许进行一定程度的聚类,可以处理此类问题。此外,EgoLines采用矩阵形式展示每个时间步自我网络的拓扑信息,并不适用于分析拓扑结构类任务。

 

引用:

[1] B. Bach, E. Pietriga, and J.-D. Fekete. 2014a. GraphDiaries: Animated transitions and temporal navigation for dynamic networks. IEEE Transactions on Visualization and Computer Graphics 20, 5, 740–754.

[2] B. Bach, E. Pietriga, and J.-D. Fekete. 2014b. Visualizing Dynamic Networks with Matrix Cubes. In Proc. SIGCHI Conference on Human Factors in Computing Systems. 877–886.

[3] van den Elzen, S., Holten, D., Blaas, J. and van Wijk, J.J., 2016. Reducing snapshots to points: A visual analytics approach to dynamic network exploration. IEEE transactions on visualization and computer graphics, 22(1), pp.1-10.

[4] Zhao, J., Glueck, M., Chevalier, F., Wu, Y. and Khan, A., 2016, May. Egocentric Analysis of Dynamic Networks with EgoLines. In Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems (pp. 5003-5014). ACM.

发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>