A Local Algorithm for Structure-Preserving Graph Cut
A Local Algorithm for Structure-Preserving Graph Cut
复制标题
DOI：
10.1145/3097983.3098015
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Dawei Zhou;Si Zhang;M. Yildirim;S. Alcorn;Hanghang Tong;H. Davulcu;Jingrui He
中科院分区：
文献类型：
--
作者：
Dawei Zhou;Si Zhang;M. Yildirim;S. Alcorn;Hanghang Tong;H. Davulcu;Jingrui He
如今，大规模图数据正在各种现实世界的应用中生成，从社交网络到合著网络，从蛋白质-蛋白质相互作用网络到道路交通网络。现有的许多图挖掘工作都是以一阶马尔可夫链为基础模型，对图的顶点和边进行挖掘。他们未能探索高阶网络结构，这在许多高影响力领域中至关重要。例如，在银行客户个人可识别信息（PII）网络中，星星结构通常对应于一组合成身份;在金融交易网络中，环结构可以指示洗钱的存在。在本文中，我们专注于挖掘用户指定的高阶网络结构，并旨在找到一个结构丰富的子图，不打破许多这样的结构分离的子图。与寻找结构丰富的子图相关的一个关键挑战是令人望而却步的计算成本。为了解决这个问题，灵感来自家庭的本地图聚类算法，有效地识别低电导切割，而不探索整个图形，我们提出了概括的关键思想，以建模高阶网络结构。特别地，我们从高阶电导的一般定义开始，并定义了高阶扩散核，其基于由用户指定的高阶网络结构诱导的高阶随机游走。然后，我们提出了一种新的高阶保结构LOcal割（HOSPLOC）算法，它运行在多对数时间在图中的边的数量。该算法从一个种子顶点开始，迭代搜索其邻域，直到找到一个高阶电导小的子图，并从有效性和效率两个方面分析了该算法的性能。在合成图和真实的图上的实验结果证明了该算法的有效性和高效性。
Nowadays, large-scale graph data is being generated in a variety of real-world applications, from social networks to co-authorship networks, from protein-protein interaction networks to road traffic networks. Many existing works on graph mining focus on the vertices and edges, with the first-order Markov chain as the underlying model. They fail to explore the high-order network structures, which are of key importance in many high impact domains. For example, in bank customer personally identifiable information (PII) networks, the star structures often correspond to a set of synthetic identities; in financial transaction networks, the loop structures may indicate the existence of money laundering. In this paper, we focus on mining user-specified high-order network structures and aim to find a structure-rich subgraph which does not break many such structures by separating the subgraph from the rest. A key challenge associated with finding a structure-rich subgraph is the prohibitive computational cost. To address this problem, inspired by the family of local graph clustering algorithms for efficiently identifying a low-conductance cut without exploring the entire graph, we propose to generalize the key idea to model high-order network structures. In particular, we start with a generic definition of high-order conductance, and define the high-order diffusion core, which is based on a high-order random walk induced by user-specified high-order network structure. Then we propose a novel High-Order Structure-Preserving LOcal Cut (HOSPLOC) algorithm, which runs in polylogarithmic time with respect to the number of edges in the graph. It starts with a seed vertex and iteratively explores its neighborhood until a subgraph with a small high-order conductance is found. Furthermore, we analyze its performance in terms of both effectiveness and efficiency. The experimental results on both synthetic graphs and real graphs demonstrate the effectiveness and efficiency of our proposed HOSPLOC algorithm.