全称 IEEE Transactions on Visualization and Computer Graphics (TVCG)，是计算机图形学领域仅次于TOG (ACM Transactions on Graphics) 的顶级期刊

摘要

小世界网络具有典型的低成对的短距路径距离，导致基于距离的布局方法产生毛球图形。因此，最近的研究方法是寻找图像的稀疏表示来放大成对距离的变化。由于在布局上对布局的影响难以进行分析，因此这些方法的组合过滤参数通常必须手动选择，并为每个输入实例分别选择。我们建议使用图不变量来自动确定合适的参数。这使我们能够执行自适应滤波来获得最突出的集群结构。该方法基于实际和合成网络的输入和输出特征之间的经验关系。实验结果表明，该方法能有效地提高强制导向布局方法的鲁棒性。

小世界网络Steven H.Strogatz的文章Exploringcomplexnetworks综述了动力学网络方面的研究。他把网络分成规则网络和复杂网络两种，而复杂网络分为随机网络，小世界网络和自相似网络。小世界网络和自相似网络都介于规则和随机网络之间。
小世界网络的特点：
在网络理论中，小世界网络是一类特殊的复杂网络结构，在这种网络中大部份的节点彼此并不相连，但绝大部份节点之间经过少数几布就可到达。
用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。
哈佛大学社会心理学家米尔格伦的的“六度分隔”理论，他发现，20%的信件最终送到了目标人物手中。而在成功传递的信件中，平均只需要6.5次转发，就能够到达目标。也就是说，在社会网络中，任意两个人之间的“距离”是6。这就是所谓的“六度分隔”理论。
通过上面的论述可以发现社会网络图结构的特点非常具有小世界网络特征

• 引申-什么是社会网络
  在学术上来讲，英文文献中出现的”socialnetwork”应被理解为”社会网络”，而非狭义的社交网络。社交网络的分析单位(unit of analysis)通常是”人”,比如我们会说某人的社交网络比较大广；此外，社交网络这个概念中”network tie “的性质也侧重在指代人与人之间的交互、沟通、互动、情感上面。
  而“社会网络”(social network)既可以指人和人之间的网络，又可以指组织和组织之间的网络，甚至城市和城市之间的关系网络，国家和国家之间的关系网络。这里unitofanalysis不一定是人，而是社会中的实体（entity).此外，社会网络里面networktie可以是指各种类型的关系，比如，可以用来表示两个组织之间有没有相同的组织愿景或服务人群，两个球队之间有没有过交战记录，两个人之间对彼此的评价，或国家之间有没有经济往来等等，不限于“社交”的概念。

社会网络的特征值：
三点组：全局集聚系数基于节点的三点组。一个三点组由三个节点组成，其中可以两边连接(为闭三点组)或三边连接(开三点组)，统称连通三点组。
全局集聚系数C：是闭三点组个数(或三倍三角形个数)除以全部连通三点组个数。

局部集聚系数：对于每个节点i，ni是节点i的邻居节点个数。

平均本地聚集系数：

示例


嵌入性(embeddeness)：两个端点所共同拥有的邻居节点个数
（邻居节点重叠(neighborhood overlap)：）

网络基序(Network motif)
网络的复杂性本质上就是关系的复杂性。但是，研究者通过对真实网络的分析，发现各种关系种类的出现频率是非随机性的。某些特定的关系种类在网络中反复出现，形成网络的典型连接方式
不同类型的网络具有不同的典型连接方式
“网络基序”，认为它们是一个网络的基本构造单元

小世界网络：
高集聚系数

低平均最短路径长度

示例：
每个节点有K>=4最近邻居节点（局部）
可调：改变重连接给定边的概率p
小p：规则网格
大p：经典随机图

小世界的起源：
隐含的社会网络结构并不包含群体关系，单但是如果将群体关系明确之后，会发现小世界网结构的产生正是由于实体的多个群体归属所导致的，如下图：

