Characterizing and Utilizing the Interplay Between Core and Truss Decompositions
Characterizing and Utilizing the Interplay Between Core and Truss Decompositions
复制标题
DOI：
10.1109/bigdata50022.2020.9378497
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Penghang Liu;Ahmet Erdem Sarıyüce
中科院分区：
文献类型：
--
作者：
Penghang Liu;Ahmet Erdem Sarıyüce
求图的稠密区域是网络分析中的一个重要问题。核心分解和桁架分解从两个不同的角度解决这个问题。前者是一个顶点驱动的方法，分配密度指标的顶点，而后者是一个边缘驱动的技术，把密度量词的边缘。尽管这两种方法之间的算法相似，但尚不清楚网络中的核心分解和桁架分解是如何相关的。在这项工作中，我们介绍了顶点相互作用（VI）和边缘相互作用（EI）图来表征核心和桁架分解之间的相互作用。根据我们的观察，我们设计的核心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.