基于MCMC技术的社会网络搜索

VIP免费

3.0 牛悦 2024-11-19 5 4 1.2MB 55 页 15积分

侵权投诉

摘要

复杂网络中的搜索有着大量的实际应用，包括万维网中网页的搜索、P2P网络

中指定文件或数据的搜索、任意两个城市之间的最短路径的寻找等等。在复杂网

络中如果每个节点都知道网络的全局连接信息，也就是说，每个节点都知道怎样

在最小的步数内到达其它节点，这是最优的一种搜索情况。但是，现实中的网络

通常都相当复杂。人们很难像在交通网中一样用一张地图标出所有节点之间的连

接关系，节点往往只能利用一些诸如邻居节点的相关信息或者邻居的邻居的节点

的信息等局部信息来进行搜索，因此对局部搜索策略的研究具有重要的意义。

自从复杂网络的小世界与无标度特性被发现以来，许多研究者开始从网络拓

扑结构角度出发提出一些新的搜索策略或算法，并研究搜索效率与网络拓扑结构

的关系。

论文首先给出了复杂网络的简单介绍，并对社会网络中的搜索这一课题的研

究现状作了归纳与总结。重点研究了不带有坐标信息的长程连接图，使它符合

Kleinberg模型以使得贪婪搜索成为可能。论文主要贡献如下：

1. 给出了MCMC算法，它将Kleinberg式的连接图嵌入到一维或二维格子上。可在

连接图上进行贪婪搜索，不用考虑生成图时节点的初始位置。

2. 给出和仿真了两种算法停止标准，用以比较不同节点选择方法的效率。一个

是跟过程相关的性能提升率的界限，另一个是理想模型的界限。

3. 给出两个局域选择方法，加快MCMC算法收敛速度。局域指的是方法跟节点在

格子上的邻居的位置相关。

4. 多节点交换技术。在马尔科夫链的每一步考虑更多的对等节点和位置分配。

将该方法和其它方法作表较。

主要结论是在只考虑长程连接不考虑底图格子上的邻接关系的重叠网上可以

实现搜索。局域选择方法比均匀随机选择方法更快地达到停止标准。如果仅考虑

链的迭代次数，多节点交换也能提高收敛速度，但效果不如局域两节点方法。

关键词：社会网络蒙特卡罗方法小世界网络贪婪搜索

ABSTRACT

The problem of searching in complex networks has a large number of practical

applications, such as searching webpage in WWW, searching desired files or data in

P2P network, finding shortest path between two cities, etc. If the global knowledge of

the network is available, i.e., every vertex knows how to reach any other vertex in the

minimum number of steps, then one is in the best position to perform a search. However,

many real networks are quite complex and it is not possible to draw a map to show the

interconnected information between every pair of vertices as in traffic networks. In

other words, search strategies should be based only on the local information such as the

identities and degree of their neighbors and their neighbors’ neighbors. Therefore, the

investigation of local search strategies is of great importance.

Since the discovery of small-world and scale-free features of complex networks,

researchers have proposed some new search strategies by taking into account the

topologies of complex networks. Furthermore, the relationship between efficiency of

search strategies and topologies of complex networks has been widely studied.

In this thesis, we first briefly introduce some basic concepts of complex networks,

and review the recent research developments on search in social network. Then we

focus on graphs with only shortcut edges and no local connections in the lattice. We

attempt to fit it against Kleinberg’s model so as to make efficient searches possible. We

summarize our contributions as follows:

1. We give an MCMC algorithm to generate an embedding of a given graph into a one

or two dimensional grid which is tuned to the distributions of Kleinberg’s model.

2. We state and simulate two stop criteria to be used for comparing the efficiency of

different selection methods further on. The first criteria relates to how fast the

method improves the actual solution, the second criteria can be used when we

know the ideal performance.

3. We propose two different selection methods for improving the converging rate of

the algorithm. we call this approach local selection since they relate to the

positions that graph neighbors take in the lattice

4. We try a different approach: not selecting switching peers as a goal, but instead by

including more peers (more configurations available in each step) for the switch in

III

each step of the Markov chain. We then try to compare the methods against each

other.

The main result is that it’s possible to make an overlay graph with only shortcut

edges and no local connections in the lattice navigable. our two local selection methods

reach the performance at the stop criteria faster than selecting nodes uniformly random

does. Involving more nodes also indicates that there is some improvement in doing this

if one considers steps of the chain, but that a directed switch gives more improvement

than only increasing the number of nodes involved.

Key Words：Social networks，Monte-Carlo algorithm，Small world，

Greedy routing

中文摘要

ABSTRACT

第一章绪论 .........................................................1

§ 1.1 网络发展简介及研究意义 .................................... 1

§1.2 复杂网络拓扑模型 ............................................ 3

§1.2.1 规则网络模型 .......................................... 3

§1.2.2 ER 随机图 ............................................. 4

§1.2.3 小世界网络模型 ........................................ 5

§1.2.4 无标度网络模型[2] ....................................... 5

§1.3 本文主要工作 ............................................... 6

第二章社会网络中的搜索概述 ..........................................8

§2.1 社会网络中搜索的著名实验 .................................... 8

§2.1.1 Milgram 和六度分离 .................................... 8

§2.1.2 Kevin Bacon 游戏(Kevin Bacon Game) .................... 9

§2.1.3 Erdös 数（Erdös Number） .............................. 9

§2.1.4 哥伦比亚大学的“小世界项目” ......................... 10

§2.2 社会网络中搜索的研究 ....................................... 11