回到原文
关键点
自动参数选择，自适应边缘滤波，图形化简图，力导向布局，小世界网络，网络可视化

Introduction

社交网络通常高度互联，并展示所谓的“小世界”属性。具有这一特征的网络一般都有一个小的平均成对的最短路径距离和一个高的局部密度。例如，对于脸书的友谊图，这意味着任何人只要与网络中的其他人有少量的中间连接就可以连接起来。
尽管可视化方法如强制导向的布局方法为许多图形提供了高质量的结果，但是它们的能力对于小世界图来说是有限的。最终的图纸通常凌乱,看起来像个毛团,其中固有的图形结构是不可见的。这使得社交网络中最重要的任务之一——工作分析、发现和可视化的内聚亚群以及它们在网络中的相互关系，非常有问题。这些布局方法的主要问题是，它们试图直接将成对的图-理论距离转化为欧氏距离。然而，如果成对的两种形式的变化是很低的，就像发球图一样，结果的布局在欧氏距离上也有较低的变化。

人们提出了各种各样的方法来减少毛球图上的乱画。虽然基于几何图形的可视化技术，比如“边圆面包”，由于在飞机上的节点上的缺失，应用到毛球图纸上，不太可能带来好处，但修改后的布局算法似乎更有希望，因为它们可以补偿图像中的结构性影响。例如，Boitmans等4人提议修改成对的距离，以使相邻的高度节点被进一步分开。这允许放大布局的核心，特别适合于具有极度倾斜程度分布的图形。另一个建议是在人工选择的领域中扭曲布局5。一种不同的一般方法是在图中识别集群，然后使用这些集群来可视化网络6、7。这种方法将可视化问题转移到集群或社区检测方法的选择上。

处理这个问题的另一种方法是图像的简化——阳离子，它的思想是将图中最重要的部分减少到最重要的位置。这个稀疏的子图，也就是所谓的主干，可以用来布局图。简化方法，保持特定的柱状图，如频谱8，cu/连接性9，或者缩短测试路径10，11，倾向于保持小的成对距离，也就是说，产生的后骨仍然是毛球图形。最具前景的简化方法是对内聚亚群进行的最有效的和视觉化的探索，就是根据嵌入的标准7、12、13、14、15来过滤边缘，这是基于边缘周围的局部密度来确定的。按照这种方法，所有的方法都需要输入一个阈值参数，根据这个参数提取主干，然后使用标准的强制方法进行布局。由于参数对最终可视化的非线性影响，找到合适的阈值参数来检索有意义的网络可视化是非常昂贵的。阈值的一个小差异可能已经完全改变了布局。因此，确定最佳的阈值，在布局中最突出的组结构，在试验和错误的基础上是一项非常耗时的任务，特别是对于大型网络来说。

对于这些方法，我们提出了一种预处理技术，它可以自适应地确定组结构在图和布局中最明显的阈值(如我们的实验中所示)。利用聚类系数，我们的技术可以量化每一个可能的阈值值。

我们的贡献是:

• 一种新颖的方法来量化每一个阈值对主干的组结构的影响。
• 一种有效的动态算法，保持在边删除下的聚类系数，在O(α(G)m)总时间内运行，其中m是图中的边数，而α(G)是最小的能够覆盖图G边集合的生成森林
• 对我们的方法在许多真实世界和合成网络中的有效性进行了广泛的评估。

为了评估我们的预处理技术，我们使用了四边的Simmelian脊骨，作为14个具有不同边缘嵌入度指标的实验研究，它非常适合于解开毛球图形，同时保留了组结构。特别是在多中心的小世界网络中，它支持标准的强制导向的布局技术，在最终的图中强调了固有的组结构。

我们首先从下一节的几个方面概述了主干布局方法，并解释了第3部分中自适应滤波的量化度量方法。在第4部分中，我们首先评估它的含义——确定与已知集群的关联，然后研究它对网络布局的影响。第5节总结了我们的结论。

骨干布局方法

