基于结构熵约束的图聚类方法

张志颖，田有亮,3

（1. 贵州大学计算机科学与技术学院，贵州 贵阳 550025；2. 贵州省公共大数据重点实验室，贵州 贵阳 550025；3. 贵州大学密码学与数据安全研究所，贵州 贵阳 550025）

1 引言

在大数据和5G时代的环境下，云计算、大数据和物联网等为代表的信息技术得到了前所未有的飞速发展[1-2]。新技术的不断涌现和发展，让人们意识到数据的价值和开放共享[3]的重要性。例如，在物联网的大数据社交电子商务中，智能设备通过感知用户的偏好和浏览足迹，为用户提供精准的商品和便捷的服务[4]。因此，在大型网络图中，迫切需要利用一种方法来发现网络图中的真实结构和相关程度。

图聚类是一种针对图中节点间的某种相近或相似性的划分方式[5]，发现图中各节点数据间的相关关系，并通过聚类效果为智能设备提供有效的服务。近年来，图聚类在社交网络[6]、医学图像[7]和生物数据网络[8]等应用领域得到了广泛的发展。因此，根据网络图生成一个无向无权图，可以通过结构熵[9]来检测图结构中的真实结构，进而更有效地挖掘出图中节点的关联程度。

目前，研究者对共享和挖掘图结构中数据的兴趣不断增长，对社交网络中隐私数据的保护力度也在逐渐加大。Keyvanpour等[10]在隐私保护数据挖掘中提出了一种新的自定义隐私模型。进一步扩展了有向无环图的隐私模型和讨论了发布社交网络时的隐私风险[11]，当数据挖掘算法应用于真实数据集时，可被恶意数据挖掘者用来威胁社交网络用户的隐私。Al-Saggaf等[12]在社交网络上下文中使用决策森林数据挖掘算法，该算法不仅构建了决策树，而且还建立了一个森林，允许从数据集中探索更多的逻辑规则。数据集的庞大，导致数据集中存在敏感信息。并且这项技术在信息提取、数据缩减和隐私方面也面临着巨大的技术挑战。Görnerup等[13]提出了一种从大量蜂窝网络数据中挖掘路线信息的复合方法，该方法可通过分布式集群有效减少序列数据来解决可伸缩性问题，以及通过将原始数据分组到聚合中之后，在需要时对有关聚合的统计进行扰动以实现进一步的隐私保护。

为了平衡网络的效用和隐私，周艺华等[14]针对如何在保证隐私安全的前提下，挖掘出有效知识的问题，提出了一种基于聚类的社交网络隐私保护方法，该方法有效地减少了信息损失，提高了数据有效性。Yan等[15]提出了一种细粒度的差分隐私机制，用于在线社交网络中的数据挖掘。还考虑了针对差分隐私的共谋攻击，提出了保护隐私数据挖掘的对策。Tian等[16]介绍了一种用于将不确定性注入社区以生成不确定性图的隐私保护方法。关键思想是混淆原始图形的一部分，以实现隐私保护和有效地提高数据的实用性，并使用公开的真实数据集评估生成的不确定图的实用性。

针对网络数据挖掘研究成果中存在高冗余和不安全的问题。Jiang等[17]提出了一种基于Apriori算法的网络隐私数据挖掘方法，基于结合数据冗余分析、过滤和伪装，采用优化的TS Apriori算法对伪装后的数据集进行挖掘。实验结果表明，该方法存在冗余度低、安全性强和挖掘精度高等优点。Reza等[18]提出了一种3LP+（three layers of protection）隐私保护技术，以保护用户的敏感信息泄露，将3LP +应用于合成生成的在线社交网络数据集，并证明3LP +优于现有的隐私保护技术。为了分析和查看人们对在线商人、社交网络和其他数字媒体的隐私和安全。Alshaikh等[19]使用最广泛的社交网络之一Twitter，以分析Twitter用户之间的交互，为了提取有意义的数据以帮助确定用户对数字世界的隐私和安全的感知。然而以上研究方法并不能检测出图结构中数据结构的真实信息，从而在挖掘图结构中关联信息时可能会存在一定的误差。

