论文标题
表征和利用核心和桁架分解之间的相互作用
Characterizing and Utilizing the Interplay Between Core and Truss Decompositions
论文作者
论文摘要
在图中找到密集区域是网络分析中的重要问题。核心分解和桁架分解从两个不同的角度解决了这个问题。前者是一种顶点驱动的方法，该方法为顶点分配密度指标，而后者是一种将密度量化器放在边缘的边缘驱动技术。尽管这两种方法之间存在算法相似性，但尚不清楚网络中的核心和桁架分解是如何相关的。在这项工作中，我们介绍了顶点相互作用（VI）和边缘相互作用（EI）图，以表征核心和桁架分解之间的相互作用。根据我们的观察结果，我们设计了Core-TrussDD，这是一种异常检测算法，以识别核心分解和桁架分解之间的差异。我们分析了大量多样的现实世界网络，并演示我们的方法如何成为表征网络中模式和异常的有效工具。通过VI和EI图，我们观察到来自不同领域的图形的不同行为，并确定了由特定现实世界结构驱动的两种异常行为。我们的算法提供了一个有效的解决方案来检索网络中的异常值，这与两种异常行为相对应。我们认为，研究核心和桁架分解之间的相互作用很重要，并且可以就现实世界网络的密集子图结构产生令人惊讶的见解。
Finding the dense regions in a graph is an important problem in network analysis. Core decomposition and truss decomposition address this problem from two different perspectives. The former is a vertex-driven approach that assigns density indicators for vertices whereas the latter is an edge-driven technique that put density quantifiers on edges. Despite the algorithmic similarity between these two approaches, it is not clear how core and truss decompositions in a network are related. In this work, we introduce the vertex interplay (VI) and edge interplay (EI) plots to characterize the interplay between core and truss decompositions. Based on our observations, we devise CORE-TRUSSDD, an anomaly detection algorithm to identify the discrepancies between core and truss decompositions. We analyze a large and diverse set of real-world networks, and demonstrate how our approaches can be effective tools to characterize the patterns and anomalies in the networks. Through VI and EI plots, we observe distinct behaviors for graphs from different domains, and identify two anomalous behaviors driven by specific real-world structures. Our algorithm provides an efficient solution to retrieve the outliers in the networks, which correspond to the two anomalous behaviors. We believe that investigating the interplay between core and truss decompositions is important and can yield surprising insights regarding the dense subgraph structure of real-world networks.