图1中显示的主干布局方法的总体工作流程如图1所示。在第一步中，计算了仅依赖于图结构的边嵌入度度量。基于这些边权值，过滤步骤将删除低于给定阈值的所有边。由于连接对于强制导向的布局方法是不可缺少的，但是可能会通过过滤步骤被破坏，下一步是将所有的边缘从基于嵌入度的所有树的结合中重新插入，以确保主干保持连接。请注意，为了避免任意的(非结构的)优先的优势，联合是必要的。

图1所示。主干方法的工作流程由一个流程来扩展，该流程分析了所有可能的阈值参数，并对组结构进行了分析。这允许向用户指出有趣的阈值，以及对该参数的完全自动选择。

结构边缘嵌入的计算可以分为两部分。第一部分计算的是最初的边缘重量，即所谓的四边形重量，它测量了一个边在其邻域内的集成程度，并被定义为

q(u,v) 是包含边(u,v)的四边形的个数

v∈V，N(v)是v的邻居节点

此后，将执行重新附权值。重新调整权值原因是关系(u,v)∈E可能对u和v的重要性是不一样的。关系e可能对u是最重要的，可能是对v无关紧要的,例如因为v可能有其他更重要的关系,因此趋向于摆脱u的束缚.

对于一个边(u，v)，重新加权是根据最初的边权值来对u和v的邻边进行排序的。然后，k被选为Jaccard的系数，u和v的系数是最大化的。这一最大的Jaccard系数可以被看作是在他们的排名上的u和v的协议，并被用作过滤步骤的嵌入度。

为了计算最后一步的强制导向布局，我们使用了在14、18中建议的应力最小化16初始化。这种布局算法发现了节点位置，使得两两匹配的算法与图的理论距离相匹配。为了在算法的每一次迭代中找到这些位置，每个节点都被重新定位为所有其他节点的函数。在下一节中，我们将提出一个仅依赖于图形结构的度量，但是它仍然是最终布局质量的一个适当的指示器。

基于局布局类的自适应过滤

在本节中，我们的目标是对网络中可聚类的结构程度进行量化，这应该可以作为网络集群结构的清晰程度的度量，但不需要执行实际的聚类操作。这个量化允许对手动选择和全自动参数提取提供可视化支持.
不同于在19、20中的现有方法来执行聚类操作，而是度量聚类在网络中的一个经常观察到的参数，即很高的平均聚类系数。聚类系数可以捕捉到一个顶点的邻域之间的关联程度。

在一系列具有不同的稀疏化参数的后骨中，主要的假设是，具有高聚类系数的主干比具有低聚类系数的主干更有可能包含内聚类。如果使用聚类系数的量化是有效的，那么它的最高值应该将我们指向稀疏化参数，由此产生的主干最类似于一个预定义的集群图22，表示底层的组结构。

图2所示。摘要通过对一个具有隐式群结构的综合网络，对聚类系数的聚类系数的有效性进行了评价。最高集群系数(a)表示参数，其中组刚刚开始分解(d)，这也是产生的主干与地面真相集群图最相似的点。(e)过滤删除了越来越多的集群边缘，破坏了组的相对位置。

更准确地说，我们使用phi系数作为一种相似性度量来评估聚类系数的有效性。phi系数可以被理解为两个矩阵实体之间的相关度量，其中第一个矩阵是主干图的邻接矩阵，第二个矩阵是给定的聚类结构的块矩阵。图2给出了整个过程的概况，并展示了一个带有预先划分的合成网络的聚类和phi系数，以及4个有不同的稀疏化阈值的主干图(图2b到2e)。聚类系数可以作为聚类结构的一个指标，并将我们的聚类参数化，这很有可能强调了团体信息。

聚类系数的有效计算

现在，我们研究了如何计算聚类系数对每一个可能的稀疏化参数进行计算的方法。局部聚类系数被定义为一个顶点v的封闭三元组的百分比