因此，本文需要解码出网络结构的真实结构，进一步地挖掘出图结构的关联信息。Li等[20]定义了图的结构熵的概念，以度量图中嵌入的信息，并确定和解码图的基本结构。Li等[21-23]首先提出了一种通过网络结构熵的度量方法来寻找社区的算法。他们发现，社区检测算法可以准确识别几乎所有自然选择产生的网络社区。随后提出了图的抵抗力的概念，使用一个伴随结构熵的概念来度量图抵抗策略性病毒攻击的级联失败的能力。进一步提出了一种利用结构信息理论的快速且无归一化的算法来解码染色体域。Liu等[24]提出了一种基于社区的结构熵来表达由社区结构揭示的信息量。通过利用用户账户的社区隶属关系，攻击者可以推断出敏感的用户属性。这就提出了社区结构欺骗的问题，并着重于在在线社交网络中披露社区结构的隐私风险。

基于以上研究，本文针对大规模动态数据之间的关联程度，提出了一种基于结构熵约束的图聚类方法。相比已有工作，该方法通过引入结构熵来度量动态复杂网络，解码出网络的真实结构信息，解决了现有文献对动态复杂网络中信息关联刻画不足的问题。具体而言，本文的贡献如下。

1) 提出了利用二维结构信息的求解算法和熵减原则的聚类算法。通过算法将图结构中节点进行划分，关联程度强的划分为一个模块，从而挖掘出图结构中关联程度强弱的模块隐私信息。

2) 提出了K维结构信息的求解算法。通过算法将已划分的模块做进一步的划分，得到图中所有节点的关联程度。同时结构熵可以解码出在大规模噪声结构中图结构的信息，这个信息能区分图结构中的规律和噪声，从而挖掘出图结构中节点的实质结构。

3) 通过实例分析和实验评估表明，所提出的图聚类方法不仅能够有效地反映图结构的真实结构，而且还能有效地挖掘出图结构中节点之间的关联程度。与其他3种聚类方法相比，该方法在执行时间上具有更高的效率，并且保证了聚类结果的可靠性。

2 相关概念定义

定义1（图的编码树[20-25]）设图G=(V,E)，图的编码树T，使得图中的每个节点都在编码树中，存在顶点集V的子集Tα，并且以下属性成立。

对于根节点λ，定义一个集合Tλ=V。

对于每个节点α∊T，αˆ〈j〉表示α的子节点，j是1到自然数N从左到右递增。每个内部节点至少有两个直接后继节点，因此当i＜j时，αˆ〈i〉在αˆ〈j〉左边。

对于α∊T，都有一个与α相关的子集Tα⊂V，对于α，β。α表示β的父节点，如果α≠λ，α-表示α的父节点。

对于每一个i，{Tα|h(α)=i}是V的一个分区，其中h(α)是α的高度，根节点的高度为0，当α≠λ时，h(α) =h(α-)+1。

对于每个节点α，Tα是Tβ对所有β的联合，β-=α，因此Tα=∪β-=αTβ。

对于T的每个叶子节点α，Tα是一个单例。因此Tα包含V中的单个节点。

对于每个节点α∊T，如果Tα=X为一组顶点X，则α是X的码字，记c(X)=α，X是α的标记，记M(α)=X。

定义2（结构熵[20]）设图G=(V,E)，根据图G的不同维度得到一维结构熵、二维结构熵和K维结构熵。将不同维度的结构熵的最小值定义为图在不同维度下的结构信息。

定义3（一维结构信息[20]）假设G=(V,E)是一个n个顶点m条边的无向连通图，对于每个顶点i∊ { 1,2,…,n}。用di表示G中顶点i的度，m为图边的数量，设Qi=di/2m。然后用概率向量Q=(Q1,Q2,…,Qn)来描述图G中顶点的平稳分布。由此可定义图G的一维结构信息：

