论文部分内容阅读
核值是一种反映图的聚合度的重要指标，也是图数据分析中紧密子图挖掘的一个热点，它适用于对网络拓扑结构的分析以及社区的查找，还可以用来遏制谣言的传播。静态图上的核值计算以及动态图上的核值更新分别称作核值分解和核值维护问题，这一类问题已经得到了广泛的研究。然而，绝大多数的这些研究都只关注于无权图，但是在现实场景下，大部分的图都是有权的，每个个体在网络中都自带一定权重。然而，目前还没有较为高效的算法能解决这一问题。
为了解决上述场景的问题，定义了应对点带权重场景的有权图核值，相较于无权图，图中的每个节点的权重都将被考虑。无权图可以看作是有权图每个节点权重为1的特殊情况。有权图的核值分解算法通过定义有权度，逐步的删除有权度最低的顶点以及相连接的边并为各个点分配了核值。
为应用于现实中动态图的场景，提出了有权图的单边插入删除核值维护算法。通过理论证明表明，当一条边插入或删除时，有权核值可能发生变化的顶点的有权核值范围确定且变化的范围有界，以此实现核值的更新。现实中的网络往往是多条边同时变化的，为了解决单边插入删除核值维护算法的局限性，提出了多边插入删除的有权图核值维护算法并提出了k边集以及k偏向插入边集和k偏向删除边集的结构，一组边集的插入/删除可以划分为相应多组k边集和k偏向插入/删除边集。通过理论证明表明，同组边集的插入/删除后，有权核值可能发生变化的顶点的有权核值范围仍然可以确定且变化的范围有界。通过边集的划分，同组的边集可以同时处理，相较于单边插入/删除核值维护算法减少了重复计算以及迭代次数，提升了算法的效率。
在真实数据集以及时序图上的大量实验表明，核值维护算法可以有效地对核值进行更新，且基于分组的多边核值维护算法相对于单边插入删除核值维护算法具有更高效的特点，算法的高可扩展性也在实验中得到验证。有权图核值分解及维护算法可以很好对有权网络中的个体重要性进行判定。
为了解决上述场景的问题，定义了应对点带权重场景的有权图核值，相较于无权图，图中的每个节点的权重都将被考虑。无权图可以看作是有权图每个节点权重为1的特殊情况。有权图的核值分解算法通过定义有权度，逐步的删除有权度最低的顶点以及相连接的边并为各个点分配了核值。
为应用于现实中动态图的场景，提出了有权图的单边插入删除核值维护算法。通过理论证明表明，当一条边插入或删除时，有权核值可能发生变化的顶点的有权核值范围确定且变化的范围有界，以此实现核值的更新。现实中的网络往往是多条边同时变化的，为了解决单边插入删除核值维护算法的局限性，提出了多边插入删除的有权图核值维护算法并提出了k边集以及k偏向插入边集和k偏向删除边集的结构，一组边集的插入/删除可以划分为相应多组k边集和k偏向插入/删除边集。通过理论证明表明，同组边集的插入/删除后，有权核值可能发生变化的顶点的有权核值范围仍然可以确定且变化的范围有界。通过边集的划分，同组的边集可以同时处理，相较于单边插入/删除核值维护算法减少了重复计算以及迭代次数，提升了算法的效率。
在真实数据集以及时序图上的大量实验表明，核值维护算法可以有效地对核值进行更新，且基于分组的多边核值维护算法相对于单边插入删除核值维护算法具有更高效的特点，算法的高可扩展性也在实验中得到验证。有权图核值分解及维护算法可以很好对有权网络中的个体重要性进行判定。