基于相对熵的动态图摘要算法

1.本发明涉及一种基于相对熵的动态图摘要算法，属于计算机技术领域。


背景技术：

2.图结构数据能够表现实体对象之间的复杂关系，研究者们一般采用图结构来描述用户间的信息交互。然而，现有应用的庞大的用户基数带来了海量用户交互数据，往往具有上亿顶点和千亿条边，难以进行直接的分析处理。图摘要技术将复杂的图数据压缩到一个简洁的摘要信息中，可以对海量的大图数据进行简洁高效的处理，从而节省存储空间和计算资源。
3.传统的图摘要方法多研究静态图场景下的图摘要算法，难以及时反馈给用户关键的信息。
4.有鉴于此，确有必要提出一种基于相对熵的动态图摘要算法，以解决上述问题。


技术实现要素：

5.本发明的目的在于提供一种基于相对熵的动态图摘要算法，可以在进行动态图摘要时有效的提高摘要效率，还能使摘要得到的结果更具有原始图的一些特征。
6.为实现上述目的，本发明提供了一种基于相对熵的动态图摘要算法，主要包括以下步骤：
7.步骤1、结构特征构建阶段：给定无向图g＝(v,e,ω)，v代表顶点集合，e代表边集合，ω是边权重，对任意v∈v，计算v的所有三步可达顶点集合n(v)；
8.步骤2、初始图摘要阶段：基于v中所有顶点的特征向量的杰卡德相似度距离，使用k均值算法对节点进行粗聚类，聚类结果记为c1、c2…cn
；根据聚类结果合并超点，将节点数小于等于阈值的簇直接合并为超点vi；
9.步骤3、动态图摘要阶段：在动态过程中到达一个新增节点v，基于步骤1计算节点v的特征向量x，并计算最小哈希值的概率分布q(xi)；
10.步骤4、动态调整阶段：从新增节点v的二跳可达节点n(v)中随机抽取一个节点v1。
11.作为本发明的进一步改进，步骤1中，根据n(v)生成一个布尔向量表示该节点的三跳邻居特征，并将所有特征向量组成特征矩阵mv，用最小哈希值方法计算出各节点的k个最小哈希值和各节点间的杰卡德相似度。
12.作为本发明的进一步改进，对所述特征矩阵进行行重排，得到一个新的矩阵，每一个节点vi的第一个非零布尔值所对应的行即为节点vi的一个最小哈希值。
13.作为本发明的进一步改进，步骤2中，以杰卡德相似度作为距离对节点进行粗聚类，根据聚类结果合并超点，对于聚类结果中节点数小于等于阈值的簇直接合并为超点vi，对于节点数大于阈值的簇，对簇内节点随机分块，在使σ尽可能小的原则下合并为超点vj，之后在满足的超点之间建立超边，同时计算超边的权重。
14.作为本发明的进一步改进，步骤2还包括，随机选取k个节点作为初始聚类中心其他所有节点加入杰卡德相似度最高的聚类中心所在的簇，然后选出每个簇中和其他节点平均相似度最高的节点作为新的聚类中心，再重复此过程两次后的分簇结果即作为粗聚类的最终结果。
15.作为本发明的进一步改进，步骤2还包括，将聚类结果中节点数小于等于阈值的簇直接合并为超点vi，对于节点数大于阈值的簇进行进一步的划分，对簇内节点随机分块l次，选取σ最小的一次分块合并为超点vj，将超点vi、vj加入超点集合s，之后在满足的超点之间建立超边p
ij
＝{vi,vj,w
ij
}，并加入超边集合p，
16.其中，h是超点个数、ni是超点i中的节点个数、pi(x)是超点i的最小哈希值分布；指的是vi超点合vj超点中原始节点之间潜在的边，指的是vi超点合vj超点中原始节点之间实际存在的边，w
ij
是中所有边的权重之和，作为超边的权重，最终摘要图的形式为g
*
＝(s,p,w)，s是超点集合，p是超边集合，w是与p对应的权重集合。
17.作为本发明的进一步改进，步骤3中，然后计算节点v和各个超点的相对熵，将节点v加入与其相对熵最小的超点，在此过程中新增节点v以概率θ逃逸，独立成为一个新的超点。
18.作为本发明的进一步改进，基于概率分布q(xi)和概率分布p(xi)计算新增节点和各个超点的相对熵，相对熵又可称为kl散度，描述两个概率分布p和q的差异性或相似性，用d
kl
(p||q)表示，
19.d
kl
(p||q)＝h(p,q)-h(p)
[0020][0021]
其中，d
kl
为最小相对熵，θ与d
kl
成反比，将新增节点加入与其相对熵最小的超点v0，并更新v0相连超边的权重。
[0022]
作为本发明的进一步改进，步骤4中，在满足损失阈值的条件下，将v1转到与其相对熵最小的超点中。
[0023]
作为本发明的进一步改进，在尝试把v1移动到v2的过程中只需要考虑
[0024]
的值是否减小，能使σ0减小则将v1其转到与其相对熵最小的超点v0中，其中，p1(x)是v1所在超点v1的最小哈希值概率分布、p2(x)是超点v2的最小哈希值概率分布。
[0025]
本发明的有益效果是：本发明得到的摘要图具有新的变化趋势和新的特征，能够
减少摘要时间，节省了计算资源，避免了以往动态图摘要算法采样慢、存储空间大等缺陷，能够更好的应用于图流场景，在图处理领域有较好的应用价值。
附图说明
[0026]
图1为本发明基于相对熵的动态图摘要算法的框架图。
具体实施方式
[0027]
为了使本发明的目的、技术方案和优点更加清楚，下面结合附图和具体实施例对本发明进行详细描述。
[0028]
在此，需要说明的是，为了避免因不必要的细节而模糊了本发明，在附图中仅仅示出了与本发明的方案密切相关的结构和/或处理步骤，而省略了与本发明关系不大的其他细节。
[0029]
另外，还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。
[0030]
如图1所示，本发明揭示了一种基于相对熵的动态图摘要算法，主要包括结构特征构建阶段、初始摘要阶段、动态摘要阶段、动态调整阶段这四个阶段，主要包括以下步骤：
[0031]
步骤1、结构特征构建阶段：给定无向图g＝(v,e,ω)，v代表顶点集合，e代表边集合，ω是边的权重。对任意v∈v，计算v的所有三步可达顶点集合n(v)。根据n(v)生成一个布尔向量表示该节点的三跳邻居特征，并将所有特征向量组成特征矩阵mv。用最小哈希值方法计算出各节点的k个最小哈希值和各节点间的杰卡德相似度。
[0032]
集合v的大小为n(给每个节点编号)。从出发进行三步扩展，获取三跳可达节点n(vi)，据此获得vi的三跳邻居特征值，所有节点的三跳邻居特征值在一起组成一个特征矩阵，如下表1所示：
[0033]
表1
[0034][0035]
对特征矩阵进行行重排，得到一个新的矩阵，每一个节点vi的第一个非零布尔值所对应的行即为节点vi的一个最小哈希值。以v1为例若a
11
、a
21
、a
31
的值都为0,且a
41
为1，则v1的一个最小哈希值为4。随机选择k个排列变换对上述特征矩阵进行随机行重排，对于每一个节点vi，值将会得到k个最小哈希值。节点vi的最小哈希签名即为这k个最小哈希值构成的
列向量。
[0036]
两个节点之间，最小哈希值相等的重排数列为x，最小哈希值不相等的重排数列为y，则这两个节点之间的杰卡德相似度可近似为x/(x+y)。以这种方式计算所有节点对之间的杰卡德相似度。
[0037]
步骤2、初始图摘要阶段：基于v中所有顶点的特征向量的杰卡德相似度距离，使用k均值算法对节点进行粗聚类，聚类结果记为c1、c2…cn
；根据聚类结果合并超点，将节点数小于等于阈值的簇直接合并为超点vi。对于节点数大于阈值的簇，对簇内节点随机分块，并在合并规则下合并为超点vj，之后检查是否需要在各个超点之间建立超边，同时会合成超边的权重。
[0038]
具体地，步骤2中，以杰卡德相似度作为距离对节点进行粗聚类。根据聚类结果合并超点，对于聚类结果中节点数小于等于阈值的簇直接合并为超点vi。对于节点数大于阈值的簇，对簇内节点随机分块，在使σ尽可能小的原则下合并为超点vj。之后在满足的超点之间建立超边，同时计算超边的权重。
[0039]
随机选取k个节点作为初始聚类中心其他所有节点加入杰卡德相似度最高的聚类中心所在的簇。然后选出每个簇中和其他节点平均相似度最高的节点作为新的聚类中心。再重复此过程两次后的分簇结果即作为粗聚类的最终结果。
[0040]
将聚类结果中节点数小于等于阈值的簇直接合并为超点vi。对于节点数大于阈值的簇进行进一步的划分，对簇内节点随机分块l次，选取σ最小的一次分块合并为超点vj。将超点vi、vj加入超点集合s，之后在满足加入超点集合s，之后在满足的超点之间建立超边p
ij
＝{vi,vj,w
ij
}，并加入超边集合p。
[0041]
其中h是超点个数、ni是超点i中的节点个数、pi(x)是超点i的最小哈希值分布；指的是vi超点合vj超点中原始节点之间潜在的边，指的是vi超点合vj超点中原始节点之间实际存在的边。w
ij
是中所有边的权重之和，作为超边的权重。最终摘要图的形式为g
*
＝(s,p,w)，s是超点集合，p是超边集合，w是与p对应的权重集合。
[0042]
步骤3、在动态过程中，对于每一个新增的节点v，先统计其三步可达节点，根据这些节点可以获得新增节点的k个最小哈希值，再统计这些最小哈希值的概率分布q(xi)。
[0043]
基于概率分布q(xi)和概率分布p(xi)可以计算新增节点和各个超点的相对熵。相对熵又可称为kl散度，描述两个概率分布p和q的差异性或相似性，用d
kl
(p||q)表示，
[0044][0045]
将新增节点加入与其相对熵最小的超点v0，并更新v0相连超边的权重。为了避免超点的数量不再随时间增加，在此过程中新增节点以概率θ逃逸为一个新的超点，这里d
kl
为最小相对熵，θ与d
kl
成反比。
[0046]
步骤4、如果新增节点的邻近节点v0已经在节点集合中，考虑新增节点对周围结构的影响，找到新增节点v的两跳可达节点n(v)，从v0的邻近节点n(v0)中随机抽取一个节点v1，v1在超点v1中。在能使σ减少的条件下，将v1转到与其相对熵最小的超点v2中，并更新与v1、v2相连超边的权重。
[0047]
在尝试把v1移动到v2的过程中只需要考虑
[0048]
的值是否减小，能使σ0减小则将v1其转到与其相对熵最小的超点v0中，其中，p1(x)是v1所在超点v1的最小哈希值概率分布、p2(x)是超点v2的最小哈希值概率分布。
[0049]
综上所述，本发明基于最小哈希值方法以及相对熵理论，提出了一种图流场景下基于相对熵的动态图摘要算法。先是用最小哈希值方法计算出各节点的三跳邻居特征值及特征值的杰卡德相似度，并以此作为距离进行快速的k均值聚类，再根据簇内节点数阈值和合并规则进行大小簇合并，然后生成超点、超边及其权重。在动态过程中，对于新增节点，先计算其与每个超点间最小哈希值分布的相对熵，之后新增节点也会以概率θ逃逸成一个新的超点，这个概率与最小的相对熵成反比，未逃逸的新节点会加入与其相对熵最小的超点。最后计算新增节点的两跳邻居节点与各超点间的相对熵，根据相对熵调整邻居节点所属的超点。
[0050]
本发明通过最小哈希值算法得到每个节点的最小哈希值，再基于最小哈希值计算节点间的杰卡德相似度，以此作为距离进行粗聚类，并基于聚类结果进行初始的超点合并。在动态过程中则根据相对熵来将新增节点加入超点，并考虑新增点对周围点的影响尝试对周围点进行部分转移。相比于以往的动态图摘要算法，根据聚类情况进行初始图摘要，并在动态过程中依据相对熵将新增节点及其周围受影响节点加入到合适的超点中，得到的摘要图具有新的变化趋势和新的特征，能够减少摘要时间，节省了计算资源，避免了以往动态图摘要算法采样慢、存储空间大等缺陷，能够更好的应用于图流场景，在图处理领域有较好的应用价值。
[0051]
以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。

