论文：E-Map: A Visual Analytics Approach for Exploring Significant Event Evolutions in Social Media
作者：Siming Chen, Shuai Chen, Lijing Lin, Xiaoru Yuan, Jie Liang, Xiaolong Zhang
发表：IEEE VAST 2017
介绍
社交媒体在信息与重要事件的传播与扩散中起了重要作用。当一个重要事件在社交媒体中出现时，会引发一系列的关注者转发、评论该问题，并产生新的意见。一个重要事件往往有上百万人牵涉其中。因此，社交媒体能很好的反应事件的演变过程、激发人们参与事件讨论的原因。关于某个重要事件，人们关注的问题包括：人们在社交媒体上讨论什么？信息是如何传播的？事件的演变是如何发生的？
挑战与贡献
然而，复杂的社交媒体数据对认知与了解重要事件及其发展带来的挑战。首先，某个社交媒体中的重要事件会涉及到庞大的人群，尤其是当被转发上百万次以后。其次，社交媒体上的消息具有多样性。发布的消息，被转发后会增加很多额外的内容，包括简单的评论和激烈的讨论，需要专门的工具来挖掘消息语义中的主题。最后，事件的演变无法被预知，一个事件往往会激起人们对更多事件的激烈讨论。
本文的贡献主要分为三部分。一，提出了针对社交媒体数据中事件演变与传播的地图隐喻可视化方法。二，之前的用户行为分析都是将用户行为作为空间中的对象，而本文将研究核心用户对时间演变的影响。三，本文提供了两个基于真实数据的案例分析。
数据
本文所使用的数据是从新浪微博上爬取的，每一条新浪微博消息都带有井号标注的主题与消息中的若干关键字，爬取得到的每一条数据包括：时间点、消息 ID、转发消息 ID、内容、用户。本文将要研究的事件，是指与一个井号标签或关键字有关的社会现象或故事，包括<时间，人物，转发的消息，主题>。主题在本文中是一个很泛的概念，包括某些语义、关键字、话题。本文对事件的定义抛弃了地理位置属性，因为不是所有的社交媒体都包含位置信息的。
上图显示了包含了一个事件的所有感兴趣的特性。
D1：新的话题参与者、观点、讨论会产生一系列的子事件，从而出现不同的阶段。
D2：拥有重要影响力的核心用户与受害者都能引导事件的发展。
D3：不断的转发将事件暴露给了公众，并导致信息扩散，过程中会产生新的意见与素材。
D4：讨论的主题在整个发展过程的不同阶段中会合并、分裂、消失。
E-MAP 设计
上图为 E-MAP 的设计，作者之所以选择地图隐喻是因为，1.地图能提供结构化的、具有语义的空间来组织信息。2.用户对地图这个图形表征非常熟悉。其中，时间信息通过上图右上角的颜色条映射，每一个地图上的元素分别对应以下事件中的特征。
城市：关键字。每条消息一个。最具代表性。大小表示包含这个关键字的消息数量。城市间的距离表示关键字在转发关系中的距离。
城镇：附属于一个城市的消息。与城市的距离表示距离第一条包含该关键字的消息发布的时间差。时间上相近的小时可以合并为城镇。
区域：一个城市与其附属城镇的的领土。虚线表示，区域大小与形状由其中的城市、城镇数量决定。区域之间的距离表示，区域所代表关键字之间的转发关系远近。
河流：存在很多的转发消息，同时包含河流流经区域的关键字。
陆地&岛屿：主题与关键字之间的分布。
E-MAP 构造方法
上图展示了 E-MAP 的构造方法，共分为两个部分：图构造与地图构造。构造过程中，处理的图节点包含消息、关键字、虚拟时间节点三种，图中的边关系包含关键字-关键字、关键字-时间、关键字-消息三种。
（a）计算初始图布局：分时间段计算关键字，在每个分段内计算 TF-IDF，得到 K,T 节点及其关系。再找包含关键字的消息：一个包含关键字 A 的消息转发自一个包含关键字 B 的消息。根据找到的所有节点与关系，计算初始力引导布局。
（b）优化图布局：在加上 KM 关系与 M 节点，重新优化布局。因为 M 节点太多，所以其实只加上最重要的 K 节点的相应 M 节点。
（c）计算 VORONOI 分割：用 4096 个种子点计算 VORONOI 三角网格。根据图结构中计算的 K,M 位置将节点放到网格中，并用一个高斯核函数计算 VORONOI 网格点的密度。
（d）计算区域边界：每个三角网格划分给离他最近的城市（K）。网格区域的边缘就构成了城市之间的分界线。在每个区域中，根据消息发生的时间，重新离城市由远到近排列。并将时间上相近的消息聚合。
（e）构造河流：对于 KK 关系，从起始 K 节点开始，到终止 K 节点，链接中间所有经过的三角网格的中心。给定转发的消息的影响力，根据阈值筛选消息，保证筛选完大概 5-10 条河流。
（f）合并陆地、产生岛屿：根据步骤（c）所算的网格节点上的密度分布，将密度大于 0 节点圈起来，密度为 0 的则不作任何处理，这样就形成了陆地跟岛屿。
（g）最终布局优化：1.利用 PD 算法计算陆地腐蚀的形状。2.调整河流。根据每个三角网格的中心计算差值函数，让河流看起来更平滑。
所有构造算法的复杂度均为 O(n),数据预处理的时候树结构遍历跟排序算法复杂度 O(nlogn)。
系统界面与可视分析流程
上图为系统界面。本文提出的可视分析流程共分为三个部分：
时空总览：a、b 图。其中，在 b 图中，纵轴上关键字按他们出现的时间排序，关键字的颜色表示该关键字出现的峰值时刻在哪里。横轴表示时间，每个 block 的高度及颜色都表示该时间段内出现该关键字的消息数量。最上面一行最宽的是每个时刻消息总和。
多层次的时空探索：涉及到 a-g 图及其中的所有交互。交互包括：时间轴上的刷选与导航、传统的地图交互（缩放、选择、导航）、地图上的多边形刷选生成文字云。其中，通过在地图上的交互，用户可以选择一个城市，高亮消息内容，并在关键词关系列表高亮。选择城镇后，在消息列表里展示包含这个城市关键字的所有消息内容，并看到消息发送的时间与用户。
事件演变分析。要探索的事件演变过程中的两项重要内容：用户轨迹与用户联系。其中，用户轨迹指发布众多消息的用户会在城镇之间移动。能体现消息与转发消息之间的主题变化。黑色的曲线表示。线的粗细表示。用户联系指人们发布的消息能被不同的人转发。这个行为如果影响力很大的话通过河流展示（因为有阈值筛选），如果不是的话用灰色的直线表示。系统中一共提供两种探索模式，单项模式与聚合模式。其中，单项模式指在城镇级别上展示每个单个链接。聚合模式则将所有隶属于某个城市的城镇消息聚合，通过城市之间的关系展示聚合后的链接。
案例分析-Kim Jong-nam 之死
本案例中，搜索的主要关键字为 Kim Jong-nam，韩国，马来西亚。包含 222,678 条消息、130,197 个用户、涉及的时间区间为 2017.02.14-2017.03.17。Kim Jong-nam 为朝鲜主席金正恩的哥哥，2.14 在马来西亚死亡，并且有证据表明是毒死，因此成为微博上的重要热点事件。地图上可以看到，“Malaysia, North Korea, Kim Jeongnam, Kim Jeong-eun, Ambassador, Assassination 都是重要关键字。
可以看到，该事件的发展阶段主要分为四部分。
2.14-2.24, 尚未官方宣布是谁死了，但是群众已经辨认出来是 KIM JONG-NAN，并开始讨论。人讨论的内容包括：为什么刺杀发生在拥挤的马来西亚机场，以及警方官方宣布一些调查结果，是不是弟弟为了避免政权争夺杀了哥哥。
2.24 号，一个关于 KIM JONG NAM 是被毒害的新故事被发布。新出现的关键字包括：VX 、神经、毒性、生化武器。可以看出公众对非法生化武器的恐慌。
2.28-3.7 号，有新的话题在被讨论，例如，马来西亚在 3.4 号释放了一个朝鲜嫌疑犯，因为缺乏拘捕他的证据。马来西亚将韩国大使送出马来西亚。朝鲜决定停止对中国的稀土出口等等。
美国与韩国受到了波及。被讨论的对象包括 THAAD。
讨论
此外，本文提出的方法也包含了若干问题：
地图上允许存在的最大城市或城镇数量为 10^4，但是人为能感知到的对象数量为 10^3
一条消息一个关键字
预处理比较慢
本文的优点包括：
结合节点链接与空间填充方法的地图隐喻设计
抽象出的社交媒体事件特征与地图中对象的对应关系明确并且合理
对复杂时空数据分析的实现
本文的缺点包括：
地图隐喻设计对理解社交关系网络的歧义
城市/城镇之间的距离度量不能准确表示节点之间的相似性
地图中展示的也并不是标准的社交网络
文章中没有 user study（包括之前那篇 D-MAP）
✉️ zhangtianye1026@zju.edu.cn