定义4（二维结构信息[20]）给定一个无向连通图G=(V,E)，假设P= (X1,X2,…,XL)是V的一个分区，称Xj为一个模块或者社区。通过P定义图G的结构信息如下：

其中，L是分区P中的模块数，n j是模块Xj中的节点数，是Xi中第i个节点的度，V j是模块Xj的体积，也就是模块Xj中所有节点的度之和。gj是模块中Xj只有一个端点的边的数量。

因此可以定义图G的二维结构信息，也称之为模块熵：

其中，P是图G中所有可能划分出的分区模块。

定义5（图聚类[26]）根据节点间的某种相近或相似性，利用聚类方法将图中所有节点划分成一些聚类，这个过程被称为图聚类。

为了更好地理解图聚类，本文将图聚类表示为社交网络图G上的一种映射关系φ:(v1,v2,…,vn)→(X1,X2,…,Xm)，φ满足以下两个条件。

3 问题描述

3.1 方案模型

结构熵被用来度量嵌入图结构中的不确定性，结构熵的最小化是解码图结构中真实结构的一种直观的方法。通过图结构的结构熵最小化，将图结构的随机变化和噪声引起的扰动减小到最小，并且在比较图结构的节点模块合并前后结构熵的差异程度过程中，可反映出图结构中节点之间的关联程度。如图1所示，在图结构交互过程中如何有效地挖掘出它们之间的关联程度是本文所要考虑的新问题。针对这一问题，可以用图的二维结构熵度量图中的结构信息。对于图中的每一个节点模块，在模块的生成过程中，任意两个节点模块的合并必须满足熵减原则，也就是说两个节点合并后的模块熵较合并之前减少的越多，表示模块合并后的不确定性越低，其图结构的二维结构熵也越小。这就反映了网络结构中本质的真实结构信息，即网络结构的结构熵越小，模块中的节点关联程度越强。

图1 图结构节点聚类模型Figure 1 Graph structure node clustering model

3.2 算法设计

为了能从大规模噪声结构中挖掘出图结构的隐私信息，必须利用结构熵的最小值来解码图结构的真实结构，从而更好地反映出图结构中任意两个节点的关联程度。在此，本文提出利用二维结构熵最小值的计算算法和熵减原则的模块分区算法来得出图结构中节点的关联性。

为了解决网络结构中数据的高精度问题需要一个新的信息度量，能度量嵌入在复杂系统中的信息，这个信息能区分网络结构中数据的规律和噪声，从而解码出嵌入在大规模噪音结构中的规律。因此需要设计算法1。

算法1二维结构信息最小值求解算法

输入一个n个顶点m条边的无向连通图G=(V,E)

算法1可计算出一个n个顶点和m条边的无向连通图G的二维结构信息，图G的二维结构信息就是图所能划分的所有模块熵的最小值。设图的二维结构熵在最小值时所对应节点的划分为分区P，P= {X1,X2,…,XL}。其中，分区P是对所有节点的一个划分，X i(i= 1,2,…,L)是划分P下的一个模块或者说是一个社区，模块是由部分节点组成的集合。然而针对不同的划分结果，计算出图的二维结构信息也不同。只有当图的二维结构信息取值为模块熵的最小值的时候，对应的图中节点分区P才能体现出该图的节点关联程度的最优结果。也就是当图的二维结构信息最小时，模块中节点的不确定性最小，节点的关联程度最强。

然而在计算二维结构信息时，为了得到模块熵的最小值，只能通过不同的分区和计算进行比较。然而无法快速地通过计算对比来减少计算成本，从而无法更有效地确定图中的顶点的划分结果是否完善。因此，进一步地利用二维结构信息和熵减原则来有效提高本文获取模块分区的结果。为了能够将图中节点有效分区，得到节点模块之间的关联程度设计了算法2。

算法2网络节点模块分区算法

输入一个n个顶点m条边的无向连通图G=(V,E)

