Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts
Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts
复制标题
DOI：
10.1007/s11590-015-0971-7
复制
发表时间：
2018-12-01
影响因子：
1.6
通讯作者：
Balasundaram, Balabhaskar
中科院分区：
文献类型：
--
作者：
Moradi, Esmaeel;Balasundaram, Balabhaskar
低直径聚类检测是一种重要的基于图的数据挖掘技术，广泛应用于社会网络分析、生物信息学和文本挖掘等领域。集群内的低成对距离可以促进集群中的顶点之间的快速通信或良好的可达性。形式上，导出直径至多为k的子图的顶点子集称为k-俱乐部。对于参数k的低值，该模型提供了团模型的图论松弛，其形式化了低直径簇的概念。使用图分解和模型分解技术的组合，我们演示了如何找到一个最大大小的k俱乐部的基本优化问题可以解决最佳的大规模的基准实例，可在公共领域。我们的方法避免了使用复杂的配方的最大k俱乐部的问题，有利于一个简单的放松的必要条件的基础上，结合规范的超立方体切割引入巴拉斯和Jeroslow。
Detecting low-diameter clusters is an important graph-based data mining technique used in social network analysis, bioinformatics and text-mining. Low pairwise distances within a cluster can facilitate fast communication or good reachability between vertices in the cluster. Formally, a subset of vertices that induce a subgraph of diameter at most k is called a k-club. For low values of the parameter k, this model offers a graph-theoretic relaxation of the clique model that formalizes the notion of a low-diameter cluster. Using a combination of graph decomposition and model decomposition techniques, we demonstrate how the fundamental optimization problem of finding a maximum size k-club can be solved optimally on large-scale benchmark instances that are available in the public domain. Our approach circumvents the use of complicated formulations of the maximum k-club problem in favor of a simple relaxation based on necessary conditions, combined with canonical hypercube cuts introduced by Balas and Jeroslow.