λ(v)是顶点v涉及的闭合三元组(三角形)的数目。τ(v)是v中连接的三元组的数量，对于N(v)≤1（邻居节点个数）我们定义其聚类系数为0，这样便可以过滤掉外围度为1的点。

由上述可定义全局聚类系数或者叫做平均聚类系数：

当Sun调查网络统计数据的有效更新模式时，我们还不清楚他们更新方案的聚集系数。它们提供了一个用于更新聚类系数的O()时间复杂度，是网络的平均度。考虑到时间复杂度O()远小于n=|V|,目前尚不清楚如何在聚集系数为n(最坏的情况下)时更新删除下一个边缘的数量可以在O()时间内执行完毕。当删除的边被包含在图中每个顶点的三角形中时，就会给出这样的情况(例如，算法1的例子)。

###　算法1　对全部可能的过滤变量计算聚集系数
输入：Graph G = (V,E) 其中 n = |V|,m = |E|,边权重 w：E -> R(非零实数)，随E变化而变化
数据：Tr[e]:包含边e的三角形集合
d[v]:顶点v的度，λ[v]:顶点v的三角形数目

输出：多级(i=0,1,,k)主干结构的聚集系数Ci

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Tr[e],e∈E                       列出三角形集合（triangle listing algorithm）
for v∈V do C[v]<-λ[v]/τ(v)      计算全部节点的聚集系数
由全部节点的聚集系数得到平均聚集系数 C0
按边的权重划分到不同的桶B1..Bk中
按权重的降序将桶进行排序
for i to k
    foreach e = (u,v)∈Bi do 循环每个桶中的边
        //remove来自三角形中的边e的贡献值
        平均聚集系数 = 平均聚集系数 - u和v的聚集系数影响
        u的邻接点 = 邻接点 - 边e涉及的三角形的顶点
        v的邻接点 = 邻接点 - 边e涉及的三角形的顶点
        顶点u的度-1
        顶点v的度-1
        此时重新根据λ和τ计算顶点uv的聚集系数
        最后再讲uv聚集系数的影响加回平均聚集系数
    
    foreach Tr[e]结合中的 (u,v,w)
        类似上述过程
        完成后就删除Tr()
    Ci<-C

迭代计算

定义 w:E->R 为边缘的权重，反映了结构上的边嵌入，W={w(e)|e∈E}是可能的边权重的集合，Gz，z∈W是 主干结构的结果。
为了计算一个图的聚类系数,我们只需要知道每个顶点的三角形数量,时间复杂度为O(α(G)m),α(G)是图的荫度,或是图g所需的能覆盖所有的边的最小生成森林。实际上,α(G)可以被认为是社交网络的一个小常数。对每个主干结构执行这个计算将花费O(α(G)m)时间，此时可能的主干结构数为O(m)。
算法1描述了如何通过计算原始图的聚类系数来提高效率，并迭代地更新正在删除的每条边的三角统计数据。
当边缘e被删除(第7行)时，所有的三角形(Tr)都会被销毁。因此，正如已经观察到的，对于其中一个三角形中的每个顶点来说，它的本地聚集系数和它对C的贡献值需要更新。

算法1的正确性

根据聚集系数的定义，C平均、对初始图是正确的。它显示在每条边被删除后C平均、的适当的更新。因此，在删除边e=(u,v)之后，就可以显示每个局部聚集系数C[v]被正确地更新了。局部系数只改变了通过e创建了三角形的顶点，而e的所有三角形(Tr[e])也都是u和v的三角形(见算法1下面的数字)。因为它们都被破坏了，所以我们需要通过|Tr[e]|来减少λ[v]和λ[u]。对于e所在的三角形中一个带有权重w的边e，实际上只有一个三角形受到影响(算法1的第17行)，通过从三角形集合中删除另外两条边（(u,w)(v,w)）的每个三角形移除每个三角形t，我们确保这个三角形永远不会再被考虑。因此，C[w]被正确地更新了。u和v的度也被正确地减少了一个单位，这样就可以更新C[u]和C[v]了。

算法1的运行时间