该算法的节点模块划分方法的主要过程如下：假设v1,v2,…,vn是节点集合V中所有按顺序排列出的节点。将Xi设置为所有i的单例{vi}，构成了所有节点集V的初始划分模块。如果不存在满足i＜j这样的，则返回分区P。否则，有i0,j0使得是所有i,j在上的最大值，得到其中，表达式如下：

根据二维结构信息最小值求解算法和网络节点模块分区算法可以有效地处理图的结构信息数据，从大规模噪声结构中解码出图节点之间的关联程度，既不需要改变原始数据也不需要选择参数。这就排除了在归一化或在参数选择中可能产生噪声的影响。

本节使用了一种基于结构信息理论的图节点分区算法。通过节点的划分模块和整体的划分分区，用结构熵的最小值来获取图中节点随机游动发生的不确定性，从而更好地反映出图节点之间的关联程度。因此，网络节点分区算法的本质是固定结构不确定性最大的网络节点，合并网络中连接紧密程度高的节点模块。节点的分区算法不仅挖掘出了使整个网络的不确定性最小化的基本结构，而且从模块分区结果中反映出网络中连接紧密程度最高的节点模块。

4 K维结构信息的聚类算法

网络表现为特定群体中多个个体及它们之间相互联系组成的集合，最适合用图来表示。其中，节点表示个体，边表示个体间的联系。常见的网络图结构模型为简单的图模型G=(V,E)，在图G中，V= {v1,v2,…,vn}为图中节点集，E= {(vi,vj)| 1≤i,j≤n,i≠j}为边集。图中任何边(vi,vj)表示节点之间的联系，为结构边。根据实际网络中个体之间联系的紧密程度不同，结构边的权值不同。本文假设给定的是一个无向无权的连通图，结构边具有相等的权值，均为1。

为了发现图中的簇，把图分割成若干块。每一块是一个簇，使得簇内的节点能够以利益最大化的方式有效地连接，而不同簇内的节点之间以较弱的方式连接。因此，本文通过利用结构熵能检测图结构的真实结构来更有效地对图中节点进行划分。其主要特点都是聚类，将图中所有节点划分为模块子集的过程，使得图中相似度最高的节点形成一个簇，簇内的节点与其他簇内的节点相似度最低。

图聚类问题的实质就是图划分问题，聚类的过程其实就是对图划分过程的优化。优化的目的是使划分的模块间的相似度变小，模块内的节点相似度变大。然而对于如何度量嵌入大规模噪声结构中的整体图结构的信息，仅是二维结构信息是远远不够的。因此，利用K维结构信息来作为图聚类的一种方法，也就是在二维结构信息和熵减原则的基础上，进一步地计算出图结构的最小结构熵，从而更有效地反映图结构的真实结构。为了更加针对性地对图中节点间的关联程度做出有效的挖掘，设计了算法3。

算法3K维结构信息求解算法

定义6（K维结构信息[20]）对于一个无向连通图G=(V,E)，假设T是图G的分区树。通过T定义图G的结构信息如下：

对于任意顶点α∊T，如果α≠λ，λ为树T的根节点，那么定义顶点α的结构信息为其中，gα是从Tα中的节点到Tα之外节点的边数，Vα是集合Tα的体积。

通过分区树T定义图G的结构信息如下：

图G的K维结构信息定义如下：

其中，T覆盖图G的所有分区树，K表示T的高度。算法3计算出图结构的整体K维结构信息，K维结构信息能挖掘嵌入在图结构中的信息，这个信息能区分图结构的规律和噪声，从而解码出嵌入在大规模噪声结构中的规律，进一步决定并解码出该图结构的真实结构。通过在二维结构信息的基础上加入merge和combine两个算法，将图结构由高度为2的分区树转化为高度为K的分区树，从而进一步地划分图结构中节点的关联程度。因此，当K维结构熵越小时，越能反映出图结构中单个节点间的关联程度。

