【www.zhangdahai.com--其他范文】
宗传玉，宪 超，夏秀峰
（沈阳航空航天大学 计算机学院，沈阳 110136）
随着数据源数量的增长与数据库技术的发展，数据可用性的研究得到了广泛的关注。由于大部分用户缺乏必要的专业知识，提交的查询请求可能不能表达用户真正的查询意图，无法从数据库中得到想要的查询结果；
但是，这些用户可以通过提供一些实例来表达自己的查询意图。因此，为了提高数据的可用性，数据库系统应该提供一种功能，即根据用户提供的实例为用户推荐合适的查询参数，使用户能够根据推荐的查询参数获得所需的查询结果，从而提高数据的可用性。
图数据G=（V，E）能够用于表示数据和数据间的关系，其中V用来保存表示实体的节点，E用来保存表示实体间关系的边。随着社交网络、合作网络、信息网络、通信网络等应用的迅速发展，有效地对图数据进行管理和分析已经成为众多学者们研究的热点。基于图结构的聚类（图结构聚类）得到了广泛的研究。执行图结构聚类后，图中联系紧密的节点被聚类到相同的簇中，联系分散的节点被聚类到不同的簇中，剩余一些没有被聚类到簇中的节点又被划分为桥节点与离群节点。
pSCAN（pruned Structural Clustering Algorithm for Networks）算法［1］是一个快速且准确的图结构聚类算法，该算法根据两个聚类参数生成聚类结果，一个是密度约束μ，另一个是相似度阈值ε。给定一个社交网络图G=（V，E），x和y为图G中的两个节点，N［x］用来表示节点x的邻居集合，集合中包含节点x本身。σ（x，y）用于表示两个节点x和y之间的结构相似度，这个值由x和y的各自邻居数量与公共邻居数量决定，结构相似度越大，说明两个节点的关系越密切，当结构相似度不小于ε时，x和y两个节点互为ε-邻居。
pSCAN 算法的聚类过程如下：计算每个节点的ε-邻居数量，如果某个节点x的ε-邻居数量不少于密度约束μ，x是一个核心节点。核心节点x将形成一个簇C，随后C将迭代地吸收该簇中的核心节点的ε-邻居中的核心节点，C将以这种机制持续扩大，直到没有新的核心节点加入为止。等到所有的核心节点都被聚类到不同的簇中后，最后将每一个簇中核心节点的ε-邻居中的非核心节点聚类到相应的簇中，直到处理完所有的节点。此外，对于不属于任何一个簇的节点x，如果x的邻居属于两个或以上的簇，那么x是一个桥节点；
否则，x是一个离群节点。
如图1 所示，当参数ε=0.61、µ=4 时，可以得到一个簇C1=｛v1，v2，v3，v4，v5，v6，v7，v8，v9｝。因为v10、v11、v12不属于任何一个簇，并且每个节点的邻居不属于两个或两个以上的簇，所以v10、v11、v12三个节点是离群节点。
图1 图结构聚类实例Fig.1 Example of structural graph clustering
由于大部分用户缺乏必要的专业知识，无法为pSCAN算法提供合适的参数，随意设置参数很难得到想要的结果。然而，对于这些用户来说，虽然不能提供合适的聚类参数，但是根据一些背景知识能够提供一些实例簇，比如某一组技术人员的研究方向相同且属于同一个部门，他们应该属于同一个簇。对于数据库系统来说，提供根据用户提供的实例为用户推荐合适的查询参数的功能是十分重要并且有用的［2］。目前，基于用户实例来探究用户查询意图已经成为数据库领域的一个研究热点。基于密度的图结构聚类算法主要有SCAN（Structural Clustering Algorithm for Networks）算 法［3］、SCAN++（Structural Clustering Algorithm for Networks++）算法［4］以及pSCAN 算法等，pSCAN 算法是目前效率最高的图结构聚类算法，因此，本文以pSCAN 算法作为研究基础。
如图1 所示，假设用户不能提供合理的聚类参数，但是根据一些已有的背景知识，用户知道，｛v1，v2，v3，v4，v5，v6，v7，v8，v9｝应该属于同一个簇，那么如何根据这个实例簇为用户返回合理的聚类参数是本文要研究的主要内容。为了解决这类问题，本文提出了一种实例簇驱动的图结构聚类参数计算算法，使得系统返回的聚类参数能够将用户提供的实例簇节点聚类在同一个簇中，且不包含其他非实例簇的节点。用户只需要向系统提交一些实例簇来表达自己的聚类需求，就可以获得在该实例簇需求下的有效聚类参数。用户再根据有效聚类参数执行pSCAN 算法，便可以得到想要的聚类结果，这样既可以帮助用户更好地理解图结构聚类操作，又可以有效提高图数据库的可用性。
对于结构庞大的图结构数据来说，得到有效的聚类参数来使得用户提供的实例簇节点能够聚类在同一个簇中的代价十分昂贵。因此，实例簇驱动的图结构聚类参数计算算法的主要挑战是如何基于实例簇快速且准确地得到满足实例簇需求的聚类参数。此外，满足实例簇需求的有效聚类参数往往不止一个，如何得到满足实例簇需求的最优聚类参数也是本文研究的一个重点。
综上，本文的主要工作如下：
1）构建了一个实例簇驱动的图结构聚类参数计算算法框架，该框架包含获取子图、划分节点和计算并验证聚类参数3 个模块。
2）为了使实例簇中的节点能够形成一个簇，提出了两个有效的实例簇驱动的图结构聚类参数计算算法，为用户返回满足实例簇需求的最优聚类参数。
3）在3 个真实的社交网络数据集上进行了大量的实验，结果表明提出的算法能够基于实例簇有效地返回满足用户需求的最优聚类参数。
1.1 图结构聚类
很多学者对于图结构聚类提出了不同的算法。Xu 等［3］提出了SCAN 算法，它是一种根据结构相似度来将图中节点进行聚类的算法。Chang 等［1］提出了一种能够减少结构相似度计算次数的新方法pSCAN 算法，它是一种基于SCAN 算法的图结构聚类算法，性能要高于SCAN 算法。由于pSCAN 算法计算量巨大，学者们不断在此基础上进行剪枝以减少计算量：Ruan 等［5］研究了具有 Jaccard 相似性和余弦相似性的边缘插入和删除的图结构聚类算法；
Shiokawa 等［6］研究的DSCAN（Distributed Structural Clustering Algorithm for Networks）是一种采用边缘修剪技术来减少分布式算法的通信和计算开销的图结构聚类算法；
Yu 等［7］研究了基于动态规划的稳定结构聚类算法，能够在不确定图中聚类；
Tseng等［8］提出了一种基于并行索引的近似SCAN 算法，并行索引查询比GS*-Index（Graph Structure Index）更快；
Liang 等［9］研究 的 probSCAN（Prob Structural Clustering Algorithm for Networks）是一种基于分解的算法，它包含一个具有成本效益的索引结构，以加快图中结构相似度计算；
Zong 等［10］针对动态变化的参数研究了两种有效的增量聚类算法，避免SCAN 算法的重复执行；
Seo 等［11］研究了用于图结构聚类的高效算法，能够为非常大的图提供可扩展性能；
Shiokawa等［4］研究的SCAN++算法是一种引入直接两跳可达节点的图聚类算法。
1.2 实例驱动的查询构造方法
许多学者提出了不同的基于实例进行查询的方法：Shen等［2］提出了一种通过实例进行查询的方法，以用户查询作为用户兴趣数据的实例并加以实现；
Fariha 等［12］提出了一种称为SQuID（semantic Similarity-aware Query Intent Discovery）的算法，通过用户提供的几个例子来推断用户的意图，从而完成用户的查询，这种查询可以令没有专业知识的用户进行专业查询；
Khwildi 等［13］提出了一种针对高动态范围（High-Dynamic Range，HDR）图像的高效检索系统；
Sarwar 等［14］提出了一种基于语义角色标签的方法来识别事件跨度的无监督查询算法；
Adamou 等［15］研究了针对未知数据集查询时基于示例的星形查询，可以通过用户对其他数据的查询推荐未知数据集的查询；
Rezig 等［16］研究了一个通过用户提供的示例记录的方法DICE（Data dIsCovery by Example），合成查询捕获用户意图，返回更多满足用户意图的记录；
Qin 等［17］研究了一个数据探测系统，可以找到用户想要的元组，并在交互中对所需元组进行偏好排序；
Jiang 等［18］提出了一种利用样例影片对期望的拍摄方法进行控制的运动控制器；
Thakkar 等［19］提出的EGS（Example-Guided Synthesis）通过用户提供的实例的潜在结构生成关系查询；
Fariha 等［20］提出的SuDocu（Summarizing Documents）是一个由用户提供示例摘要反映用户摘要意图的文档摘要系统。本文的算法也是基于QBE（Query By Example）思想，通过少量的实例簇进行计算，得到满足用户实例簇的最优聚类参数。
在本章中，首先描述一些重要的符号和定义；
然后，形式化定义了实例簇驱动的图结构聚类参数计算。
2.1 相关定义
在说明实例簇驱动的图结构聚类参数计算问题之前，首先介绍一些与图结构聚类参数计算有关的重要概念，例如结构相似度、ε-邻居、核心节点、结构可达等。
定义1结构相似度。给定图G=（V，E）中的两个节点u和v，则u和v的结构相似度定义为σ（u，v）：
定义2ε-邻居。给定一个相似度阈值ε、一个节点v以及它的一个邻居u，如果v与u的结构相似度大于或等于相似度阈值ε，那么u和v互称为对方的ε-邻居，v的ε-邻居集合如式（2）所示：
定义3核心节点。给定相似度阈值ε，密度约束μ和一个节点v，如果v的ε-邻居集合中节点个数大于μ，v被称为核心节点；
否则，v被称为非核心节点。
定义4结构可达。给定两个节点u和v，相似度阈值ε和密度约束μ，如果存在一个节点序列x1，x2，…，xn(n≥2)，并且u=x1，v=xn，且满足以下条件：
则称节点v能够从u结构可达。
2.2 问题描述
通过分析pSCAN 算法的聚类原理可知，满足用户提交的实例簇需求的聚类参数可能有多个。如图1 所示，假设用户提交的实例簇为C1，满足该实例簇的聚类参数有多个，聚类参数为μ1=4、ε1=0.58 时，得到的聚类结果为R1=｛v1，v2，v3，v4，v5，v6，v7，v8，v9｝；
当聚类参数为μ2=3、ε2=0.5 时，得到的聚类结果为R2=｛v1，v2，v3，v4，v5，v6，v7，v9，v10，v11，v12｝。通过比较可以发现，为用户返回第一组聚类参数，用户执行该参数后得到的聚类结果更能满足用户的实例簇需求。此外，参数值越大，聚类条件也就越严格，返回的冗余节点和冗余簇也就越少。因此，为了提高聚类参数质量，本文将能够使得实例簇中节点成为一个簇的参数的最大值（即上限）称为最优聚类参数。而实例簇驱动的图结构聚类参数计算算法是指根据用户提交的实例簇，为用户返回满足实例簇需求的最优聚类参数。综上，本文的问题定义如下：
问题定义：给定一个图数据集D，一个实例簇C=｛v1，v2，…，vn｝，实例簇驱动的图结构聚类参数计算是指如何快速找到能够使得C中节点成为一个簇的最优聚类参数μopt，εopt，当用户在D上基于最优参数执行pSCAN 算法时能够得到一个聚类结果R，且R应满足如下条件：
在本章中，首先，介绍了实例簇驱动的图结构聚类参数计算算法框架；
然后，讨论了聚类参数ε和μ对pSCAN 结果的影响。
3.1 算法框架
通过分析pSCAN 算法可知，pSCAN 算法的聚类结果中的每一个簇只可能包含两类节点：核心节点和非核心节点。此外，密度约束μ是一个有限的整数。实例簇驱动的图结构聚类参数计算算法的思路是首先根据实例簇获得密度约束μ的可行区间；
然后基于每一个可用的密度约束μ，计算满足实例簇需求的相似度阈值参数ε的最大值（最优值）并对获得的参数进行验证；
最后返回满足实例簇需求的最优聚类参数。本文构建了一个实例簇驱动的图结构聚类参数计算算法框架，如图2 所示。该框架包括获取子图、划分节点和计算并验证聚类参数3 个模块。
图2 实例簇驱动的图结构参数计算算法框架Fig.2 Framework of instance-cluster-driven structural graph parameter calculation algorithm
1）获取子图：在该模块中，根据给定的实例簇C从图数据集D获取与C相关的子图H，H需满足如下条件：
①子图H包含C中所有节点及C中节点的邻居。
②子图H包含D中至少一个节点属于C的边。
2）划分节点：首先根据子图H计算出密度约束μ的可行区间。然后根据区间中每一个可行μ计算出对应的最大相似度阈值ε。因为一个簇是由互相结构可达的核心节点和从这些核心节点结构可达的非核心节点构成的，为了得到每个μ对应的最优的ε，首先根据μ对实例簇中的节点进行划分并根据划分后的节点计算ε，并不断地优化ε值来优化对实例簇中节点的划分，直到满足以下条件：
①实例簇C中的所有核心节点互相结构可达。
②实例簇C中所有的非核心节点都至少与一个核心节点结构可达。
3）计算并验证聚类参数：通过划分核心节点与非核心节点来获得每一个密度约束μ下对应的最优相似度阈值ε。由于划分节点可以获得满足实例簇的最大结构相似度，并且在相同密度约束μ下，相似度阈值ε越大，聚类效果越好。因此，认为满足当前节点划分的最大ε时就是当前μ所对应的最优ε。然后在H上验证当前得到的参数μi和εi得到Hi。如果满足实例簇需求，则计算终止，否则计算并验证下一个可用μi+1所对应的最优εi+1，直到满足实例簇需求为止。
3.2 不同参数对查询结果的影响
不同聚类参数会产生不同的聚类结果。在相同密度约束下，相似度阈值越大，聚类条件越严格，聚类结果越不可能包含冗余节点和冗余簇。如图3（a）所示，当聚类参数为μ=4、ε=0.61 时，得到聚类结果={v1，v2，v3，v4，v5，v6，v7，v8，v9}；
当聚类参数μ=4 不变，参数ε增大为ε=0.61时，得到聚类结果=｛v1，v2，v3，v4，v5，v6，v7，v9｝，如图3（b）所示。类似地，在相同相似度阈值下，密度约束越大，聚类条件越严格，如图3（c）和图3（d）所示，当聚类参数为μ=5、ε=0.58 时，得到聚类结果=｛v1，v2，v3，v4，v5，v6，v7，v8，v9｝；
当聚类参数ε=0.58 不变，参数μ减小为μ=5时，得到聚类结果=｛v1，v2，v3，v4，v5｝。上述分析进一步说明了参数值越大，聚类条件越严格，得到的聚类参数越能满足用户实例簇的需求，执行最优聚类参数后得到的冗余簇就越少。
图3 不同参数下的聚类结果Fig.3 Clustering results under different parameters
4.1 定理及证明
综上所述，首先需要计算的是密度约束μ的可行区间，为了获得更高的效率，在这一步应尽可能缩小这个可行区间，一个重要的定理如下：
定理1如果一个节点x∈V，d[x]<μ，那么x一定不是核心节点。
证明x是一个核心节点需要满足条件，|Nε(x) |≥μ，并且|Nε(x) |≤|N[x] |=d[x]，即d[x]≥μ，如果不满足，则x不可能是一个核心节点。
如图3（a）所示，d[v7]= |{v2，v6，v7} |=3 <4=μ，所以v7不可能是一个核心节点。
引理1如果实例簇C中的一个节点x是非核心节点，那么x的邻居中至少有一个节点y是核心节点。
证明 pSCAN 聚类算法执行后，核心节点会生成一个簇C，C中的核心节点迭代地吸收核心节点的ε-邻居节点，如果有一个非核心节点x的邻居中没有核心节点，那么x将无法被聚类到簇中。也就是说非核心节点的邻居中必然有一个是核心节点，该非核心节点才有可能出现在聚类结果中。
如图3（a）所示，如果v7被划分为非核心节点，那么v2和v6之中必定有一个是核心节点，这样生成的簇才能够包含v7。
在满足引理1 后，可以保证实例簇C中所有节点被聚类到簇中，但是无法保证这些节点被聚类到同一个簇中，因为可能会出现核心节点与非核心节点结构不可达的情况，或者会出现核心节点之间结构不可达的情况，会导致这些节点被聚类到两个或者两个以上的簇中。此时得到的ε值过大，可以再继续减小ε的值，使这些节点被聚类到同一个簇中，一个重要的引理如下：
引理2如果实例簇C中的每个非核心节点都有一个核心节点的ε-邻居，且C中的每个核心节点都相互结构可达，那么C中的节点就能构成一个簇。
此外，本文引入了以下定义：
定义5核心节点最大相似度阈值。给定一个节点v，密度约束μ，节点v的核心节点最大相似度阈值返回在当前密度约束μ下，节点v能成为核心节点时相似度阈值ε的最大取值，形式化定义为Epμ(v)：
其中：maxμ表示向量中元素从大到小排列的第μ个值。如果当前ε取值小于等于Epμ(v)时，v是一个核心节点；
否则，v是一个非核心节点。
如图4 所示，Ep4(v6)=σ(v1，v6)=0.73，当ε≤0.73 时，v6是核心节点，当ε>0.73 时，v6是非核心节点。
4.2 实例簇驱动的图结构聚类参数计算的基本算法
根据上述定理和引理，将实例簇中的所有节点划分为核心节点和非核心节点，针对可行区间内的每一个μ计算得到一个对应的最优参数ε。算法1 的伪代码如下：
算法1 实例簇驱动的图结构聚类参数计算的基本算法（PART）。
首先通过输入图数据集D、实例簇Cs（第1）行）获取Cs相关的子图结构。根据子图结构，可以得到密度约束μ的可行区间（第2）行），接下来对可能区间内的最大μ进行计算（第3）行）。根据定理1，将Cs中的部分节点划分为非核心节点（第4）～8）行）。对Cs中未确定的节点，计算它们的核心节点最大相似度阈值（第9）～10）行）。在未确定的节点中，找到一个核心节点最大相似度阈值最小的节点作为非核心节点，并在该非核心节点的邻居中找到一个核心节点最大相似度阈值最大的节点作为核心节点，如果当前ε值大于该核心节点的最大相似度阈值，则更新ε为该核心节点的最大相似度阈值（第11）～19）行），然后将所有核心节点最大相似度阈值大于当前ε的未确定节点划分为核心节点（第20）～23）行），接下来，重复上述步骤，划分非核心节点和核心节点并更新ε，直到所有节点均被划分为核心节点或非核心节点（第11）～24）行）。接下来检验当前ε，如果成功聚类为同一个簇，并且簇中不包含Cs外的节点，则停止计算，输出当前μ和ε（第25）～27）行）；
如果不能成功聚类为同一个簇，或者检验时可以得到同一个簇，但簇中包含Cs以外的其他节点，或者计算得到的ε值为0，则认为当前μ值时无解，更新μ=μ-1（第28）～29）行），再重新进行计算，直到能够成功聚类为同一个簇为止（第3）～30）行）。最后输出μopt，εopt（第31）行）。
如图4 所示：首先找到μ可行区间［2，5］，对于最大值μ=5，首先将C中节点v5，v7，v8，v9划分为非核心节点，然后计算v1，v2，v3，v4，v5，v6的核心节点最大相似度阈值，选择最大核心节点最大相似度阈值的节点作为核心节点，将v1，v3，v4，v6划为核心节点，此时得到ε=0.58；
再选择最小核心节点最大相似度阈值的节点作为非核心节点，将v2划分为非核心节点，此时C中所有节点均被划分为核心点或非核心点；
检验当前参数下实例簇C中所有节点被聚到同一簇中，且不包含任何簇外节点。最后返回最优参数为μopt=5，εopt=0.58。
图4 算法1的实例Fig.4 Example of Algorithm 1
4.3 实例簇驱动的图结构聚类参数计算的改进算法
由于算法1 计算所需的时间较长，对算法1 进行了改进和优化，在保证精度的前提下，提高了计算效率。
根据以下引理能够提高判断一个节点是否是核心节点的效率。
引理3如果一个节点已被计算的ε-邻居数量大于等于μ时，这个节点一定是核心节点。
如图4 所示，根据引理1，假设当前μ=4，当计算出｛v1，v2，v3，v4｝为v1的ε-邻居后，无论v5，v6与v1之间的结构相似度为多少，v1都会是一个核心节点，因此，不需要再计算v5，v6与v1之间的结构相似度，可以节省大量的计算。
算法1 中会出现核心节点与非核心节点结构不可达的情况，因此引入以下定义来提高构建核心节点与非核心节点结构可达路径的效率。
定义6最大结构可达相似度阈值。给定两个节点u和v，密度约束μ，u和v的最大结构可达相似度阈值为u的核心节点最大相似度阈值和它与邻居v的结构相似度中的较小值，将其形式化定义为Mepμ（u，v）：
当ε≤Mepμ(u，v)时，u是一个核心节点，并且v是u的ε-邻居，u可以将v聚类到自己所在的簇中。当ε>Mepμ(u，v)时，要么u是一个非核心节点，要么v不是u的ε-邻居，在这两种情况下，u都不可以将v聚类到自己所在的簇中。
如图4（b）所示，Mep4(v3，v8)=min｛0.61，0.58｝=0.58：当ε≤0.58 时，v3可以将v8聚类到自己所在簇中；
当ε>0.58 时，v3不能将v8聚类到自己所在簇中；
当ε=0.61 时，v8成为离群节点。
为了提高检验节点之间构建结构可达路径的效率，引入以下引理，只需要判断核心节点之间结构可达就可以满足引理2 的需求。
引理4对于聚类结果C中的每个核心节点，如果核心节点之间相互结构可达，C中节点就能够构成一个簇。
如图1 所示，聚类结果中的簇C1中，核心节点v1，v2，v3，v4，v5，v6都是相互结构可达的。
依据引理3 和定义6 可以减少节点之间结构相似度的计算，依据引理4 可以减少节点之间构建结构可达路径的检验。改进后算法的伪代码如算法2 所示。
算法2 实例簇驱动的图结构聚类参数计算的改进算法（ImPART）。
首先通过输入图结构D、实例簇Cs（第1）行）提取Cs及其周围节点的子图结构。根据子图结构，可以得到密度约束μ的可能区间（第2）行），接下来对可能区间内的最大μ进行计算（第3）行）。首先划分得到一部分非核心节点（第4）～6）行）。然后根据引理2，对每一个非核心节点，计算每一个邻居的最大结构可达相似度阈值，将最大结构可达相似度阈值最大值邻居划分为核心节点（第7）～9）行）。如果当前ε大于该核心节点的最大结构可达相似度阈值，则更新ε为该核心节点的最大结构可达相似度阈值（第10）～11）行）。接下来根据引理1 计算剩余未确定节点的核心节点最大相似度阈值（第14）～21）行），类似PART 算法划分核心节点和非核心节点并更新ε，直到所有节点均被划分为核心节点或非核心节点（第22）～33）行），接下来检验当前ε能否成功聚类为同一个簇（第25）～30）行），如果能够成功聚类，则输出当前μ和ε；
如果核心节点之间不能够相互结构可达或者核心节点和簇外节点结构可达或者得到的ε为0，则降低μ，对更新后的μ重新计算ε（第3）～30）行）。最后输出最优聚类参数μopt，εopt（第31）行）或者空集。
在本章中，通过大量实验来评估实例簇驱动的图结构聚类参数计算算法PART 和ImPART 的性能。
5.1 数据集和实验设置
数据集（http：//snap.stanford.edu/data/）的说明如下：
ego-Facebook：ego-Facebook 是一个来自Facebook 的用户社交关系网络数据。该数据集包含4 039 个节点和88 234 条边，为相对稠密的图。
p2p-Gnutella31：p2p-Gnutella31 是一个来自Gnutella 的从2002 年8 月开始收集的对等文件共享网络数据。该数据集包含62 586 个节点和147 892 条边，为稀疏图。
Slashdot0902：Slashdot0902 是一个来自Slashdot 的用户社交关系网络数据。该数据集包含82 166 个节点和948 464条边，为稀疏图。
由于目前没有基于实例簇对图结构聚类参数进行计算的相关算法，且现有的基于实例对查询参数进行计算的算法都无法解决本文研究的问题。因此，在上述稠密图和稀疏图中只对本文所提出的PART 和ImPART 两个算法的性能进行了测试。为每一个数据集都设计了四组实例簇，四组实例簇的大小均在100～1 000 内（同一量级），且相差不大。其中，实例簇C1～C4 属于ego-Facebook 数据集，实例簇C5～C8 属于p2p-Gnutella31 数据集，实例簇C9～C12 属于Slashdot0902 数据集，每个实例簇中的节点个数如表1 所示。
表1 实验中使用的实例簇Tab.1 Instance clusters used in experiments
5.2 算法性能
首先，评估了在不同数据集下，针对不同实例簇，算法PART 和ImPART 的运行时间。正如期望的那样，如图5 所示，对于同一实例簇，ImPART 的运行时间明显低于PART 的运行时间，运行时间缩短了20%以上，主要是因为ImPART基于引理3 和引理4 剪枝掉了很多冗余计算，提高了计算效率。对于同一数据集的不同实例簇来说，虽然节点个数不同，但ImPART 的运行时间却相差不大，如图5（b）中的C5～C8，主要原因就是ImPART 算法的运行时间主要受到通过实例簇获取的相关子图的结构的影响，而C5～C8 获得的相关子图的结构相差不大，因此运行时间相差不大，C10 和C12的运行时间相差不大也是类似的原因。此外，对于不同数据集上实例簇节点个数相近的实例簇来说，算法的执行时间相差还是比较大的，如图5（b）和5（c）所示，实例簇C8 和C11 中的节点个数相近，但是为C11 计算最优聚类参数的时间明显高于为C8 计算最优聚类参数的时间，主要原因是，这两个实例簇所在的数据集不同，导致获取的实例簇相关的子图结构差别比较大，子图结构越复杂，需要访问的边数越多，需要计算的结构相似度也会更多，从而导致PART 和ImPART 的运行时间就越长。
图5 不同实例簇下PART和ImPART的运行时间Fig.5 Running times of PART and ImPART under different instance clusters
其次，评估了同一实例簇下数据集节点数对PART 和ImPART 运行时间的影响，选择C4、C7、C10 实例簇进行测试。实验结果如图6 所示，当数据集节点数增大时，PART 和ImPART 的运行时间都在增加，但增加的不明显。因为随着数据集中节点数的增加，在数据集中获取与实例簇相关的子图的时间就会增加，子图的结构也会变得更复杂，而算法的运行时间会随着图结构的复杂程度增大而增加。增加不明显主要原因是数据集中增多的节点没有对获取的实例簇相关的子图产生大的影响。
图6 数据集大小不同时PART和ImPART的运行时间Fig.6 Running times of PART and ImPART under different data sizes
再次，评估了同一实例簇下不同量级数据集节点数对ImPART 运行时间的影响。设置数据集的节点数为5 000 和20 000，由于ego-Facebook 数据集的大小只有4 000，无法选择不同量级数据集大小，所以只选择p2p-Gnutella31 数据集和Slashdot0902 数据集进行测试。实验结果如图7 所示，当数据集节点数明显增加时，ImPART 的运行时间也在增加，但增加得不明显。因为随着数据集中节点数的增加，在数据集中获取相关子图的时间会增加，子图的复杂程度会增加，因此运行时间会增加。增加的时间不明显的原因是数据集中需要计算的结构相似度的次数没有明显增加，增加的节点对实例簇相关的子图没有产生较大影响。此外，C5 和C6 运行时间几乎相同，这主要是因为C5 和C6 获得的相关子图的结构相差不大。
图7 不同量级数据集上ImPART的运行时间Fig.7 Running time of ImPART on datasets with different magnitudes
然后，为每个数据集设计了3 个节点数属于不同量级的实例簇来评估算法PART 和ImPART 的性能。3 个实例簇的节点数选取区间分别为［10，100）、［100，1 000）、［1 000，5 000］。其中，实例簇C21～C23 属于ego-Facebook 数据集，实例簇C24～C26 属于p2p-Gnutella31 数据集，实例簇C27～C29属于Slashdot0902 数据集，实例簇大小如表2 所示。如图8 所示，对于同一个数据集的不同量级的实例簇来说，两个算法的执行时间会随着实例簇节点个数量级的增大而明显地增大。实例簇越大，ImPART 的效率提升越明显，如图8（a）所示，这是因为算法的运行时间主要集中在结构相似度的计算和检验能否成簇的计算，而ImPART可以减少大量冗余计算。
表2 不同量级的实例簇Tab.2 Instance clusters with different magnitudes
图8 不同量级实例簇下PART和ImPART的执行时间Fig.8 Running times of PART and ImPART under instance clusters with different magnitudes
最后，本文比较了不同实例簇所对应的最优聚类参数，不同实例簇对应的最优密度约束和最优结构相似度阈值分别如图9 所示。
图9 不同实例簇对应的最优聚类参数Fig.9 Optimal clustering parameters corresponding to different instance clusters
从图9 中可以看出不同的实例簇所对应的最优聚类参数是不同的，主要原因就是最优聚类参数会受到实例簇中节点数量、边的数量以及实例簇相关子图结构的影响。
本文提出了一种实例簇驱动的图结构聚类参数计算算法，可以根据用户提供的实例簇得到满足当前实例簇需求且不包含任何冗余节点的一组最优聚类参数μopt和εopt。基于此提出了一个实例簇驱动的图结构聚类参数计算的基本算法PART；
然后对PART 算法进行了改进，提出了一个有效的实例簇驱动的图结构聚类参数计算的改进算法ImPART，提高了参数计算效率。实验结果表明，所提算法可以快速且准确地找到满足用户提供的实例簇需求的最优聚类参数。未来将探索更有效的参数计算算法，更快确定密度约束参数μ的有效可行区间，通过更有效地对实例簇中节点进行划分，更有效地获得满足实例簇需求的最优聚类参数。
