局部网络几何可视化聚类分析：怀疑者和未决定者的识别

视觉信息学6（2022）11通过局部网络几何的可视化聚类分析识别怀疑者和未决定者郑胜辉a，d，e，刘伟，约阿希姆·吉森c，黄天一a，d，菲利普·卢卡斯c，克劳斯·穆勒ba西湖大学，中国b美利坚合众国纽约州石溪大学c德国耶拿弗里德里希-席勒大学d中国杭州西湖高等研究院e未来产业研究中心，杭州，中国ar t i cl e i nf o文章历史记录：2022年4月9日收到收到修订版，2022年5月15日接受，2022年2022年7月16日在线发布保留字：图形/网络数据高维数据可视化社会科学和信息科学中的可视化数据聚类协调和多个视图a b st ra ct所谓怀疑论者和未决定者，我们指的是集群社交网络中的节点，这些节点不能轻易地分配到任何集群中。这样的节点通常位于集群之间的界面（未决定的）或它们的边界（怀疑论者）。识别这些节点在诸如选民定位的营销应用中是相关的，因为由这些节点代表的人通常比深入集群内的节点更有可能在营销活动中受到影响。到目前为止，这个识别任务还没有像其他网络分析任务（如聚类，识别中心节点和检测基序）那样得到很好的研究。我们通过从网络结构中获得新的几何特征来完成这项任务，这些几何特征自然适合于识别界面和边界节点的交互式视觉方法。版权所有©2022作者。由爱思唯尔公司出版我代表浙江大学和浙江大学出版社有限公司这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍营销中的顾客定位是社会生活中的一个重要问题。选民定位是顾客定位的一个典型实例。它已成为一个重要的工具，最新在2004年总统选举，现在是大量使用的民主党以及共和党。营销活动大致可分为两类，即（1）通过市场分析确定目标市场和细分市场，（2）通过提供产品信息和/或产品促销来影响客户行为。当然，营销活动会产生成本，因此必须仔细规划。例如，假设向客户提供因此，识别这些客户或群体已成为一项重要的营销活动。在我们这个时代，营销技术是如此先进，针对个人客户，而不是客户群体或细分市场已成为技术和财务上可行的。除了经典的社会人口统计信息，社交网络已成为一个有趣的数据源，可用于定位客户。通讯作者：西湖大学，杭州，中国.电子邮件地址：chengshenghui@westlake.edu.cn（美国）Cheng）。https://doi.org/10.1016/j.visinf.2022.07.002在更广泛的营销背景下，将客户分类为犹豫不决者和怀疑者是有意义的。例如，它在具有高品牌忠诚度的饱和市场（如烟草市场）中很有用。品牌忠诚度高的吸烟者很难通过营销活动接触到。更有可能被这种摄像头接触到的是在两个或三个品牌之间转换的犹豫不决的吸烟者，以及不经常吸烟或主要吸烟同一品牌香烟的怀疑论者，但也经常从其他品牌。在这里，我们解决的问题，确定两个营销目标，“未定”和“怀疑论者”，从群集的社交网络数据。一个集群网络表现出几个密集连接的组，组之间的边明显较少。由于这两个类，“未定”和“怀疑论者”，是不明确的，这个问题是一个可视化分析方法的主要候选者，它允许我们在视觉上识别网络中的可疑节点，并检查它们是否真的是目标类的成员。在本文的其余部分，我们希望采用更多的技术术语，即“未决定”的界面节点和“怀疑论者”的边界节点或离群值。 我们描述和讨论了一组几何特征，可以有效地计算网络中的节点之间的相似性信息。这些特征自然地适用于识别界面和边界节点的交互式视觉方法。我们还描述了如何从社交网络中的关联信息中获得相似性信息，并验证了我们的方法和2468- 502 X/©2022作者。由爱思唯尔公司出版代表浙江大学和浙江大学出版社。公司这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表视觉信息学期刊主页：www.elsevier.com/locate/visinfS. Cheng，J. Giesen，T. Huang等人视觉信息学6（2022）1112Fig. 1. Twitter极化人群网络是一个典型的政治话题讨论网络，因为它具有两组用户，形成不同的讨论组，一个自由派和一个保守派，几乎没有互动。对于像voter这样的应用程序，在这样的网络中最感兴趣的节点是两个组之间的接口处的节点或仅松散地链接到其中一个组的节点，因为它们更有可能受到政治运动的影响图二、不 同 的视觉探索及其相 应 的效果。Twitter Polarized Crowd网络和Facebook Ego Networks数据集上的随附视觉探索工具。图2显示了我们工作中使用的不同视觉探索及其相应的效果。文件的组织。本文的组织如下：在下一节中，我们将我们的论文定位在相关工作的背景下。在第3.1和3.2节中，我们描述了新几何特征的基本思想，并展示了如何计算它们。我们已经实现了一个交互式的工具，支持基于特征的识别接口和边界节点的结构化社会网络数据。第4节中描述了工具以及实现视图和交互的基本原理。我们在第5节中描述的两个案例研究中应用我们的方法和工具，并在第6节总结了我们的结果。2. 相关工作Pretorius，Pretorius等（2014）给出了多变量网络分析任务的全面概述。抽象地说，任务是一个分析活动的组合，实体和该实体的属性。网络实体是根据Lee et al. （2006）节点、边（或链路）、节点和边的路径以及整个网络。网络属性分为两类：结构或拓扑属性以及与节点和边相关的属性。因此，网络分析任务也可以区分为基于结构或基于属性。在这里，我们只想关注结构特性和基于结构的任务。连接任务是一个子集根据Pretorius等人的研究，基于结构的任务包括聚类任务和桥接任务，旨在寻找网络中的桥梁和连接点。在这里，我们还想添加boundary/outlier-tasks，用于查找仅松散连接到集群的节点。聚类，桥接和边界/离群任务都是de Almeida Valiati等人意义上的分析识别任务。 （2006年）。在本文中，我们将讨论聚类的变体以及某些桥接和离群任务：寻找桥接或连接点（又名切割顶点）是网络分析和图形算法中的经典主题（Cormen et al. ，2009年）。在我们的玩具第4节的例子（见图。节点4是一个连接点，因为它的删除增加了网络的连接组件的数量（从一个到两个）。在更大的节点集群网络中，通常有更多的节点，而不仅仅是一个节点，它们在多个集群中具有这些节点位于集群的接口处，但不再是铰接点，例如参见图1B。1.一、尽管如此，就我们从网络数据中识别未决定的消费者的预期应用而言，我们也希望检测这些节点。与经典工作的另一个不同之处在于，我们不仅在原始信息上解决问题，即，仅仅是网络的邻接矩阵，而且还基于导出的辅助信息，即节点相似性。对于边界节点和离群值也是如此。基于主要信息，边界节点和离群点是具有小度的节点少量的入射边。使用次要信息还允许检测不一定具有小度但与几乎所有其他节点不同在营销环境中，边界节点和离群值主要对应于怀疑论者。在这一点上，一个自然的问题是，为什么一个交互式的视觉方法是必要的识别接口和边界节点，特别是因为我们将引入自动计算的功能，旨在识别这些节点。简单的回答是，就像集群本身的概念一样，接口节点和离群点的概念也是模糊的。因此，全自动的方法并不适合可靠地识别它们这些功能的真正好处是提供了分析人员交互使用的过滤器，用于将所有节点的搜索空间缩小到离群值和接口节点的可能候选者。然后，分析员可以进一步检查为了完整起见，我们还在这里简要概述了一些工具和技术，这些工具和技术是为了支持S. Cheng，J. Giesen，T. Huang等人视觉信息学6（2022）1113基于结构的多变量网络分析任务，尽管它们都不支持我们识别接口和边界节点的特定目标。Nishikawa和Motter（2011）列出了28个有效可计算的网络属性，其中大部分是光谱性质。他们使用这些属性将给定网络的节点嵌入到28维空间中，并通过标准聚类技术以及对随机选择的二维投影进行交互式视觉检查来搜索所得点云中的Cheng等人（2018年，2014年）应用可视化来显示环面网络中的连接活动，但不适用于一般网络。Wong等人 （2006）引入了另一个结构网络的特征，称为图签名。对于每个节点，度为d的签名被定义为向量（n1，. . .，nd），其中n i是距节点距离i处的节点的数量。通过使用广度优先搜索，可以有效地计算图特征向量可以通过多维缩放嵌入到平面中。在其他一些任务中，图形特征有助于找到接合点，但通常不适合识别离群值和接口节点。Wattenberg（2006）介绍了用于分析多变量网络的网络图工具。NodeGraph使用一种简单的基于网格的方法来关注节点属性和连接之间的关系。它的交互方法来自于与电子表格透视表和在线分析处理（OLAP）中的方法的类比。多变量网络数据的多维性质建议使用标准的多维可视化技术，如散点图矩阵（SPLOM）和平行坐标图（PCP）进行分析。GraphDice工具（Bezerianoset al. ，2010年）是适应SPLOM的多元网络数据的分析。在概览图矩阵中，示出了属性的每个成对组合的一个节点-链路图，即，属性的散点图矩阵以及绘制的边。用户可以选择一个图作为主图，然后将其放大。GraphDice工具扩展了ScatterDice工具（Elmqvist et al. ，2008）用于导航和探索多维表，因此继承了其丰富的交互功能。Viau等人 （2010）更进一步调整标准多-多维可视化技术，用于分析多变量网络数据。他们引入了平行散点图矩阵（P-SPLOM）作为散点图矩阵（SPLOM）和平行坐标图（PCP）的统一，以及它们之间的平滑此外，他们建议使用混合网络布局，即，属性驱动的布局与节点的力导向和手动布局的混合，以便为探索用户提供更多的自由度和可定制性 Rendez（Cheng和Mueller，2015; Cheng等人，，2017年）和数据上下文映射（Cheng和Mueller，2016年）也是在彩色化的帮助下可视化多维数据的重要技术（ Cheng et al. ，2019 ）或其他增强（Zhang et al. ，2022），但它们都不适合图形数据。Vehlow等人 2013年，提出了一种简洁的可视化方法。重叠的社区和社区分配在不同细节层次上的模糊性。 类似的目的Wu等人（2015）描述了一种交互式视觉摘要的方法大型网络中的社区。他们将每个社区视觉上编码为一个多边形。未明确指定给任何社区的边界节点将在多边形之间单独绘制。然而，Wu和Vehlow都需要每个节点的先验社区信息，例如来自一些社区检测算法。在我们的工作中，我们不依赖于这样的信息，但引入新的几何节点功能的基础上，当地的邻居节点。然后，我们使用可视化分析方法来探索这些功能，以确定接口和边界节点。3. 初步我们的工作是基于现有的局部邻域特征和相似性矩阵的网络。因此，我们将在本节中对其进行审查。3.1. 局部邻域特征在这里，我们激励和描述的几何特征的建设，以识别接口和边界节点的社交网络，大大提高了ad hoc功能，如节点度- grees。但是请记住，这些功能并不完整，因为它们可以完全自动识别这些节点。它们旨在交互式地用作过滤器，以减少网络中所有节点的搜索空间3.1.1. 输入数据我们考虑一些相似性矩阵作为我们的基本数据结构。相似性矩阵通常从诸如社会人口统计数据、在线活动数据、社交网络数据等的异质数据源导出。本文不涉及从主要数据源计算相似性得分，除了第3.2节，我们从社交网络数据中导出相似性矩阵。导出相似性度量是一项标准的机器学习任务。一种常见的方法是将数据点转化为特征向量，然后将相似度定义为特征向量之间的点积以这种方式计算的相似性矩阵每个相似性得分是点积，也称为Gram矩阵。通常，Gram矩阵不是从特征向量显式计算的，而是从数据的核函数隐式计算的（Schölkopf和Smola，2001）。在后一种情况下，Gram矩阵也称为核矩阵。格拉姆矩阵不仅是对称的，而且是半正定的。由于技术原因，我们还假设相似度矩阵是对称的，并且是半正定的。3.1.2. 从相似性机器学习可以用于从编码在相似性矩阵中的数据导出结构可以从相似性矩阵计算的流行结构是聚类，即，将数据划分成组，使得组内相似性大而组内相似性低。在市场营销中，集群通常被称为市场细分。这里我们感兴趣的是二级结构：是个模糊的概念。虽然将一些数据点分配到一个集群对人类观察者来说是显而易见的，但对其他人来说可能是相当可疑的我们的目标是识别聚类分配不那么明显的数据点在市场营销方面，这些客户对某个细分市场的分配可能不严格，因此是旨在促进不同细分市场的市场活动的主要目标，例如品牌忠诚度不是很高的吸烟者或选举活动中的犹豫不决的选民。许多机器学习技术，例如线性支持向量机（Schölkopf和Smola，2001年）或k-均值聚类，不适用于抽象的相似性矩阵，而是适用于欧几里得点云。为了使这些技术适用于相似性矩阵，后者通常被转换为欧几里得点云，使得转换后的欧几里得距离很好地近似（不）相似性。这也是我们在这里想要追求的方法，即从节点的欧几里得嵌入中导出支持识别聚类社交网络中的接口和边界节点的几何特征S. Cheng，J. Giesen，T. Huang等人视觉信息学6（2022）1114=【日;;得内容.≥∑i，j2∑==--≤··· ≤=∈√√=i、 jσ2xi∈Nj或x j∈ Ni，（）下一页我 II我=我3.1.3. 谱嵌入谱嵌入是一种流行的技术，用于将相似性矩阵嵌入到欧几里得空间中，使得与相似数据点相关联的点的欧几里得距离较小，而对于不同的节点则较大。与其他映射技术相比，如MDS，谱嵌入可以更好地呈现样本的局部流形，从而更好地挖掘数据中的聚类。在我们的谱嵌入中，数据现在被编码在欧几里得点云中，而不是相似性矩阵中。到目前为止，我们已经考虑了编码数据→相似性矩阵，现在我们考虑编码数据→相似性 矩阵→欧几里得 点云给定一个样本矩阵X x1x2. xn，谱嵌入首先构造一个与加权邻接矩阵W相关联的基于邻域的相似图。W中的每个元素wi，j定义如下。中国2wi，j=（一图三. 局部邻域的形状近似于与协方差矩阵QiQi相关联的椭圆体Ei。椭圆体的形状由QiQi的特征值的倒数确定。这里有两个例子：（1）球形邻域，其中μ1<$μ2;（2）细长邻域，其中μ1<$μ2。它们的邻居跨越整个空间Rd。因此，有必要选择k d。椭圆的形状取决于k-最近邻的分布，因此可以作为邻域形状的近似。拟合椭球可以通过局部主分量计算主成分分析（PCA）。让其他的聪明人，{p，. . . ，p}其中N是x，di1ik是i i i， jxi和xj之间的距离，并且σ是自由参数。然后，可以通过以下问题提取很好地表示该图的流形的特征：是pi的k-最近邻的集合，并定义q ij=p ij− p i，其中j = 1，. . . ，k.1 2qij被组织在一个k×n矩阵Qi中，其列是µarg min1Dµ=0（µi−µj）wi，j∑Dµ2，向量qij。这里n是节点数。协方差矩阵QiQ是对称正定的，秩为k，因此其中D是具有第i个对角元素的对角矩阵如di，ijwi ， j。通过对µTµ1进行归一化，这个问题的最优解µ是对应于D−1L的最小非零特征值的归一化特征向量，其中L=D−W是拉普拉斯矩阵（Shi和Malik，2000）。不过，E i=x∈Rk：x<$Qi Qi<$x=1是一个椭圆体。Ei的半主轴由Qi Qi的特征向量给出，它们的长度由相应特征值的倒数给出。如果0<λi1λik是QiQ i的特征值，则该特征向量可以很好地表示流形结构在上图中，我们不能仅通过该特征向量来很好地可视化样本。作为对应于少数小特征值的次优解，一些下一个归一化特征向量也包含有用的划分信息，因此可以用于我们的可视化。在谱嵌入之后，每个x i的点被定义为p i（µi1，. . .，µid）。谱嵌入的计算复杂度为O（n3）.现在可以通过k均值算法或任何其他几何聚类算法对点pi R d进行聚类，或者通过线性支持向量机对点p iRd进行分类，只要我们也具有点的类标签。3.1.4. 使用除聚类之外的几何我们在这里要探索的关键思想是，编码在欧几里得点云中的几何信息应该比线性分类或聚类更有用。我们特别感兴趣的是点云内点的局部分布。我们的工作假设是，在边界或集群之间的点的局部分布不同于集群内部的点。点的局部分布的第一个简单度量是点到其k个最近邻的平均距离。事实证明，这种测量确实提供了有关界面和边界节点的有用信息，但远不是识别这些节点的可靠，完整的特征。作为点的局部分布的稍微更复杂的测量，这比简单的平均距离好得多，我们建议将椭球拟合到每个点的k个最近邻，使得从点到点的向量0< µik：=1/ λik≤· · ·≤μi1：=1/λi1是Ei的半主轴的长度。如果所有的μij都是相同的大小，那么椭球是类球的，而它是扁长的或扁圆的，见图2。3.第三章。3.1.5. 局部邻域特征我们希望使用编码在与点pi相关联的椭圆体Ei中的局部信息，以区分聚类中的点与其边界上的点，或者in between之间clusters集群.椭球的旋转完全由特征值λij，j1，. . .，k或其倒数的平方根μij。因此，我们将特征向量µi 1，. . . ，μik∈ Rk到点P1，并因此到第i个数据点。当然，我们也可以再次使用例如k均值聚类来对特征向量进行聚类，但是最有可能的是，k的值与聚类点pi的k的值不同。由于特征向量与点相关联，而这些点本身又与数据点相关联，因此我们对数据点进行了第二次聚类。在营销背景下，第一聚类基于客户的欧几里德点表示并且对应于市场细分，而第二聚类基于特征向量并且指示客户属于其分配的市场细分的重要的是要记住，特征向量总是可以由其他特征补充，最值得注意的是将项目分配e−µTµ=1S. Cheng，J. Giesen，T. Huang等人视觉信息学6（2022）1115={}∈×| | =⎜⎜⎟⎟⎜⎜⎝⎟⎟⎠⎛⎞A=无菌⎜⎟⎟见图4。这个简单的例子有两个团/集群（分别是节点0、1、2、3和5、6、7、8），一个节点位于两个集群之间的接口上（节点4），另 一个节点松散耦合到第二个集群（节点9）。我们工作的目的是识别接口和松耦合节点。3.2. 网络相似矩阵到目前为止，我们已经开始了我们的讨论与相似性矩阵作为我们的基本数据结构。在这里，我们展示如何获得这样的一个相似性矩阵，仅仅是从网络的结构。为此，设G（V， E）是一个网络，其顶点集记为V，其边集记为E。在社交网络中，边编码两个事件节点之间的一些社交互动。设A是网络的邻接矩阵，即，一个n n-矩阵，如果有V n个节点，如果i， j E，则其条目aij为1，邻接矩阵在结构上是对称的，原则上可以作为相似性矩阵，但在这种情况下，相似性只是一个二元特征，可以判断两个节点是否在社会上相互作用。此外，A是不一定是半正定的，尽管这主要是一个技术细节。相似性矩阵的一个更好的选择是A2，即，邻接矩阵与自身的矩阵乘积。这里的解释是，如果两个节点有更多的共同邻居，即，它们都与大量的节点交互。此外，A2是对称的和半正定的。因此，A2在社会网络分析中是一个很好的相似性度量并不奇怪，在那里它被称为结构等价（Lorrain和White，1971）。当然，还存在从邻接矩阵定义对称、半正定相似性矩阵的其他可能性，例如，基于最短路径，但A2是一个直观的 和方便的选择，特别是在我们的几何工作假设的上下文中，即在边界处或在簇之间的点与在簇内部深处的点不同地分布。这里的点对应于网络中已经被频谱嵌入到欧几里得空间中的节点。让我们用下面的玩具例子来检验这个工作假设。玩具的例子。我们的玩具例子是一个有10个节点的网络：两个不相交的集团，每个集团有4个节点，一个节点连接到两个集团中的所有节点，一个节点连接到一个集团中的两个节点。见图 4我们的玩具网络的邻接矩阵A如下所示：图五. 使用A2的前两个特征向量嵌入玩具网络的节点。因此，相应的相似度矩阵A2被给出为43333111103433311110334331111033343111102333383333211113433321111334332111133354111113334510000222112我们简单地使用A2的前两个特征向量将网络的节点嵌入平面。在添加一些抖动之后的嵌入如图所示。 5如可见于图 5中，界面节点4和边界节点9可以通过到其最近邻的平均距离被清楚地检测到。此外，节点4的相当大的度因此，我们可以很容易地将节点4归类为接口节点，将节点9归类为边界节点。在更复杂的网络中，比如Twitter，极化人群网络，见图。 1、分类不再那么简单，几何特征更加复杂对我们有利4. 可视化分析框架我们已经实现了一个交互式工具，允许探索网络数据中的主要功能（集群，细分市场）和次要功能（邻域形状）。该工具支持我们在下面描述的四个完全链接的视图。4.1. 查看⎛A=0⎜⎝我们工具的四个视图（网络布局，邻域分布概览、特征浏览器和形状浏览器）总结在图中。六、这里我们应该指出，本文的内容并不是提供新的可视化，而是证明了与我们的几何特征相结合的成熟的标准可视化技术可以成为实现我们在集群社交网络中识别接口和边界节点的目标的有效手段⎜⎟⎟⎠0111100000101110000011011000001110100000111101111000001011100000110110000011101100001111010000000110S. Cheng，J. Giesen，T. Huang等人视觉信息学6（2022）1116见图6。在我们的工具中实现的四个视图用于识别接口和边界节点：网络布局，邻域分布概览，特征浏览器和形状浏览器。网络布局视图。已知许多不同的图形布局策略，其允许将网络表示为平面中的节点-链路图，其中节点通常表示为盘并且链路表示为直线或曲线段，参见例如（Battistaet al. ，1998），以获得不同布局策略和目标的概述。我们的工具的网络布局视图具有应力最小化布局，旨在保持节点相似性，即，试图将相似的节点彼此靠近。此外，我们已经试验了力导向布局（Battista et al. ，1998），其旨在避免视觉混乱和边缘交叉，以及主干布局（Nocajet al. ，2014），其被设计用于分离社交网络中的不同社区 事实证明，后两种布局并不能很好地支持边界和界面节点的识别，见图11。 14（a）. 请始终记住，这是唯一不显示特征向量的视图，而是原始网络。邻域分布概览视图。邻域分布概览用于显示高维数据中的聚类和离群值局部邻域特征向量的整体，见3.1节，已经为给定网络的节点计算，可以被认为是一个高维点云。已经提出了许多用于可视化高维点云的方法，其中包括散点图矩阵（Hartigan，1975）、平行坐标（Inselberg和Dimsdale，1990）和多维缩放（MDS）（Borg和Groenen，2005），这些方法在本文中作为整体类的代表这些技术甚至可以结合在一起。由于MDS允许为了快速测量结构，例如，聚类和离群值，我们选择它作为我们的主要视图，用于可视化局部邻域特征。功能资源管理器视图。虽然MDS图在检测聚类和离群值方面效果很好，但它们无法解释特征向量的哪些维度然而，特征资源管理器允许通过将高维点映射到折线的平行坐标来进行这种洞察。因此，我们选择将其添加为可视化局部特征向量的替代视图，即，局部协方差矩阵的特征值。应该注意的是，我们缩放了这个视图中显示的特征值，使得数据集中第i个缩放特征值使得区分不同的聚类更容易。见图7。“网络布局”视图和“形状资源管理器”视图之间针对“网络布局”视图中的两个不同选择的选择交互。显然，网络布局视图中的不同节点组具有不同的局部邻域形状特征，如红星图所示。请注意，左侧选定的节点的平均形状比右侧选定的节点更接近平均形状（蓝色）特征向量并允许更容易的交互，即限制用于过滤的一些特征值的范围，参见第4.2节。缩放特征值的缺点是平行坐标视图不能正确地传达局部邻域的形状。形状资源管理器视图。MDS图和平行坐标图都不允许直接评估局部邻域的形状。为此，我们在工具中添加了一个形状浏览器作为星形图视图（Kandogan，2001），该工具具有局部邻域特征的星形图。星形图立即传达了当地社区的形状，即，拟合的椭圆体，相当好。一眼就能看出椭圆体是否更圆或者是细长的。请记住，拉长的椭球暗示了网络中的界面或边界节点，也见图11。7.第一次会议。我们工具中的星形图主要用于特征向量组，而不是单个特征向量，即，对于选择或聚类，其平均值将显示在星形图中。例如，图6所示的星形图表示网络中所有节点的平均形状。4.2. 相互作用交互用于配置可视化，并允许探索不同的邻域特征以识别界面和边界节点。所实现的交互包括节点的选择、到特征向量的维度的子集上的投影以及通过这些维度和其他特征（如节点度和到k个最近邻居的平均距离）进行过滤。此外，可以对特征向量进行聚类，并且可以从选择中创建彩色组选择. 可以在Network Layout（网络布局）视图或Distri- butionOverview（分布概览）视图中使用矩形范围查询选择网络节点。该选择在其他视图中也变为活动状态（画笔）。 例如图 8我们展示链接S. Cheng，J. Giesen，T. Huang等人视觉信息学6（2022）1117见图8。“分布概览”视图与所有其他视图之间的选择交互。在“分布概览”视图中选择的点将在“网络布局”视图和“要素管理器”视图中亮显。 “形状资源管理器”视图提供所有节点（蓝色）和选定节点（红色）的星形图。分布概览视图中的选择与所有其他视图，并在图。7我们证明了网络布局视图和形状资源管理器视图中的选择。为了支持语义分析，用户还可以通过将鼠标悬停在节点上来读取节点的标签（如果可用）过滤。过滤仅仅意味着限制节点属性的范围。在我们的例子中，属性是节点度、到最近邻居的平均我们的工具在Feature Explorer视图的平行坐标图中启用了对特征向量维度的过滤，其中可以为相应的特征值选择一系列值。投影投影用于从局部特征向量中移除一些维度。这种互动是可能的并且还影响分布概览视图和形状资源管理器视图。它不影响网络布局视图，因为该视图不依赖于本地特征向量。集群。为了获得局部特征向量分布内的聚类结构的第一印象，我们为用户提供了首先自动聚类特征向量的选择。然后相应地对图的节点以及MDS和平行坐标图中的点进行着色，例如参见图1B。11（b）.我们的工具目前支持k-均值聚类（Lloyd，1982），其中k的值可以由用户交互式设置通常，k的小值工作良好，并且特征向量的自动计算的聚类之一已经相当好地对应于界面和边界节点。重要的是要注意，特征向量的聚类不同于经典的谱聚类（Luxburg，2007），其中几何聚类算法直接应用于网络节点的谱嵌入，而不是像我们在这里使用的特征向量这样见图9。Twitter的两极分化人群网络有两个庞大而密集的群体，自由派和保守派，彼此之间几乎没有联系。他们基本上是互相忽略的。这里显示的是应力最小化网络布局。5. 案例研究我们展示了我们的方法来寻找Twitter 的极化人群网络和Facebook的自我网络数据集的接口和为了将网络的谱嵌入到欧氏空间中，空间，我们使用扩散映射的相似性矩阵，而不是直接使用其特征向量。Nadler等人提出了扩散图。 （2008），他证明了嵌入节点的欧几里得距离在网络中有一个很好的解释，如果嵌入维数等于网络中的节点数。他们还证明，即使对于小得多的嵌入维数，这种扩散距离也很好地近似。嵌入维数应结合用于计算邻域特征向量的最近邻的数量k来选择。对 于 其 他 网 络 （ 例 如 我 们 在 上 一 节 所 有 图 中 使 用 的 TwitterBroadcast网络），通常也会给出良好的结果，默认的选择是将嵌入维数选择为k/2。请注意，邻居的数量必须始终大于嵌入维数邻居数目的选择取决于网络的大小。通常，对于较小的网络，此数字应该较小。在我们的案例研究中，10到20之间的任何数字都很有效，因为结果对选择不敏感。尽管如此，在我们的工具中，我们为用户提供了在预定义范围内更改邻居数量以及嵌入维度为了保持工具的交互性，必须预先计算可能选择的结果。5.1. Twitter两极分化的人群Twitter极化人群网络已经由Smith等人介绍和讨论。，2014）在他们对Twitter上政治对话的分析中。这个网络是一个典型的关于分裂政治话题的讨论网络因为它的特点是形成不同讨论组的两组用户，一个自由派和一个保守派，它们几乎不相互作用，并且使用不同的信息资源因此，这个网络被标记为两极分化的人群。这个网络也可以作为一个例子，说明人们倾向于与其他想法大致相同的人在一起因此，我们的相似性矩阵A2（网络的平方邻接矩阵）是一个很好的度量对于网络中的极化，因为集群中的节点S. Cheng，J. Giesen，T. Huang等人视觉信息学6（2022）1118见图10。Twitter极化人群网络中的三种用户类型。从左到右：未决定的用户（接口节点）、怀疑者（边界节点）和坚定者。识别这些类型很难使用自动技术，如聚类特征向量，但需要我们的工具的交互式功能。的相互作用这里是MDS或网络布局视图中的直接选择见图11。 Twitter极化人群网络的聚类分析。根据定义，关于该相似性度量，几乎不与集群外部的节点交互Twitter Polarized Crowd网络有640个节点和7,988个链接，其中节点代表使用标签MY 2K的Twitter用户。这个标签是白宫在2012年推广的。它指的是，如果国会不延长布什时代对年收入25万美元或以下家庭的税率，中产阶级家庭的税收估计将增加2,200美元。如果用户回复、提及或关注另一个用户，则网络中存在链接。从图中可以看出。9，Twitter极化人群网络显然分为两个集群和一些离群值。图的聚类算法，例如马尔可夫聚类（van Dongen，2008），很容易检测到这些簇，但不能检测接口和边界节点。此外，无论是中心性得分，节点度，还是到网络谱嵌入中的k个最近邻的是特别适合用于识别接口和边界节点的特征，参见图1和图2。 11（a）和12（左）。识别接口和边界节点。将3均值聚类应用于邻域特征向量，参见图11。图11（b）揭示了大致对应于网络的应力最小化布局中的接口和边界节点的第三集群。这里应该指出的是，值得注意的是，3均值聚类中的前两个聚类对应于保守派和自由派这聚类是在邻域特征向量上计算的，而不是在网络的谱嵌入上。也就是说，这两个组还可以通过它们的邻域特征向量来区分，该邻域特征向量指示这两个组中的每一个内的不同通信行为。重要的是要注意，从图布局中无法看出邻域结构中的这种差异，S. Cheng，J. Giesen，T. Huang等人视觉信息学6（2022）1119见图12。 突出显示的是保守派和自由派团体内部的节点、两个团体之间界面的节点和一个边界节点。看到有关这些节点的详细信息，请参阅主文本。左边的节点根据它们的介数中心性得分（Brandes，2001）进行着色，右，它们根据特征向量的自动3均值聚类而被着色图9（这同样适用于其他图形布局），或从其他手段，如中心性分数，见图9。 12（左）。自动聚类邻域特征向量已经给出了界面和边界节点位置的良好第一印象，但没有区分它们。 交互式探索揭示了更多细节。通过在邻域分布概览视图中选择特征向量，或通过在网络布局视图中选择节点，可以轻松区分三种用户类型，见图。第十章：未决定（和非政治）用户：这种用户类型的成员既不属于自由派，也不属于保守派。他们的社区结构是拉长的，因为他们有自由和保守的用户作为他们最近的邻居。他们处于保守派和自由派的中间.典型的节点聚类算法不能检测到这种用户类型，并将其成员放入自由或保守的集群，例如在图1中。图10（左）示出了节点聚类算法的典型结果。非政治性用户：这种用户类型的成员表现出与未决定用户相似的邻域结构，因为他们的邻域结构也是细长的。与未决定用户的区别在于，该用户类型的成员的最近邻居来自自由派或保守派集群，但不是来自两者，参见图10（中间）。对应的节点是边界节点。中坚：这种用户类型的成员有一个球形的邻里结构，见图. 10（右）。他们最近的邻居属于同一个集群，自由或保守，作为成员本身。这种用户类型的成员通常也在他们的集群中处于相当中心的位置，见图2。图11（a）（右）为程度中心性分数。对应的节点既不是接口节点，也不是边界节点。仔细看看。 为了提供地面真相，我们查阅了一些的Twitter帐户，目前在网络中（见图。（12）大多数人都有很高的中心性得分。重要的是要注意，应力最小化布局仅提供一些指示，而不是节点分类的基础事实。1. bodiesoflight是一个深奥的Twitter账户，基本上不涉及政治话题，hermanos是一个关注429个其他Twitter账户的用户，这些账户基本上都涉及流行文化。因此，相应的节点分别位于边界或接口处是有意义的2. Politics_PR是R的Twitter账户。Saddler在Nationbuilder.com上声称自己是一个图十三. Facebook的自我网络数据集展示了10名斯坦福大学学生（红色节点）在Facebook上的自我网络。这里再次示出了应力最小化网络布局。政治自由主义的一面尽管如此，它的节点也有许多链接到保守组，这证明了它在界面上的位置。3. DailyCaller是政治新闻网站的Twitter账户，由福克斯新闻的政治新闻记者塔克·卡尔森和副总统切尼的前首席政策顾问尼尔·帕特尔创立。《每日来电》声称每月拥有超过2000万独立读者，并不像其创始人的传记所暗示的那样具有党派色彩。该帐户也有许多链接到自由集团。因此，将此节点分类为接口节点是有意义的4. 来自新泽西州的tironsi75fromNJ在他的推特账户上声称“永远的伯尼”。因此，我们的过滤器及其在网络布局中的位置建议将该节点视为边界节点似乎是不合理的。请注意，数据集是在三年多前收集的，用户5. NHLabor_news是NH LABOR NEWS博客的Twitter帐户，由来自新罕布什尔州多个不同职业的一群“自豪的工会成员”维护因此，它显然是正确地深入自由派集团内部。S. Cheng，J. Giesen，T. Huang等人视觉信息学6（2022）1120图十四岁Facebook Ego Networks的聚类分析。5.2. Facebook Ego Networks如今，消费者与帮助他们满足需求或欲望的不幸的是，按品牌忠诚度聚集的社交网络数据（想想耐克和Adidas）在公共领域不可用在我们的第二个用例中，我们使用了Mcauley和Leskovec（2014）收集的Facebook Ego Net- works数据集，用于验证自动检测社交圈的算法，如运动队或亲戚，在人们的个人社交网络中。这个网络的特点是几个密集连接的组，只是松散耦合，因此也表现出接口和边界节点，我们想确定。请注意，圆与传统的集群不同，因为成员可以是分层的。这样一种政治结构的一个例子是大学朋友圈，来自计算机科学系的朋友，而计算机科学系又包含同一顾问下的朋友用于收集图15. 通过FeatureExplorer视图交互式过滤边界和接口节点。这里只选择了非常细长的邻域，正如平行坐标图中明显的聚类结构所表明的那样6. TheTeaParty_net显然正确地深入保守派群体。从我们对Twit- ter极化人群网络中Twitter账户的检查中，我们得出结论，边界节点通常对应于非政治Twitter账户，而界面节点要么对应于非政治账户，要么对应于具有高中心性得分和来自两个群体（自由派和保守派）的大量追随者的因此，在这个网络中，一些边界节点和接口节点共享相同的语义（用户类型），并且需要其他方法（如中心性得分）来区分。McAuley和Leskovec开发了一个Facebook应用程序，10名参与者（斯坦福大学研究生）用来标记他们自我网络中整个网络有4，039个节点和88，234条链路。识别接口和