...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Graph Clustering using Effective Resistance
【24h】

Graph Clustering using Effective Resistance

机译：使用有效阻力进行图聚类

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) and sufficiently large delta 1, partitions V into subsets V(1),..., V(h) for some h= 1, such that at most delta^{-1} fraction of the weights are between clusters, i.e. sum(i j) |E(V(i), V(j)| w(E)/delta and the effective resistance diameter of each of the induced subgraphs G[V(i)] is at most delta^3 times the inverse of the average weighted degree, i.e. max{ Reff(u, v) : u, v in V(i)} delta^3 · |V|/w(E) for all i = 1,..., h. In particular, it is possible to remove one percent of weight of edges of any given graph such that each of the resulting connected components has effective resistance diameter at most the inverse of the average weighted degree. Our proof is based on a new connection between effective resistance and low conductance sets. We show that if the effective resistance between two vertices u and v is large, then there must be a low conductance cut separating u from v. This implies that very mildly expanding graphs have constant effective resistance diameter. We believe that this connection could be of independent interest in algorithm design.
机译：我们设计了一个多项式时间算法，对于任何加权无向图G =（V，E，w）和足够大的 delta> 1，将V划分为子集V（1），...，V（h）并持续h> = 1，使得最多 delta ^ {-1}的权重分数在群集之间，即sum（i

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号