技术特征：
1.一种基于相对熵的动态图摘要算法，其特征在于，主要包括以下步骤：步骤1、结构特征构建阶段：给定无向图g＝(v,e,ω)，v代表顶点集合，e代表边集合，ω是边权重，对任意v∈v，计算v的所有三步可达顶点集合n(v)；步骤2、初始图摘要阶段：基于v中所有顶点的特征向量的杰卡德相似度距离，使用k均值算法对节点进行粗聚类，聚类结果记为c1、c2…
c
n
；根据聚类结果合并超点，将节点数小于等于阈值的簇直接合并为超点v
i
；步骤3、动态图摘要阶段：在动态过程中到达一个新增节点v，基于步骤1计算节点v的特征向量x，并计算最小哈希值的概率分布q(x
i
)；步骤4、动态调整阶段：从新增节点v的二跳可达节点n(v)中随机抽取一个节点v1。2.根据权利要求1所述的基于相对熵的动态图摘要算法，其特征在于：步骤1中，根据n(v)生成一个布尔向量表示该节点的三跳邻居特征，并将所有特征向量组成特征矩阵mv，用最小哈希值方法计算出各节点的k个最小哈希值和各节点间的杰卡德相似度。3.根据权利要求2所述的基于相对熵的动态图摘要算法，其特征在于：对所述特征矩阵进行行重排，得到一个新的矩阵，每一个节点v
i
的第一个非零布尔值所对应的行即为节点v
i
的一个最小哈希值。4.根据权利要求1所述的基于相对熵的动态图摘要算法，其特征在于：步骤2中，以杰卡德相似度作为距离对节点进行粗聚类，根据聚类结果合并超点，对于聚类结果中节点数小于等于阈值的簇直接合并为超点v
i
，对于节点数大于阈值的簇，对簇内节点随机分块，在使σ尽可能小的原则下合并为超点v
j
，之后在满足的超点之间建立超边，同时计算超边的权重。5.根据权利要求4所述的基于相对熵的动态图摘要算法，其特征在于：步骤2还包括，随机选取k个节点作为初始聚类中心其他所有节点加入杰卡德相似度最高的聚类中心所在的簇，然后选出每个簇中和其他节点平均相似度最高的节点作为新的聚类中心，再重复此过程两次后的分簇结果即作为粗聚类的最终结果。6.根据权利要求1所述的基于相对熵的动态图摘要算法，其特征在于：步骤2还包括，将聚类结果中节点数小于等于阈值的簇直接合并为超点v
i
，对于节点数大于阈值的簇进行进一步的划分，对簇内节点随机分块l次，选取σ最小的一次分块合并为超点v
j
，将超点v
i
、v
j
加入超点集合s，之后在满足的超点之间建立超边p
ij
＝{v
i
,v
j
,w
ij
}，并加入超边集合p，其中，h是超点个数、n
i
是超点i中的节点个数、p
i
(x)是超点i的最小哈希值分布；指的是v
i
超点合v
j
超点中原始节点之间潜在的边，指的是v
i
超点合v
j
超点中原始节点之间实际存在的边，w
ij
是中所有边的权重之和，作为超边的权重，最终摘要图的形式为g
*
＝(s,p,w)，s是超点集合，p是超边集合，w是与p对应的权重集合。7.根据权利要求1所述的基于相对熵的动态图摘要算法，其特征在于：步骤3中，然后计
算节点v和各个超点的相对熵，将节点v加入与其相对熵最小的超点，在此过程中新增节点v以概率θ逃逸，独立成为一个新的超点。8.根据权利要求7所述的基于相对熵的动态图摘要算法，其特征在于：基于概率分布q(x
i
)和概率分布p(x
i
)计算新增节点和各个超点的相对熵，相对熵又可称为kl散度，描述两个概率分布p和q的差异性或相似性，用d
kl
(p||q)表示，(p||q)表示，其中，θ＝1/e
dkl
，d
kl
为最小相对熵，θ与d
kl
成反比，将新增节点加入与其相对熵最小的超点v0，并更新v0相连超边的权重。9.根据权利要求1所述的基于相对熵的动态图摘要算法，其特征在于：步骤4中，在满足损失阈值的条件下，将v1转到与其相对熵最小的超点中。10.根据权利要求9所述的基于相对熵的动态图摘要算法，其特征在于：在尝试把v1移动到v2的过程中只需要考虑的值是否减小，能使σ0减小则将v1其转到与其相对熵最小的超点v0中，其中，p1(x)是v1所在超点v1的最小哈希值概率分布、p2(x)是超点v2的最小哈希值概率分布。

技术总结
本发明提供了一种基于相对熵的动态图摘要算法，包括对于初始图，首先用最小哈希值方法计算出各节点的三跳邻居特征值及特征值的杰卡德相似度，并以此作为距离对节点进行粗聚类；根据簇内节点数阈值和合并规则进行大小簇合并，然后生成超点、超边及其权重；在动态过程中，计算新增节点与各超点间最小哈希值分布的相对熵，将新点加入相对熵最小的超点；同时计算新增节点的两跳邻居节点与各超点间的相对熵，并根据相对熵调整邻居节点所属的超点。本发明得到的摘要图具有新的变化趋势和新的特征，能够减少摘要时间，节省了计算资源，避免了以往动态图摘要算法采样慢、存储空间大等缺陷，能够更好的应用于图流场景，在图处理领域有较好的应用价值。有较好的应用价值。有较好的应用价值。


技术研发人员：刘强 赵龙龙 刘浩 季一木
受保护的技术使用者：南京邮电大学
技术研发日：2023.05.12
技术公布日：2023/8/23