算法1的第一部分的运行时间主要由列出三角形(O(α(G)m))和排序(O(mlogm))组成，在第二个for循环中，每个三角形都处理一次，所需的更新需要常数时间。因为最多有O(α(G)m)个三角形，所以第二个for循环的运行时间是O(α(G)m)。

评估有效性

根据所选的稀疏化参数，原图的散化会产生不同的主干结构。对于每一个这样的结构，我们想要量化它的结构是如何被一组固有的群集所组成的。
模块化通常用于聚类质量评估，但我们不使用它，这是因为它的反直觉行为:即使是对图的完美划分，也只包含有连接的组件，而模块化具有多样性，并且与1的最优值有很大的不同。我们将读者介绍到引述27和28，就这一行为进行更广泛的讨论。
相反，我们测量了主干结构的相似性，其反映了一个完美的划分，由非连接的小结组成，使用对应的邻接矩阵的phi系数。当应用于二进制变量时，phi系数是皮尔逊相关系数的一种变化。弗里曼也称其为Borgatti的参数。
直观的解释是，如果图形与给定的完美划分相似则它的值很大，如果不相似，则很小(接近0)。

由于成对的缩短路径距离通过力导向布局被转换成欧氏距离，我们计算了平均成对的最短路径距离来量化特定参数的图的扩展。在此基础上，利用欧氏空间内的平均邻居距离作为一种局部紧度测度，对阈值参数对最终布局的影响进行了评价。如果聚集结构对于某一特定的主干来说是突出的，那么局部的布局紧凑性应该是很高的。

我们现在更精确地定义phi系数，并给出一个具体的例子。在此之后，我们将解释数据集和图形模型，以最终讨论结果和局限。

phi相关系数

对于主干图G’={V,E’∈E}和顶点集V的划分C={C1,…,Ck} ，令C(v)∈C表示顶点v∈V的聚类。进一步，令
X作为G’的邻接矩阵

Y作为在这个划分上的完美图的邻接矩阵

在这里，循环并不重要，只要它们的存在或不存在被定义为X和Y。由于我们只对一个顶点对的布尔值感兴趣，所以皮尔逊相关系数会降低到phi值。

a，b，c，d代表观测的频率，从2 x 2个偶然事件表中得到

下图3给出了一个图和一个完美的分区之间的相似性的例子。

左边的图G与一个完美的分区(顶点颜色)相似，正如G的邻接矩阵X和完美的划分Y的矩阵结构之间的高度相似性所表明的那样。此时，x=1,y=1是23，x=1,y=0是2，x=0,y=1是2，x=0,y=0是22
φ(X,Y)=套公式=0.84

数据和模型

对于评估，我们使用来自facebook100数据集的网络。这些网络最初来自Facebook，包含了美国100所高等教育机构的学生的社会关系。网络大小不同，从762到41K个顶点，从16K到160M条边。其他的属性，如性别，预期的毕业年，宿舍等，都被作为顶点属性。Traud等30人认为，宿舍对社会关系的形成很重要。因此，我们使用寝室属性作为分区C，从而用phi值进行评估。当主干结构和聚类系数计算考虑到图的所有顶点时，在计算phi值时则会忽略一个缺失宿舍值的顶点。因此，大量缺失的值可能会将phi值作为评估准则。
请注意，尽管经验上许多社交相关的属性与同型属性值相关联，但在Facebook的网络中，没有一个真实的群体结构是可用的。出于这个原因，我们还使用了一种基础的地面真相组结构，使用了14个分区模型(PPM)，并由Lancichinetti等人(LFR)的模型来生成人工网络。

结论和讨论

图2a 剩余的边缘
聚集效应（上）以聚类参数为基础，和真实的情况（phi系数）十分相似（下），沿着稀疏化参数的减小。

