期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 66, 期 5, 页码 3065-3078出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2019.2940246
关键词
Correlation clustering; network motif; hypergraph; graph clustering
资金
- NSF [CIF 1218764, CIF 1117980, 1339388]
- STC Class 2010 [CCF 0939370]
- IC Postdoctoral Research Fellowship
- Direct For Biological Sciences
- Division Of Integrative Organismal Systems [1339388] Funding Source: National Science Foundation
Motivated by applications in social and biological network analysis we introduce a new form of agnostic clustering termed motif correlation clustering, which aims to minimize the cost of clustering errors associated with both edges and higher-order network structures. The problem may be succinctly described as follows: Given a complete graph $G$ , partition the vertices of the graph so that certain predetermined important subgraphs mostly lie within the same cluster, while less relevant subgraphs are allowed to lie across clusters. Our contributions are as follows: We first introduce several variants of motif correlation clustering and then show that these clustering problems are NP-hard. We then proceed to describe polynomial-time clustering algorithms that provide constant approximation guarantees for the problems at hand. Despite following the frequently used LP relaxation and rounding procedure, the algorithms involve a sophisticated and carefully designed neighborhood growing step that combines information about both edges and motifs. We conclude with several examples illustrating the performance of the developed algorithms on synthetic and real networks.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据