论文标题
边缘标签引起的密集子图
Dense subgraphs induced by edge labels
论文作者
论文摘要
在网络中找到密集连接的节点组是一种广泛使用的工具，可在图形挖掘中进行分析。寻找此类群体的一个流行选择是找到高平均程度的子图。虽然有用，但解释这种子图可能很困难。另一方面，许多现实世界网络都有其他信息，我们对带有标签的网络特别感兴趣。在本文中，我们研究了发现诱导密集子图的一组标签。我们考虑两个密度的概念：平均程度和边缘数量减去由参数$α$加权的节点的数量。有很多方法可以从一组标签中诱导子图，我们研究了两种情况：首先，我们研究了连接性诱导的致密子图，该子图边缘需要具有所有标签。其次，我们研究了析取诱导的密集子图，其中子图边缘需要至少一个标签。我们表明这两个问题都是NP-HARD。由于硬度，我们求助于贪婪的启发式方法。我们表明我们可以有效地实施贪婪的搜索：查找连接性诱导的和析取的密集子图的各自的运行时间为$ O（p \ log k）$和$ o（p \ log^2 k）$，其中$ p $是边缘 - label pairs and $ k $的数量，是$ k $的数量。我们的实验评估表明，我们可以在合成图中找到地面真理，并且可以从现实世界网络中找到可解释的子图。
Finding densely connected groups of nodes in networks is a widely used tool for analysis in graph mining. A popular choice for finding such groups is to find subgraphs with a high average degree. While useful, interpreting such subgraphs may be difficult. On the other hand, many real-world networks have additional information, and we are specifically interested in networks with labels on edges. In this paper, we study finding sets of labels that induce dense subgraphs. We consider two notions of density: average degree and the number of edges minus the number of nodes weighted by a parameter $α$. There are many ways to induce a subgraph from a set of labels, and we study two cases: First, we study conjunctive-induced dense subgraphs, where the subgraph edges need to have all labels. Secondly, we study disjunctive-induced dense subgraphs, where the subgraph edges need to have at least one label. We show that both problems are NP-hard. Because of the hardness, we resort to greedy heuristics. We show that we can implement the greedy search efficiently: the respective running times for finding conjunctive-induced and disjunctive-induced dense subgraphs are in $O(p \log k)$ and $O(p \log^2 k)$, where $p$ is the number of edge-label pairs and $k$ is the number of labels. Our experimental evaluation demonstrates that we can find the ground truth in synthetic graphs and that we can find interpretable subgraphs from real-world networks.