聚类分析可以对网络中节点实行分组管理，使得组内的节点具有非常相似的特性或者需求，这有利于应用在智能设备中更好地服务用户和加强对用户信息的保护。利用结构信息的最小化将复杂的网络抽象成一个图，不仅对分析整体网络的结构信息有着重要的帮助，而且还能对网络中用户的隐私信息进行挖掘和保护有着重要的意义。具体来说，根据模块熵和熵减原则，对图中节点进行合并得到不同的模块，进一步根据图的K维结构熵的最小值K维结构信息，最终得到对所有图节点的关联聚类。此时，结构熵能度量出图在大规模噪声结构中的信息，所得到的信息也反映了图的真实结构。其中节点的模块分区就表示图结构在挖掘图中关联信息条件下的聚类结果，便可将图中隐私信息关联程度紧密的节点划分为一个模块，而模块间节点隐私信息的关联程度远远小于模块内节点的关联程度。

5 实验评估与分析

本节通过实验来评估本文所提出的方法，并给出详细的实验结果和讨论与其他方法的优缺点。

5.1 实验评估

本文随机生成一个15个顶点60条边的无向无权的网络模型图。如图2所示。

图2 随机生成图Figure 2 Randomly generated graph

首先通过算法1和算法2对图进行模块划分，计算出图的二维结构信息H2(G)3.23= 。由此可见，通过二维结构信息和熵减原则算法，将图划分为大小不同的模块，并计算不同模块的结构熵H P(G)，最终得出图的二维结构信息H2(G) =min{H P(G)}，此时模块P的划分结果便是图中节点属性相关程度大的为一个模块。因此，如图3所示，利用算法1和算法2将图划分为模块P={X1,X2,X3,X4}，且X1={A,E,H}，X2={B,F,G,I,L}，X3={C,D,K,M,O}，X4={J,N}。

图3 模块熵的关联节点Figure 3 Associated node of module entropy

然后将图划分的模块P转化为高度2的分区树，引入根节点λ，模块P中每一个子模块X i(i= 1,2,3,4)为树节点，每个子模块中的节点为该树节点下的叶子节点。二维分区树如图4所示。

图4 二维分区树Figure 4 Two-dimensional partition tree

最后将以模块P的最优划分结果通过算法3做进一步的节点聚类，并计算出图的K维结构信息H K(G)= 3.07。因此，通过K维结构信息聚类算法，将所有的模块P生成的二维分区树转化成高度为K的分区树，并计算出不同的K维分区树的结构熵H T(G)，最终得出图的K维结构信息H K(G) =min{H T(G)}，此时所得到的分区树便是将图中每个节点属性关联程度最大的聚类在一起。如图5所示，从图3中可以看出，利用算法3将模块中的节点再一次进行划分，得到划分结果更为详细。因此，可以得到在模块X1中节点A、E关联程度更大，模块X2和X3中节点进一步得出两两关联程度：X2:((G,(B,L)),(F,I))，X3:((K,(C,M)),(D,O))，模块X4中的关联程度没有变化。

图5 K维分区树Figure 5 K-dimensional partition tree

当图中顶点和边的数量在不断变化时，图结构的本质信息也会改变，从而导致图的划分结果也会随之变化，如表1所示。随机生成4个不同大小的网络图，通过二维结构信息的划分方法将图中相似度高的节点分成一个模块，再通过K维结构熵最小值的原理将模块中的节点进一步划分，最终得到图中所有节点间的关联程度。所以，本文通过结构熵挖掘出图中节点关联程度大的节点都属于一个模块，而节点之间关联程度小的则被划分在不同的模块中。因此可以利用结构熵的最小值来体现网络节点的关联程度，从而挖掘出网络结构中节点之间的交互信息以及其他相关信息。

表1 不同网络图的聚类效果Table 1 Clustering result of different network graphs

5.2 有效性比较与分析

对数据挖掘的研究领域中，聚类往往可以直接或者间接地描述数据的关联程度，从而能够有效地分析数据的相关特性。因此聚类分析算法是探索数据分析的关键要素，其中K均值算法因其易于实现、可并行性强和计算成本相对较低而成为最受欢迎的方法。然而正如文献[27]提出的K均值对初始条件的高度依赖，以及在大规模数据集中可能无法很好地扩展。文献[27]提出了一个递归并行逼近K均值算法，该算法在不影响逼近质量的情况下，能很好地根据问题实例的数量进行缩放。但是该算法在递归次数和计算开销方面都消耗较大，无法有效地分析社交网络或图等结构化网络图中所嵌入的信息。

