06-社会网络分析与算法研究

《06-社会网络分析与算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、复杂网络中的搜索问题6.1引言搜索算法的研究是复杂网络研究中的一项重要内容。复杂网络中的搜索有着大量的实际应用：包括社会网络中两个人之间的最短关系链寻找、WWW中网页的搜索、P2P（Peer-to-Peer）网络中指定文件或数据的搜索及任意两个城市之间的最短路径的寻找等等。本章首先介绍三种经典的搜索策略，即广度优先搜索算法、随机行走搜索算法和最大度搜索算法，然后介绍社会网络的快速分散式搜索问题，最后介绍P2P网络和WWW网络的搜索问题。6.2广度优先搜索算法6.2.1复杂网络搜索问题6.2.2广度优先搜索策略6.2.3广度优先搜索算法实

2、现6.2.4广度优先搜索算法的应用和特性6.2.1复杂网络搜索问题复杂网络搜索策略通常用一个消息传递的过程来描述。从一个给定的源节点开始，为了寻找所需要的信息，按照一定的规则向它的一个或多个邻居传递查询消息。如果收到查询的邻居节点上不含有源节点所需的信息，那么这些邻居节点再将查询传递给它们各自的邻居，重复这个过程直到存储着指定信息的目标节点被寻找到为止，然后目标节点将信息传递给源节点。网络的小世界特性表明，只要在规则网络的基础上引入少量的随机长程连接，网络中任意两个节点之间的距离就会变得很小，这在一定程度上有利于对网络中的资源进行搜索。6.

3、2.1复杂网络搜索问题一般而言，网络的小世界特性并不一定意味着网络是可以快速搜索的。在一个大规模的网络中，连接两个节点之间的路径可能有很多条，网络中的一个节点是否能找到它与任一其它节点之间的较短甚至最短的路径，依赖于节点所了解的局部网络结构信息、节点所使用的搜索算法和整个网络的实际结构。现实网络通常都相当复杂，例如针对WWW、Internet、P2P等大规模网络，不可能获得网络的全局信息。节点往往只能利用一些诸如邻居节点的相关信息或者邻居的邻居的节点信息等局部信息来进行搜索，寻找到最短路径或者接近于最短路径的较短路径。因此对局部搜索策略的研究具

4、有重要意义。6.2.2广度优先搜索策略在许多实际网络中，单个节点无法充分掌握整个网络的全局结构，甚至可能不知道目标节点在网络中的位置。一个最简单的搜索策略就是广度搜索（broadcastsearch）策略，也就是广度优先搜索（broadthfirstsearch，BFS）算法，也叫宽度优先搜索，或横向优先搜索。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。6.2.2广度优先搜索策略当源节点s应用BFS策略在网络中的节点上寻找指定的文件时，s首先查询其所有的邻居节点，询问是否含有目标文件，如果s的邻

5、居中有某个节点存储了目标文件，则将目标文件返回给源节点；如果任何邻居都没有含有目标文件，则所有的邻居将查询继续传递给各自的邻居节点，一直到搜索到目标文件为止。当源节点s利用BFS策略搜索目标节点t时，s首先判断自己的邻居节点中有无目标节点。若有，则中止搜索；若无，则向每个邻居查询它们的邻居节点中有无目标节点。重复这个过程一直到寻找到目标节点的任一个邻居为止。6.2.3广度优先搜索算法实现已知图G＝（V，E）和一个源节点s，广度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有节点，并计算s到所有这些节点的距离（最少边数），该算法同

6、时能生成一棵根为s且包括所有可达节点的广度优先树。对从s可达的任意节点v，广度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。之所以称之为广度优先算法，是因为算法自始至终一直通过已找到节点和未找到节点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有节点，然后再去搜索和s距离为k+1的其他节点。6.2.4广度优先搜索算法的应用和特性1．应用广度优先搜索算法可以用来解决图论中的许多问题，例如：（1）寻找图中所有连通分支（connectedcomponent）。这里，连通分支是图

7、中的最大连通子图。（2）寻找连通分支中的所有节点。（3）寻找非加权图中任两点的最短路径。（4）测试一个图是否为二分图（所谓二分图，是指节点可以分成两个不相交的集合使得在同一个集内的节点不相邻（没有共同边）的图）。（5）BFS还可以用来解决电脑游戏中寻找路径的问题。6.2.4广度优先搜索算法的应用和特性2．特性BFS的空间复杂度为O（M＋N）。由于对空间的大量需求，因此BFS并不适合求解网络规模非常大的问题。在最差情形下，BFS需要寻找到所有可能节点的所有路径，从而产生大量的查询信息流量，造成网络流量急剧上升而导致网络拥塞。广度优先搜索算法具有完

8、全性。若所有边的权值相等，广度优先搜索算法能找到最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少。但对一般的图