§2.2.1 Kleinberg 提出的网格模型 ............................. 11

§2.2.2 Watts 等提出的层次树结构网络模型 ..................... 14

§2.2.3 社会网络如何成为可以实现快速搜索的网络 ............... 18

第三章基于 MCMC 技术的社会网络搜索 ..................................22

§3.1 马尔科夫链蒙特卡洛（MCMC）方法 ............................. 22

§3.1.1 Metropolis-Hastings 算法 ............................. 23

§3.1.2 在节点位置上运用 MCMC 算法 ............................ 23

§3.2 对 MCMC 方法的计算机模拟 ................................... 24

§3.2.1 一维格子的情况 ....................................... 24

§3.2.2 二维格子的情况 ....................................... 25

§3.2.3 社会网络数据 ......................................... 25

§3.3 模拟结果分析 .............................................. 25

§3.3.1 一维格子的情况 ....................................... 25

§3.3.2 二维格子的情况 ....................................... 28

§3.3.3 社会网络数据 ......................................... 29

第四章算法的性能和收敛速度 .........................................31

§4.1 性能的度量 ................................................. 31

§4.2 性能的评价 ................................................. 31

§4.3 Metropolis-Hastings 算法的收敛速度 ......................... 33

§4.3.1 位置交换建议的作用 ................................... 33

§4.3.2 算法的停止标准 ....................................... 34

§4.3.3 收敛速度的计算机模拟 ................................. 34

§4.3.4 提出的问题 ........................................... 35

第五章改进的 MH 算法 ................................................ 38

§5.1 改进的思想 ................................................. 38

§5.2 Metropolis-Hastings 算法的改进 ............................. 38

§5.2.1 正态方法 ............................................. 39

§5.2.2 混合方法 ............................................. 40

§5.2.3 改进方法的计算机模拟 ................................. 41

§5.3 算法的均匀多节点交换法改进 ................................ 44

§5.3.1 均匀三节点交换 ....................................... 45

§5.3.2 多节点交换的计算机模拟 ............................... 45

第六章结论 .........................................................47

参考文献 ............................................................ 48

在读期间公开发表的论文 ..............................................51

致谢 ............................................................. 52

第一章绪论

§ 1.1 网络发展简介及研究意义

近年来，复杂网络引起了许多相关领域研究人员的关注。所谓复杂网络就是

具有复杂拓扑结构和动力行为的大规模网络。它是由大量的节点通过边的相互连

接而构成的图。在我们的现实生活中充满着各种各样的复杂网络，如 Internet、

万维网、电力网络、交通网络、食物链网络、科研合作网络、社会关系网络等等。

网络化是今后若干年许多研究领域发展的一个主流方向，因此复杂网络的研究显

得越来越重要。

复杂网络研究的兴起使得人们开始广泛关注网络结构复杂性及其与网络行为

之间的关系。要研究各种不同的复杂网络在结构上的共性，首先需要有一种描述

网络的统一的工具。这种工具在数学上称为图（Graph）。1736 年欧拉对七桥问题

的抽象和论证思想，开创了数学中的一个分支——图论的研究。

在图论发展的最初的一百多年里，科学家们认为真实系统各因素之间的关系

可以用一些规则的结构表示，例如二维平面上的欧几里得格子或者最近邻耦合网

络等等。到了 20 世纪 60 年代，两位匈牙利数学家 Erdös 和 Rényi 建立了被公认

为是开创了复杂网络理论的系统性研究的随机图理论，在他们的随机图模型中两

个节点之间连边与否不再是确定的事情，而是根据一个概率决定[8]。这样生成的网

络叫做随机网络，它在接下来的四十年里一直被认为是描述真实系统最好的网络，

但绝大多数实际的复杂网络结构并不是完全随机的，例如，两个人之间是否是朋

友、Internet 中两个路由器之间是否有光纤连接、万维网上两个页面之间是否有

超文本链接、两个城市之间是否有直接相连的高速公路等都不会是完全靠抛硬币

来决定的。

在 20 世纪即将结束之际，随着数据库容量的持续增加以及计算机存储和操作

能力的增强，人们对复杂网络的科学探索发生了重要的转变，尤其是对于万维网

和 Internet 的图形化处理，为研究大规模复杂网络的拓扑结构提供了第一次机会。

逐渐地，研究者们开展了用图对社会科学、基础系统以及生物学中的许多网络的

研究。此时的研究开始用系统的眼光来看待这些巨大的数据集合，试图寻找这些

复杂系统的演化和动力学背后的规律和模式。的确，当研究复杂网络的结构时就

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

I摘要复杂网络中的搜索有着大量的实际应用，包括万维网中网页的搜索、P2P网络中指定文件或数据的搜索、任意两个城市之间的最短路径的寻找等等。在复杂网络中如果每个节点都知道网络的全局连接信息，也就是说，每个节点都知道怎样在最小的步数内到达其它节点，这是最优的一种搜索情况。但是，现实中的网络通常都相当复杂。人们很难像在交通网中一样用一张地图标出所有节点之间的连接关系，节点往往只能利用一些诸如邻居节点的相关信息或者邻居的邻居的节点的信息等局部信息来进行搜索，因此对局部搜索策略的研究具有重要的意义。自从复杂网络的小世界与无标度特性被发现以来，许多研究者开始从网络拓扑结构角度出发提出一些新的搜索策略或算法...

展开>> 收起<<

基于MCMC技术的社会网络搜索.pdf

共55页,预览6页

还剩页未读，继续阅读

基于MCMC技术的社会网络搜索

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: