标题： 密集子图发现与强三元闭包相结合 显示英文标题

标题： Dense Subgraph Discovery Meets Strong Triadic Closure

摘要： 寻找密集子图是一个核心问题，具有许多图挖掘应用，如社交网络中的社区检测和异常检测。 然而，在许多现实世界的网络中，连接并不相等。 一种将边标记为强边或弱边的方法是使用强三元闭包（STC）。 在此，如果一个节点与另外两个节点有强连接，那么那两个节点至少应有一条弱边连接。 STC标记不是唯一的，找到最大数量的强边是NP难的。 在本文中，我们将STC应用于密集子图发现。 更正式地说，我们对给定子图的评分是强边和弱边数量之和，由用户参数$\lambda$加权，与子图的节点数的比值。 我们的目标是找到一个子图和一个STC标记，使评分最大化。 我们证明，对于$\lambda = 1$，我们的问题等价于寻找最密集的子图，而对于$\lambda = 0$，我们的问题等价于寻找最大的团，使我们的问题NP难。 我们提出了一种基于整数线性规划的精确算法和四种实际的多项式时间启发式算法。 我们进行了一项广泛的实验研究，结果表明，我们的算法可以在合成数据集中找到真实情况，并在现实世界数据集中高效运行。 显示英文摘要

摘要： Finding dense subgraphs is a core problem with numerous graph mining applications such as community detection in social networks and anomaly detection. However, in many real-world networks connections are not equal. One way to label edges as either strong or weak is to use strong triadic closure~(STC). Here, if one node connects strongly with two other nodes, then those two nodes should be connected at least with a weak edge. STC-labelings are not unique and finding the maximum number of strong edges is NP-hard. In this paper, we apply STC to dense subgraph discovery. More formally, our score for a given subgraph is the ratio between the sum of the number of strong edges and weak edges, weighted by a user parameter $\lambda$, and the number of nodes of the subgraph. Our goal is to find a subgraph and an STC-labeling maximizing the score. We show that for $\lambda = 1$, our problem is equivalent to finding the densest subgraph, while for $\lambda = 0$, our problem is equivalent to finding the largest clique, making our problem NP-hard. We propose an exact algorithm based on integer linear programming and four practical polynomial-time heuristics. We present an extensive experimental study that shows that our algorithms can find the ground truth in synthetic datasets and run efficiently in real-world datasets.