首先，我们讨论了聚集系数作为phi系数的代理的有效性。然后通过查看局部布局的紧凑性，来评估这种行为是否也反映在最终的布局中。实验的结果是每个网络的两条曲线，类似于图2a。从左到右，根据嵌入的测量，越来越多的边被移走。这些曲线通常有一个顶点。图4显示了这些apexes的聚类和phi系数值。
由于空间限制，我们无法显示所有facebook100网络的结果。因此，我们选择了11个在图4中标注他们名字的Facebook网络。选择准则是对不同区域的覆盖，反映了网络的各种属性。

图4 聚集系数和phi值的关系
facebook 100网络和PPM500的最大聚集系数，以及所有可能的稀疏化比例。为进一步的分析选择了被标记的网络。

图5 聚集系数和phi值的关系
在不同网络(Facebook100+PPM500)上的散化比和聚类系数。如果phi值很高，那么峰值位置就非常接近。

图5显示了选定网络的聚类和phi系数的曲线。最大值处使用虚线突出显示。对于PPM500网络，聚集系数的峰值非常接近phi值的峰值，在这种情况下，对边缘的进一步过滤只会使集群变得稀疏。如果phi系数很高，例如，对于奥伯恩71、Caltech36、Lehigh96或史密斯60，那么这两个最大值就会接近于彼此。这意味着最大的聚集系数将我们指向过滤参数，其中的密度对于固有的聚类来说是最高的。与其他网络相比，Auburn71略有不同，因为它的phi值比上半年的聚类系数要大。看图4，我们可以看到80%的边都缺少相应顶点的宿舍属性值。当集群系数考虑到网络的所有顶点时，phi系数必须忽略那些缺少值的值，因为它们不为它们所知。对这些缺失值的认识可能会改变曲线的形状。

我们可以看到，对于许多其他的网络，phi系数并没有明显上升，这可能表明，宿舍并不是固有群体的解释变量。然而，聚集系数却有一个明显的峰值，这使我们能够识别出固有的结构的一个重要的全局方面。
我们还试验了许多关于集群系数的加权变量，如Panzarasa和Opsahl所讨论的，但我们没有看到对非加权的准确性的提高。结果具有可比性。我们期望其他的变量，如传递比，网络中三角形的数目除以三元组的数目，也可以工作。
利用Lancichinetti等人的图形模型，我们生成了一个真实社区结构的网络。我们将混合参数m从0.1增加到0.8，这增加了潜在的噪音，并逐渐模糊了群体结构。我们使用这个模型的实际经验是，如果混合参数大于0.6，那么这个组结构就几乎不存在了。图6显示了最大的聚类系数与最大的phi系数，使用地真信息的最大程度相同。这意味着最大的聚类系数是一个很好的代理，可以用来识别在生成的主干中最显著的组结构的稀疏化参数。

图6 phi值代替稀疏化参数
基于LFR模型的真实社区结构和不同噪音水平的图表。选择基于最大聚类系数的稀疏比，给出的结果与使用phi系数的结果几乎相同。

图8 阈值和最大聚集系数的关系
最大群集系数和它的过滤值(四边形Simmelian)为facebook100+PPM500。在三个阈值值之间进行分组，表明在不同的固有社区中存在类似的密度衰减。

过滤值

我们可以观察到一个有趣的观察值，当观察到集群系数最大(图8)的四边Simmelian主干的阈值过滤值时，可以清楚地看到facebook100网络组大约有三个不同的阈值值。这表明，在这些网络中，本地社区结构是相似的，网络中的不同社区之间的密度衰减是一致的(在这些群体中)。找出社区的规模，看看它们是否与这些群体相关联也会很有趣。使用更多的机构信息进行额外的分析，例如，基础设施的属性，可能会揭示更多的解释。

图7
平均最短路径在增长
聚集系数指明了甜蜜点
局部布局更紧凑，组织变得明显
网络通常有一个甜蜜的点，在这个点上，成对的距离(灰色的曲线)增加，但是组(蓝色曲线)是紧凑的，正如聚类系数(红色曲线)所显示的那样。

<< 更多精彩尽在『程序萌部落』>>
<< https://www.cxmoe.com >>