划分和层次方法旨在发现球状簇，对于给定的数据很难发现任意形状的簇。然而为了发现任意形状的簇，可以把簇看作数据空间中被稀疏区域分开的稠密，从而可以发现任意非球状的簇。基于密度的噪声应用空间聚类（DBSCAN，

density-based spatial clustering of applications with noise）是基于密度的聚类算法，也是主要的聚类范式之一。尽管DBSCAN算法已被广泛应用，但算法本身依然存在一定的缺点。DBSCAN算法的输入参数包括扫描半径ε和阈值MinPts，在聚类的过程中需要计算每个数据点的密度。数据点的密度与从该点到其他所有点的距离有关，使得聚类过程中存在很多冗余的距离计算，复杂度高，效率低。因此，该算法同样不适用于大规模数据和高维数据。Li等[28]对DBSCAN的聚类原理进行了深入的分析和研究，发现DBSCAN的核心问题是寻找每个点的最近邻，然后通过三角不等式提出了一种基于最近邻相似的快速密度算法，并且利用覆盖树对每个并行点的领域进行检索，可以有效减少聚类过程中距离计算的次数，提高聚类效率。但是，该算法的不足在于只基于最近距离来分析每个节点的相似度，忽略了网络的自组织原理与网络节点所嵌入的结构信息对图聚类的影响。

图聚类主要是针对图的一种聚类方法，用来搜索图找出节点间某种相似的特性形成一个簇。网络结构聚类算法（SCAN，structural clustering algorithm for networks）在处理大型网络图时，其时间复杂性关于边数是线性的，具有良好的可伸缩性。SCAN是一种快速高效的集群技术，用于查找隐藏的社区并隔离网络中的集线器或异常值。然而，对于大型网络仍然需要相当多的时间。Stovall等[29]提出了一种基于计算统一设备架构（CUDA，computer unified device architecture）的SCAN并行实现（GPUSCAN，graphic processing unit structural clustering algorithm for networks）。SCAN的计算步骤经过仔细的重新设计，通过将SCAN转化为一系列高度规则和独立的并发操作，使其在图形处理单元（GPU，graphic processing unit）上高效运行。通过GPUSCAN，可以将大型网络或一批不相交的网络卸载到GPU，以进行非常快速且高效的结构聚类。GPUSCAN是在考虑CUDA的情况下开发的，启用CUDA的GPU充当了并行分布式系统的缩影。由于GPUSCAN专注于合并和本地资源访问方法，因此具有可伸缩性，并且可以轻松地适应并发或分布式环境。相比之下，SCAN基于广度优先搜索，尽管计算效率高，但往往需要高频率的随机资源访问，并迅速成为超大型网络的I / O绑定。GPUSCAN当前受GPU上可用的设备内存量的限制。虽然可以通过将复杂的计算分布在多个连接的GPU上，从而可以轻松地扩大规模，但其开销仍是一个难以解决的问题。

因此，表2对以上3种聚类方法与本文所提出的基于结构熵的图聚类方法进行了比较。从表2可以看出，文献[27]所提方法的时间复杂度为O(nkt)，因此，该方法在计算大规模数据集时，将消耗大量的计算时间和计算开销。文献[28]所提方法的时间复杂度为logn+ MinPts2])，该算法在聚类过程中具有许多冗余计算，导致效率低和复杂度较高的问题。文献[29]所提方法的时间复杂度为O(n2)，该方法的计算效率与本文方法存在很小的差距，但该方法受GPU上可用的设备内存限制，将会增加聚类过程中的开销问题。由于图的结构信息能够度量出图结构中所嵌入的信息，这个信息量可以更好地反映出图结构的真实结构。因此，可以在大规模噪声结构中解码出网络结构的真实结构信息的情况下，利用结构熵更有利于对图结构中节点的关联信息的挖掘，从而将达到节点属性有效地聚类。因此，无论是在处理大规模数据集时，还是在动态复杂的网络结构中，本文方法在计算规模、计算开销以及计算效率等方面都优于其他方法。

