Temporal Ordered Clustering in Dynamic Networks: Unsupervised and Semi-Supervised Learning Algorithms
Temporal Ordered Clustering in Dynamic Networks: Unsupervised and Semi-Supervised Learning Algorithms
复制标题
DOI：
10.1109/tnse.2021.3058376
复制
发表时间：
2019-05
影响因子：
6.6
通讯作者：
K. Turowski;J. Sreedharan;W. Szpankowski
中科院分区：
文献类型：
--
作者：
K. Turowski;J. Sreedharan;W. Szpankowski
在时序聚类中，给定动态网络的单个快照，其中节点在不同的时刻到达，我们的目标是将其节点划分为$K$个有序簇$\mathcal {C}_1 \prec \cdots \prec \mathcal {C}_K$，使得对于$i，簇$\mathcal {C}_i$中的节点在簇$\mathcal {C}_j$中的节点之前到达，其中$K$是数据驱动的参数，并且预先未知。这样的问题在许多应用中具有相当大的意义，从跟踪假新闻的扩展到绘制信息传播的地图。我们首先将我们的问题公式化为一般动态图，并提出一个整数规划框架，该框架找到最佳聚类，表示为严格偏序集，实现最佳精度（即，成功排序的节点对的分数）对于固定密度（即，可比较节点对的分数）。然后，我们开发了一个顺序的重要性程序和设计无监督和半监督算法，以找到时间有序的集群，有效地接近最优解。为了说明这些技术，我们将我们的方法应用于顶点复制（复制-发散）模型，与其他网络模型相比，该模型在推断集群方面表现出一些边缘情况的挑战。最后，我们验证了所提出的算法在合成和真实世界的网络上的性能。
In temporal ordered clustering, given a single snapshot of a dynamic network in which nodes arrive at distinct time instants, we aim at partitioning its nodes into $K$ ordered clusters $\mathcal {C}_1 \prec \cdots \prec \mathcal {C}_K$ such that for $i, nodes in cluster $\mathcal {C}_i$ arrived before nodes in cluster $\mathcal {C}_j$, with $K$ being a data-driven parameter and not known upfront. Such a problem is of considerable significance in many applications ranging from tracking the expansion of fake news to mapping the spread of information. We first formulate our problem for a general dynamic graph, and propose an integer programming framework that finds the optimal clustering, represented as a strict partial order set, achieving the best precision (i.e., fraction of successfully ordered node pairs) for a fixed density (i.e., fraction of comparable node pairs). We then develop a sequential importance procedure and design unsupervised and semi-supervised algorithms to find temporal ordered clusters that efficiently approximate the optimal solution. To illustrate the techniques, we apply our methods to the vertex copying (duplication-divergence) model which exhibits some edge-case challenges in inferring the clusters as compared to other network models. Finally, we validate the performance of the proposed algorithms on synthetic and real-world networks.