• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Sequential importance sampling and message-passing algorithms: A new class of efficient methods for large-scale networks.
【24h】

Sequential importance sampling and message-passing algorithms: A new class of efficient methods for large-scale networks.

机译：顺序重要性采样和消息传递算法：大型网络的新型高效方法。

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

摘要

Large-scale complex networks have been the objects of study for the past two decades, and two problems have been the main focus: constructing or designing realistic models for large-scale networks and making statistical inferences in such networks. These problems appear in a variety of research areas including coding theory, combinatorial optimization, and biological systems. This thesis explains the use of the techniques Sequential Importance Sampling (SIS) and Belief Propagation (BP) for designing and making inferences in large-scale networks.; This manuscript starts with an algorithm for designing random graphs that is an important tool in simulating protocols on Internet topology and detecting motifs in genetic networks. Unfortunately, the existing algorithms for this problem have large running times, making them impractical to use for networks with thousands of vertices. Our approach is based on SIS that has been recently introduced as a successful heuristic for counting graphs. We analyze validity of SIS and obtain the fastest algorithm for generating random graphs with given degree sequences.; The second portion of this thesis will be about a mysterious message-passing algorithm called Belief Propagation (BP). Despite spectacular success of the BP in inference on large-scale networks, theoretical results concerning the correctness and convergence of the method are known only in few cases. We will prove correctness and convergence of the BP for finding maximum weight matching in bipartite graphs. This also yields a simple and distributed algorithm and offers the possibility of implementation in hardware for scheduling in high speed routers.
机译：在过去的二十年中，大型复杂网络一直是研究的对象，而两个主要问题一直是关注的焦点：为大型网络构建或设计现实模型以及在此类网络中进行统计推断。这些问题出现在各种研究领域，包括编码理论，组合优化和生物系统。本文说明了在大型网络中设计和进行推理时使用顺序重要性抽样（SIS）和信念传播（BP）技术的方法。该手稿从设计随机图的算法开始，该算法是模拟Internet拓扑协议和检测遗传网络中的图案的重要工具。不幸的是，用于该问题的现有算法具有较大的运行时间，从而使其不适用于具有数千个顶点的网络。我们的方法基于SIS，SIS是最近成功引入的一种用于对图形进行计数的启发式方法。我们分析了SIS的有效性，并获得了生成具有给定度数序列的随机图的最快算法。本文的第二部分将介绍一种称为信度传播（BP）的神秘消息传递算法。尽管BP在大规模网络推理方面取得了惊人的成功，但有关该方法的正确性和收敛性的理论结果仅在少数情况下才为人所知。我们将证明BP的正确性和收敛性，以便在二部图中找到最大的权重匹配。这也产生了一种简单的分布式算法，并提供了在硬件中实现高速路由器中调度的可能性。

著录项

  • 作者

    Bayati, Mohsen.;

  • 作者单位

    Stanford University.;

  • 授予单位 Stanford University.;
  • 学科 Statistics.; Engineering Electronics and Electrical.; Computer Science.
  • 学位 Ph.D.
  • 年度 2007
  • 页码 125 p.
  • 总页数 125
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号