表2 聚类功能对比Table 2 clustering function comparison

5.3 仿真分析

本文实验环境是一台CPU为Intel (R)Core(TM) i5-7500，内存为8 GB，操作系统为64位Windows 10的计算机。选用Python作为编程语言，模拟运行熵减原则图划分算法和图节点的聚类算法。如图6所示，本文使用0~10 000的不同节点数量运行6个实验，比较了本文所提出的二维结构信息和熵减原则下的图划分算法与K维结构信息对图节点的相似聚类算法的执行时间。

图6 不同网络节点图划分与图聚类的执行时间Figure 6 The execution time of graph division and graph clustering of different network nodes

结果表明，随着节点数量的增大，算法的执行时间在不断增加。在执行时间上，图结构的节点聚类算法的执行时间总是多于图结构的节点划分算法。然而，图聚类与图划分相比，聚类整个图结构中节点关联信息的成本更高，但图聚类算法对图结构中节点聚类的效果更好。因此，图节点的聚类算法是在图划分算法的基础上进行的。也就是在得到图中节点的模块划分之后，进一步为了得出节点之间的关联程度，利用K维结构熵的最小值对已划分的模块做进一步的聚类，从而有效地得出整体图结构中节点之间的关联程度。

4种节点聚类方案的执行时间如图7所示。结果显示，本文方法与其他3种方法在执行小规模数据时，执行时间和成本开销相差较小。然而在执行大规模数据时，本文所提出的聚类方法有较短的执行时间。从而反映了本文方法能够有效地执行大规模的动态数据，缩短聚类时间和减小聚类成本。对于文献[27]方法而言，随着数据集的增加，K-means算法的执行时间大大增加，导致计算开销也随之增加。文献[28]方法，在数据集中选择的参数均为eps = 0.1，minPts = 10。随着数据集的变化，DBSCAN算法的执行时间也有较大幅度的上升。相对于文献[29]方法而言，由于本文不需要计算分布在多个GPU上来扩大规模，因此缩短了计算时间，同时也存在相对较小的开销成本问题，极大程度上提高了本文方法对图结构中节点关联信息的聚类效率。

图7 不同网络节点4种聚类方案的执行时间Figure 7 The execution time of the four clustering schemes for different network nodes

为了实现一个高效的动态聚类方法，本文利用结构熵的最小值来反映图结构节点的最优聚类效果。图8为模拟网络节点的数目在100~500变化的情况下进行的节点聚类所得到二维结构熵和K维结构熵的最小值。从图8中可以看出，随着节点数目的增大，结构熵的值也增大。然而在相同节点下，K维结构熵总是小于二维结构熵。因此更好地说明K维结构信息能够有效地反映图结构的真实信息，从而有利于针对图结构中节点得出最优的聚类结果。同时结构熵可以用来度量嵌入在一个图中的高维信息或深度信息，并且在度量结构信息的同时解码出原始图结构的实质结构。因此，可以将结构熵的最小值K维结构信息看作是解码图结构中节点真实信息的衡量标准，有效地反映了图结构中节点之间的聚类效果。

图8 不同网络图的熵值对比Figure 8 Comparison of entropy values of different network diagrams

6 结束语

本文基于结构熵的聚类方法提出了对图结构中节点的划分。该方法主要是检测出图结构中的真实结构信息，同时挖掘出图结构中节点之间的关联信息。具体来说，本文方法不仅适用于大规模的网络图结构，而且还在保证聚类结果可靠性的同时，有效地提高了计算效率，减少了开销。在未来的工作中，将进一步研究当无向无权图扩展到有向加权图时，如何挖掘图结构中的关联信息，以及如何有效地保护挖掘出来的结构信息和原始图结构中的隐私信息。