• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Computer and Information Sciences(ISCIS 2005); 20051026-28; Istanbul(TR) >Computing Communities in Large Networks Using Random Walks
【24h】

Computing Communities in Large Networks Using Random Walks

机译：使用随机游走计算大型网络中的社区

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Dense subgraphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Computing them however is generally expensive. We propose here a measure of similarities between vertices based on random walks which has several important advantages: it captures well the community structure in a network, it can be computed efficiently, it works at various scales, and it can be used in an agglomerative algorithm to compute efficiently the community structure of a network. We propose such an algorithm which runs in time O(mn~2) and space O(n~2) in the worst case, and in time O(n~2 log n) and space O(n~2) in most real-world cases (n and m are respectively the number of vertices and edges in the input graph).
机译：稀疏图（社区）的密集子图出现在大多数现实世界的复杂网络中，在许多情况下都起着重要作用。但是，计算它们通常很昂贵。我们在这里提出一种基于随机游走的顶点之间相似度的度量，该度量具有几个重要的优点：它可以很好地捕获网络中的社区结构，可以高效地进行计算，可以在各种规模下运行，并且可以在凝聚算法中使用有效地计算网络的社区结构。我们提出了一种在最坏的情况下在时间O（mn〜2）和空间O（n〜2）以及在最真实的情况下在时间O（n〜2 log n）和空间O（n〜2）中运行的算法-world案例（n和m分别是输入图中顶点和边的数量）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号