布局质量

对于较小的图形，我们计算了各种增加滤波器参数的力导向布局，并对该布局的局部紧化度进行了评估(图7)，可以观察到局部紧实曲线与聚类系数非常相似。高紧度表示图中的顶点的邻边与布局中的这个顶点非常接近。考虑到布局实际上是在扩展，用单调递增的平均短时间曲线(图7顶部)表示，这意味着基于最优聚类系数参数，在最终的布局中，底层集群变得越来越紧凑。
为了查看我们的自适应过滤对图表的影响，我们使用了我们的方法来处理PPM500(25%)图(图2d)。图7所示的聚类系数曲线表明，如果去掉许多边，该群结构就会被破坏。这表明我们的方法甚至可以应用于非发球图上，使图更清晰地显示出一个已经清晰的组结构。

图9
来自facebook 100数据集的网络图(Rice31，|V|=4k，|E|=9.7w)。左:原始的力导向布局，右:力导向的布局，我们的自动过滤在四边形的Simmelian主结构上。

图10
facebook 100数据集的一个较大的网络(Auburn71，|V|=18k，|E|=100万)。左:原力导向的布局，右:力导向的布局，我们的自动过滤在四边形的Simmelian主结构上。

图11
来自facebook100数据集(Smith60，|V|=3k，|E|=100k。左:原始的力导向布局，右:力导向的布局，我们的自动过滤在四边形的Simmelian主结构上。

绘制

看一看图9、10,11中所产生的主干图，可以看到不同的集群，分别为Caltech36、Rice31、Auburn71和smith 60。强调网络的局部密度和主干布局让我们能够在全局环境中获得关于局部图结构的信息
的图。主干显示:

• 许多强大的社区存在。
• 社区常常是高度重叠的。
• 许多参与者(或顶点)没有很好地集成在强社区内。

根据这些建议，一个图形聚类(或社区检测)方法应该关注于强大的、可能是重叠的社区，以及一组参与者，它们在那里，但不是这些强大社区的一部分。当然，这些参与者可以根据需要分配到他们最接近的社区，例如，如果应用程序需要的话。
在分析的网络中，唯一的例外是收获图，在图中没有可见的局部集群，图9b。图8中Facebook网络的边界位置表明，与其他选择的网络相比，它具有不同的结构属性。这可能是哈佛大学住房政策的结果，该政策仅在第一年就为学生提供宿舍。
注意，具有最大集群系数的主干强调了全局上下文中的组结构。可能需要过滤出更多的边来观察固有组的精细结构。

局限

我们提出的技术在运行时可以很好地扩展到大的图形。然而，我们对集群结构的量化是整个网络的聚合，因此对单个局部细节不敏感。将这种量化以一种更精细的方式进行扩展将是很有趣的，例如，只对交互选择的顶点的子集进行计算。这将允许在图中更详细地分析和可视化特定的兴趣区域。

正如在14个方面所注意到的，四边形的Simmelian主干对于多中心网络特别有用，而对于一个单一中心的网络则更少，例如中心-外围结构。我们的量化指标只能和潜在的边缘嵌入度一样有效，因此当应用于单一核心网络时，它也有类似的缺点。

结论

我们提出了聚类系数的使用方法，在聚类结构的基础上，定量地分析了在主链结构上对主链结构的影响。使用真实世界和合成网络进行的实验评估，证实了其在四边形Simmelian脊骨上的有效性，结果也可能扩展到其他密度的基础上。此外，我们还展示了如何有效地计算每一个可能的阈值参数的聚类系数。
这在探索和可视化大型网络时尤其有用，因为在大量的网络空间中，由于时间密集型的布局重新计算，在一个错误的基础上选择适当的sparsi虚拟化级别是非常麻烦的。
虽然图表的布局度量和视觉检查都表明集群确实是明显的，但是在2行中详细的用户研究必须显示出这种视觉效果对于特定任务的重要性，例如类簇的选择。