第28卷第10期 计算机应用 Vol.28 No.10 2008年10月 Computer Applications 0ct.2008 文章编号：1001-9081(2008)10-2600-04 基于MCMC技术的社会网络搜索 李坤朋，张 宁 (上海理工大学管理学院，上海200093) (jacklion2000@126.com) 摘要：实验和理论表明社会网络中存在着短路径，即人们可以在较少的步数内找到目标。研究了社会网络中 的贪婪搜索现象，给出了将长程连接图嵌入底层一维和二维网格的马尔科夫链蒙特卡罗方法。读方法更符合现实情 况，坐标体系只是用于网上距离的计算。将算法用于模拟数据（根据一维和二维理想模型产生的困）和真实的社会网 络数据均有很好的查询效率，查询成功率高，成功壹询平均步长短。 关键词：复杂网络：蒙特卡罗方法；小世界：贪婪搜索 中图分类号：N94:TP393 文献标志码：A Search in social networks using MCMC algorithm LI Kun-peng,ZHANG Ning (College f Management,University f Shanghai for Science and Technology.Shanghai 00093.China) Abstract:Experiments and theoretical analysis demonstrate that short path exist in social networks,and people can search a target in a few steps.Greedy routing in social networks was explored.An MCMC algorithm was given to embed a given shortcut graph into a one or two dimensional grid.This algorithm was reality-oriented and the coordinate system was used only for the computation of network distance.The algorithm was tested using artificially generated data (graphs generated according to the ideal model in one and two dimensions)as well as real social network data.The result is pretty satisfactory: the success rate of inquiry is high and the mean step length of success inquiry is short. Key words:complex network;Monte-Carlo algorithm;small world;greedy routing 的函数，是对G中节点位置的分配。d表示图上距离。E为V中 0引言 的点红成的边的集合，编号l,…,m。假定边由Kleinberg模型 小世界现象的现代概，念起源于心理学家Milgram在20 得来，则某一E出现的概率是： 世纪60年代所做的实验。该实验表明社会网络中的人们能 (1) 有效地找到到特定日的地的路径。最近的基于因特网的研 P(E1p）=Πael✉)，PrH。 究川也证实了这一点。 H。是归一常数。 能产生短直径的图模型已经出现了很长时间了，总的来 作为p的函数，式(1)就是某一分配的似然函数。由E估 说这些模型是指定一结构化的底图（如网格）然后随机加人 计p的最直接方法就是求式(1)的最大似然估计。显式求出 长程连接。Kleinberg在2000年给出一数学模型2)，第一个从 p是闲摊的，一维的情况是NP完全问题。我们用贝叶斯方 理论上解释了行效搜索是怎样产生的。他指出有效搜索依赖 法，将中视为一随机变量， 于长程连接在格子上的分布，长程连接的出现频率与距离的 P(E)=P(EL)P() (2) 平方是反比例关系时，贪婪搜索将在O(lg(n)步内找到目 P(E) 是节点位置的后验分布，根据该分布为节点分配位置。 标。 ,Kleinberg的搜紫算法里每个节点都知道自己、邻居和目 L.】Metropolis-Hastings算法 标节点的坐标。而其实的世界里不存任这种坐标，每个节点 Metropolis-Hastings算法是马尔科夫链蒙特卡罗方法领域 里有广泛应用的算法。给出集合S上的分布π，它建立S上的 只知道自己的邻房，不了解全局结构。本文问到Milgram的 以π为平稳分布的马尔科大链。算法从一个选择核：开始， 初始问题，在社会网络中寻找短路径。不考虑坐标位置，将长 a:S×S一[0,1]，它为所有状态s提供了下一时步的状态分 程连接图嵌人Kleinberg模型，使其能进行有效搜索。假设该 布。下一状态r从这一分布选择，然后以概率(s,)接受， 图是将Kleinberg的分布模型用于带坐标信息的底图产生的， 以节点在网格上的位置为未知参数，我们用马尔科夫链蒙特 (,r）=min1,Qa)如果r被接受，它成为马尔科 r(s)a(5,r） 卡洛方法来估计这一嵌人。对这一嵌人进行很好的估计，将 夫链的下一个值，否则马尔科夫链保持在状态s。如此建立的 使图上贪梦搜浆成为可能，而不用考虑节点的初始位置。 马尔科夫链以P(s,r）=a(s,)(s,)为转移概率矩阵，是不 可约的，以π为平稳分布。 1声明 1,2在节点位置上运用MCMC算法 V为节点集合，G是作为底图的k维有限点阵，中为V到G Metropolis-Hastings算法用于我们的问题，就是建立位置 收稿日期：2008-04-09：修回日期：2008-08-08。 作者简介：李坤朋(1981一)，男，山东荷泽人，预士研究生，主要研究方向：复杂网络：张宁(156-)，女，江苏人，副教授，主要研究方向： 复杂系统。 万方数据
第28卷第10期 2008年10月 计算机应用 、 Computer Applications V01．28 No．10 Oct．2008 文章编号：1001-9081(2008)10-2600一04 基于MCMC技术的社会网络搜索 李坤朋，张宁 (上海理工大学管理学院，上海200093) (jaeklion2000@126．oom) 摘要：实验和理论表明社会网络中存在着短路径，即人们可以在较少的步数内找到目标。研究了社会网络中 的贪婪搜索现象，给出了将长程连接图嵌入底层一维和二维网格的马尔科夫链蒙特卡罗方法。该方法更符合现实情 况。坐标体系只是用于网上距离的计算。将算法用于模拟数据(根据一维和二维理想模型产生的图)和真实的社会网 络数据均有很好的查询效率，查询成功率高，成功查询平均步长短。 关键词：复杂网络；蒙特卡罗方法；小世界；贪婪搜索 中图分类号：N94；TP393 文献标志码：A Search in social networks using MCMC algorithm LI Kun-peng，ZHANG Ning 、(College of Management，Umvers缸y of Sha甥tmi for&面珊and Tec／mo／ogy,SJI彻咖f 200093，劬f，l口) Abstract：Experiments and theoretical analysis demonstrate that short path exist in social networks，and people can search a target in a few steps．Greedy muting in social networks was explored．An MCMC algorithm WaS given to embed a siven shortcut graph into a oile or two dimensional鲥d．This algorithm was reality-oriented and the coordinate system was used only for the computation of network distance．The algorithm was tested using artificially generated data(graphs generated according to’the ideal model in one and two dimensiom)as well as real social network data．The result is pretty satisfactory： the SUCCESS rate of inquiry is hish and the meall step length of success inquiry is short． Key words：complex network；Monte—Carlo algorithm；small world；greedy muting 0 引言 小世界现象的现代概念起源于心理学家Milgram在20 世纪印年代所做的实验。该实验表明社会网络巾的人们能 有效地找到到特定目的地的路径。最近的基于因特网的研 究…也证实了这一点。 ’ 能产生短直径的图模型已经出现了很长时间了，总的来 说这些模型是指定一结构化的底图(如网格)然后随机加入 长程连接。Kleinberg在2000年给出一数学模璎旧1，第一个从 理论上解释了有效搜索是怎样产生的。他指出有效搜索依赖 于长程连接在格子上的分布，长程连接的出现频率与距离的 平方是反比例关系时，贪婪搜索将在D(1092(n))步内找到目 标。 ，Kleinberg的搜索算法里每个节点都知道自己、邻居和目 标节点的坐标。而真实的世界里不存在这种坐标，每个节点 只知道自己的邻居，不了解全局结构。本文同到Milgram的 初始问题，在社会网络中寻找短路径。不考虑坐标位置，将长 程连接图嵌入Kleinberg模型，使其能进行有效搜索。假设该 图是将Kleinberg的分布模型用于带坐标信息的底图产生的， 以节点在网格I：的位置为未知参数，我们用马尔科夫链蒙特 卡洛方法来估计这一嵌入。对这一嵌入进行很好的估计，将 使图上贪婪搜索成为可能，而不用考虑节点的初始位置。 1 声明 V为节点集合，G是作为底图的后维有限点阵，9为y到G 的函数，是对G中节点位置的分配。d表示图上距离。E为y中 的点组成的边的集合，编号l，…，m。假定边由Kleinberg模型 得来，则某一E出现的概率是： 』L l P(引彩2耳面两素了丽 a) 峨是归一常数。 作为妒的函数，式(1)就是某一分配的似然函数。由层估 计妒的最直接方法就是求式(1)的最大似然估计。显式求出 p是困难的，一维的情况是NP完全问题。我们用贝叶斯方 法，将妒视为一随机变量， P(妒I E)：耻掣 (2) 是节点位置的后验分布，根据该分布为节点分配位置。 1．1 Metropolis·Hastings算法 Metropolis．Hastings算法是马尔科夫链蒙特卡罗方法领域 里有广泛应用的算法。给出集合S上的分布7r，它建它s上的 以fir为平稳分布的马尔科大链。算法从一个选择核Ⅱ开始， a：S×S一[0，1]，它为所有状态s提供了下一时步的状态分 布。下一状态r从这一分布选择，然后以概率口(s，r)接受， 卢(s，r)=min 1，袭渊)。如果r被接受，它成为马尔科 夫链的下一个值，否则马尔科夫链保持在状态s。如此建它的 马尔科夫链以P(s，r)=a(s，r)lBCs，r)为转移概率矩阵，是不 可约的，以仃为平稳分布。 1．2在节点位置上运用MCMC算法 Metropolis—Hastings算法用于我们的问题，就是建立位置 收稿日期：2008一04—09；修回日期：2008—08—08。 作者简介：李坤朋(1981一)。男，山东菏泽人，硕上研究生，主要研究方向：复杂网络；张宁(1956一)，女，江苏人，副教授，主要研究方向： 复杂系统。 。 万方数据
第10期 李坤朋等：基于MCMC技术的社会网络搜索 2601 函数集合S=G上的马尔科夫链，链的平稳分布是式(2)。 性有什么影响。 设《是S上的选择核，服从均匀分布，从p,选择得2，令 2.3真实的数据 a(1p2) =a(,m,),则B(p1,9）=min 将算法用于真实的社会网络，该网络由电子邮件加密工 P(EI （,pelp ）=mim(1,i de(),p(y:) dp(x),9(y) 。如果 具PGP的用户组成。为了确保邮件发送和接收者的真实性， PGP有一个密钥机制。用户只有面对面接触才能保证密钥的 p(x)=p(y）,9(y）=(x),m(z)=9(),≠x,y 真实性，所以他们是熟人关系。由一个节点开始递归生成该 称p为x,y可交换，这种情祝下上式化为(p,P2)=min 网络。令G,是第n步的图： dp1(),p(y:) 1,》 1)G,为节点集合，它们不在G。中，但与G,中至少一个 ）,E(xUy)表示连接x或y 节点有边相连。 的边。 2)从Gn选择节点x,它有最多的边进人G,。 接下来是找到选择核，最直接的方法是随机选取x和y, 3)令C1为G。和x组成的图。 使m9为x,y可交换，即： 4)循环，到C为要求的大小为止。 a(g,m)=(a+),若y可交换 3试验结果和分析 10. 其他 这样建立的马尔科夫链以式(2)为平稳分布，无论从哪个位 3.1一维的情况 置函数出发最终都收敛于该分布： 图1~8显示一维情况的实验结果有高的查询成功率和 较短的平均步长。标有原始的线代表初始生成图的结栗，随 2实验方法 机代表节点位置被重新洗牌后的结果（对随机匹配的情况洗 为验证MCMC方法的有效性，我们在几种模拟数据上做 牌与否跟初始图没有区别)，优化代表MCMC算法作用后的 了实验。 结果。 2.1一维的情况 在Kleinberg理想模型里（初始图有logn多项式的搜素 底图是一个环，我们建立三种图：Ⅺeinberg式的、随机匹 时间)，可以看到算法很好地恢复了查询步长。图3显示当能 配、长程连接的概率与距离平方成反比。我们建立大小为n 够利用底图的邻接关系时，恢复前后有几乎同样的搜索效率。 的图，n=1000×2',r从0到7。底图是节点数为n的环。为每 1.0 0.9 个节点加人3bn条随机边。因所有的边是无向的，平均度是 0.8 6bn。度数的选择是为了使搜索过程遇到死节点（节点没 0.7 有邻居到终点的距离比本节点到终点的距离小)的概率小。 0.6 边的长度是1到n/2,类型有三种：l)Kleinberg式的，边长度 为d的概率正比于1/d:2)边是节点随机匹配：3)边长度为d 0.4 原始 随机 的概率E比于1/d。 03 优化 后两种类型不是最优的，第二种代表低的聚类，第三种有 01 高的聚类。由Kleinberg的观点这两种图的搜索时间不可能 0 是log(π)的多项式。聚类高代表长程边太少，不能很快到达 103 10 10 节点数 终点：聚类低代表接近终点时没有足够多的边使得搜索更进 图1 查询成功率（调死节点结束，理想模型） 一步接近终点。 45 随机选取两个节点，看它们之间是否存在一条贪婪路径 (总是选择离终点最近的邻居)。当遇到死节点时，有三个选 40 择：1)结束本次搜索；2)继续搜索，选择最近的邻居；3)跳 3.5 到底图中的终点方向的邻居。 要使第二个选择可行，必须保证每一节点最多被访问一 我计 3.0 原始 次。搜索要有一最大步长，把它定为(bn)2。这一数字是 2.5 兼顾搜索成功率和成功搜索的平均步长而任意取定的。 2.0 对每一类型的图，我们都将节点位置重新洗牌和运行 1.5 MCMC算法6000n次来和原图比较。60O0n这个数字不是基 10 103 10 于理论结果，而是可承受的程序运行时间。重新洗牌后继续搜 节点数 图2成功查询的平均步长（遇死节点结束，理想模型） 索其结果相当于随机游走。 2.2二维的情况 我们同样考察了两个非理想模型。当长程连接是随机加 我们在二维底图上模拟了Kleinberg式的模型，以和一维 人的时候，算法也有很好表现。如图5,6，步长在所有大小的 情况进行比较。产生大小为n=1024×4"的图，r从0到3，节 图上都有提高。但是当不用底图时成功率难以保持，它随 点度数同一维的情况。长程边呈理想分布，即两节点相连的概 的增加而下降（闲7），实际上图上完全没有聚类。 率和距离的平方成反比。 另一非理想模型有太多的聚类，表现得最差。它有大量 我们将二维模型产生的图用于一维算法，同样将一维图 的短程连接，好像成功率应该很高，实际是成功率和平均步长 用于二维算法，来看底图的维数对Kleinberg式模型的可搜索 都没有显著提高（图8）)。给出这种图并不是小世界的，它 万方数据
第lO期 李坤朋等：基于MCMC技术的社会网络搜索 函数集合S=G7上的马尔科夫链，链的平稳分布是式(2)。 设Ot是s上的选择核，服从均匀分布，从妒。选择得9：，令 a(纯，他) = a(仍，妒，)， 则 卢(妒I，仡) = rain 妒I(善)=妒2(Y)，妒l(，，)=妒2(戈)，妒I(z)=妒2(彳)，z≠x,y (-，篱等)=幽(t，冉篆渊)。如果 称妒。妒：为x,y可交换，这种情况下上式化为卢(妒．，仡)=rain (1．。。飘，，装黜)州髫㈣表示连接域y 的边。 接下来是找到选择核，最直接的方法是随机选取茗和Y， 使纯仍为x,y可交换，即： ， 、 rl／(n+c^2)，若x,y可交换 a【‰妒2 J～0。 其他 这样建立的马尔科夫链以式(2)为平稳分布，无论从哪个位 置函数出发最终都收敛于该分布。 2 实验方法 为验证MCMC方法的有效性，我们在几种模拟数据上做 了实验。 2．1一维的情况 底图是一个环，我们建立三种图：Kleinberg式的、随机匹 配、长程连接的概率与距离平方成反比。我们建立大小为，I 的图，n=1000×27，r从0到7。底图是节点数为凡的环。为每 个节点加入31b n条随机边。因所有的边是无向的，平均度是 6 lb n。度数的选择是为了使搜索过程遇到死节点(节点没 有邻居到终点的距离比本节点到终点的距离小)的概率小。 边的长度是l到n／2。类型有三种：1)Kleinberg式的，边长度 为d的概率正比于1／d；2)边是节点随机匹配；3)边长度为d 的概率正比于l／∥。 后两种类型不是最优的，第二种代表低的聚类，第三种有 高的聚类。由Kleinberg的观点这两种图的搜索时间不可能 是log(n)的多项式。聚类高代表长程边太少，不能很快到达 终点；聚类低代表接近终点时没有足够多的边使得搜索更进 一步接近终点。 随机选取两个节点，看它们之间是否存在一条贪婪路径 (总是选择离终点最近的邻居)。当遇到死节点时，有三个选 择：1)结束本次搜索；2)继续搜索，选择最近的邻居；3)跳 到底图中的终点方向的邻居。 要使第二个选择可行，必须保证每一节点最多被访问一 次。搜索要有一最大步长，把它定为(1b n)2。这一数字是 兼顾搜索成功率和成功搜索的平均步长而任意取定的。 对每一类型的图，我们都将节点位置重新洗牌和运行 MCMC算法6000n次来和原图比较。6000n这个数字不是基 于理论结果，而是可承受的程序运行时间。重新洗牌后继续搜 索其结果相当于随机游走。 2．2二维的情况 我们在二维底图上模拟了Kleinberg式的模型，以和一维 情况进行比较。产生大小为，l=1024×47的图，rK0到3。节 点度数同一维的情况。长程边呈理想分布，即两节点相连的概 率和距离的平方成反比。 我们将二维模型产生的图用于一维算法，同样将一维图 用于二维算法，来看底图的维数对Kleinberg式模型的可搜索 性有什么影响。 2．3真实的数据 将算法用于真实的社会网络，该网络由电子邮件加密工 具PGP的用户组成。为了确保邮件发送和接收者的真实性。 PGP有一个密钥机制。用户只有面对面接触才能保证密钥的 真实性，所以他们是熟人关系。由一个节点开始递归生成该 网络。令G。是第凡步的图： 1)OG．为节点集合。它们不在q中，但与C。中至少一个 节点有边相连。 2)从aG。选择节点茹，它有最多的边进入q。 3)令e+．为G和髫组成的图。 4)循环，到q+。为要求的大小为止。 3试验结果和分析 3．1一维的情况 图l一8显示一维情况的实验结果有高的查询成功率和 较短的平均步长。标有原始的线代表初始生成图的结果，随 机代表节点位置被重新洗牌后的结果(对随机匹配的情况洗 牌与否跟初始图没有区别)，优化代表MCMC算法作用后的 结果。 在Kleinberg理想模型里(初始图有log，l多项式的搜索 时间)，可以看到算法很好地恢复了查询步长。图3显示当能 够利用底图的邻接关系时，恢复前后有几乎同样的搜索效率。 节点数 图1查询成功率(遇死节点结束，理想模型) 节点数 图2成功查询的平均步长(遇死节点结束，理想模型) 我们同样考察了两个非理想模型。当长程连接是随机加 入的时候，算法也有很好表现。如图5、6，步长在所有大小的 图上都有提高。但是当不用底图时成功率难以保持，它随n 的增加而下降(图7)，实际上图上完全没有聚类。 另一非理想模型有太多的聚类，表现得最差。它有大量 的短程连接，好像成功率应该很高，实际是成功率和平均步长 都没有显著提高(图8)口】。给出这种图并不是小世界的，它 万方数据
2602 计算机应用 第28卷 的直径是n的多项式。 下在一维数据上成功率是0.670，在二维数据上成功率是 35 0.650。差别的原因是Kleinberg模型在高维时定位因难。 --原始 30 0.7 随机 25 m…优化 0.6 0.5 0.4 10 0.3 0.2 0 10 103 0.1 103 节点数 图3 成功查询的平均步长（用底因的邻接关系，理想模型） 103 10￥ 10 节点数 140 图7 查淘成功率（遇死节点结束，随机匹配模型） 一一原始 随机 1.0 …优化 100 0.9 原始 0.8 随机 80 优化 0.7 60 0.6 0.5 40 0.4 20 2 02 10 10° 10 0.1 节点数 0 图4成功查询的平均步长（继续搜索，理想模型） l0* 103 10 节点数 35 图8 查询成功率（遇死节点结束，连接概率与距离平方成反比模型） 30 二 1.0 原始 25 0.9 随机 08 优化 20 0.7 15 0.6 05 0.4 03 0.2 103 10 10 01 节点数 图5 成功查询的平均步长（用底图的邻接关系，随机匹配模型） 10 10 10 节点数 140 原始 图9查询成功率（遇死节点停止，二维理想模型） 120 优化 …优化 100 4.5 随机 80 一一原始 4.0 60 35 40 3.0 20 2.5 l09 102 105 2 节点散 15 图6成功查询的平均步长（继续搜素，随机匹配模型） o 10 10 3.2二维的情况 节点数 图10成功查询的平均步长（道死节点停止，二维理想模难） 算法在二维模型上也进行了模拟，总的来说，没有在一维 情况表现得好，但比一维情况在非理想模型上的表现好。 3.3真实的数据 我们将二维模型产生的图用于一维算法，同样将一维图 同样我们将处理一二维模拟图的方法用于真实数据。用 用于二维算法。我]发现各维模型最好还是用于各白维数的 前述方法产生2000和4000个节点的子图，节点被随机地赋 底图。二维算法在一维数据上比在二维数据上表现稍微好 予底图上的位置，然后运行Metropolis-Hastings算法60O0n 点。如在大小为409%的图上，二维算法在遇死节点停止策略 次。底图是一维格子（环）时结果如表1。 万方数据
2602 计算机应用 第28卷 的直径是几的多项式。 节点数 图3成功查询的平均步长(用底I冬I的邻接关系，理想模型) 节点数 图4成功查询的平均步长(继续搜索，理想模型) 节点数 图5成功查询的平均步长(用底I冬I的邻接关系，随机匹配模型) 节点数 图6成功查询的平均步长(继续搜索，随机匹配模型) 3．2二维的情况 算法在-二维模型上也进行了模拟，总的来说，没有在一维 情况表现得好，但比一维情况在非理想模型上的表现好。 我们将二维模型产生的图用于一维算法，同样将一维图 用于二维算法。我们发现各维模型最好还是用于各自维数的 底图。二维算法在一维数据上比在：■维数据上表现稍微好 点。如在大小为4096的图上，二维算法在遇死节点停止策略 下在一维数据上成功率是0．670，在二维数据上成功率是 0．650。差别的原因是Kleinberg模型在高维时定位困难。 节点数 图7查询成功率(遇死节点结束，随机匹配模型) 锝 蓉 节点数 图8查询成功率(遇死节点结束，连接概率‘i距离平方成反比模型) 褥 蓉 节点数 图9查询成功率(遇死节点停止，二维理想模型) 节点数 。 图10成功查询的平均步长(遇死节点停止，二维理想模型) 3．3真实的数据 同样我们将处理一二维模拟图的方法用于真实数据。用 前述方法产生2000和4000个节点的子图，节点被随机地赋 予底图上的位置，然后运行Metropolis-Hastings算法6000n 次。底图是一维格子(环)时结果如表l。 埘明瞄吖嘶∞¨瞄眈毗。 万方数据
第10期 李坤朋等：基于MCMC技术的社会网络搜索 2603 表1 底图是一维格子（环）时运行结果 4000节点的图它的平均度比模拟图低很多，性能表现也 要差。这个图确实有很多节点只有很有限的邻居，算法不能 节点数平均度F成功率F步长C成功率C步长Le步长 很好地定位。 2000 64.6 0.647 3.0490.989 11.2194.435 结果好像不容乐观，但我们也有些许欣慰的地方。首先， 4000 46.4 0.3553.3640.86924.7937.352 杜会网络的搜索成功韦从米就很低。文献[4】用真实的社会 这里F代表遇到死节点结束搜素，C代表继续搜紫，L© 数据进行路山，成功率是13%。他们所用网络比我们大很 代表用底图的邻接关系。 多，没有我们稠帝，但他们只要求查询能够到达门标节点的同 10 一城市。Milm的成功率是20%，最近的用因特网做的重 复试验成功率是1,5%。耳者，类似路由算法还没有人提 出过，以前的搜索方法只有随机游走或者敏大度方法。 4结语 本文研究了在只给定一个图的情况下如何找到贪婪路 径，用到的方法是Metroplis-Hastings算法，计算机仿真和真实 数据结果表明贪婪搜索行很好的搜索效率，虽然不能总是达 到理想的效果，它比简单方法如随机游走更有效。算法并不 10 10 是完美的，本质上它依赖丁于选择节点来交换位置。目前节点 节点数 是随机选取的，也许还有更优秀的取样方法。算法能否用于 图11平均步长（用底图邻接关系，二维理想模型） 杜会网络搜索并没有得到彻底的回答，从我们有限的数据来 将数据在二维底图上进行检验。结果和一维差不多，有 看，它在一维底图上要比在高维情况下更加有效。 些指标表现好些，有的表现兼(F成功率)。 参考文献： [ DODDS PS,ROBY M,WATTS DJ.An experimental study of 表2庭围是二维格子时远行结果 search in global social networks[J].Science,2003,301(5634): 节点数F成功率F步长C成功率C步长Le步长 827-829. 2000 0.542 2.746 0.988 10.3683.776 [2] KLEINBERG J.The mll-wod phenomenon:An arithmie perspec- 4000 0.3323.0990.873.23.5185.303 tivel Cl//Proceedings of the 32nd ACM Sympoeium on Theory of Com- puting.New York.NY,USA:ACM.2000:163-170. 二维情况没有更好的表现，这有点出人意外。毕竞二维 [3] MARTEL C.NGUYEN V.Analyzing Kleinberg's(and other 位置分配更符合朴会树络动力学特征，人们不是活在一个环 small-world models C]//PODC '04:Proceedings of the Twenty- third Annual ACM Sympoium on Principles of Distributed Compu 上的。数据在一维底图上遇死节点停止情况下的成功率大图 ting.New York,NY,USA.ACM Press,2004:179-188. 小图分别为0.26和0.42，其他值和低维大体相同。从以上 [41 LIBEN-NOWELL D.NOVAK J.KUMAR R.er al.Geograph rou- 模拟可知算法在高维时总的来说衣现不作。 ting in networks.Proceedings of the National Academy of 2000节点的图有者和时样大小的模拟图几乎同样的平 Seience,2005.102(33):11623-11628. 均度，我们来比较它们的性能。真实数据比不上模拟数据在 [5]ADAMIC L.ADAR E.How to search a social network[J].Social 理想模型的指标，在一些方面如F成功率比随机匹配表现好。 Networks,2005,27(3):187-203. (上接第2579页) and Sensor Networks,2007,15(1):39 -68 显然，用户满意度是关平系统可生存性大小的一个主观 [2]FRANK H.FRISCH I T.Analysis and design of survivable network 因素。图6和7显乐的是系统可生存性随着用户满意度不同 []IEEE Transactions on Communication Technology,1970,218 的变化情况。从图巾可以看出，S的满意度对系统可生存性 (5):501-519. [3]MEAD N R,ELLISON R J,LINGER R C,e al Survivable Net- 影响最大，然后依次是S和S,,主要原因是相对S2和S来 work Analysis Method [RI.Pittsburgh:Camegie Mellon Software 说，系统在S,的时间比较长。所以提高最差情况下用户满意 Engineering Institute,2000. 度可以比较明显地提高系统生存性。也就是说要在系统最差 [4] PARK S.SONG J.KIM B.A survivability sraegy in mobile net- 的状态下，尽量多地提供基本服务，让用户觉得比较满意。这 works[J].IEEE Transactions on Vehicular Technology,2006.55 在本质上与减少威胁T,是相问的，都是要尽量满足用户的基 (1):328-340. 本服务，减少破坏基本服务的威胁。 [5]KIM D S.SIIAZZAD K M.PARK JS.A framework of survivability mod- for wirelcescr netwokC]Prcin of the Fins Intemaio 4结语 Conferencen Availability.Reliability ad Security (ARES06).Wash 本文根据VANET的特点和实际应用，分析了VANET的 ington,DC:IEEE Computer Socirty,06:515-522. I61 可生存性要素，给出了VANET的可生存性定义，分析了 WESTMARK V R.A definition for infommation syetem survivability [Cl//Hawaii:Proceedings of the 37th Hawaii International Confer- VANET的服务、威胁和策路，提出了基于马尔可夫链的平均 ence on System Sciences.Washington.DC:IEEE Computer Socie- 可生存性量化模型，并通过模拟验证了该模型的正确性。模 y,2004:90303.1. 拟和理论结果都表明，保证基本服务和防止严重威胁可以有 [7]MOITRA S D.KONDA S L.A Simulation Model for Managing Sur- 效保障VANET的可生存性。 vivability of Networked Information Systems[R].Pittsburgh:Came- 参考文献： gie Melln Software Engincering Institute.2000. [1]RAYA M.HUBAUX J-P.Securing vehicular ad hoc networks[J]. 【8)苏希.通信网性能分析基础IM).北京：北京邮电大学出假 Joumal of Computer Security,Special Issue on Security of Ad Hoc 杜，2006. 万方数据
第10期 李坤朋等：基于MCMC技术的社会网络搜索 表1 底图是一维格子(环)时运行结果 这里F代表遇到死节点结束搜索，c代表继续搜索，k 代表用底图的邻接关系。 节点数 图11平均步长(用底图邻接关系，二维理想模型) 将数据在二维底图上进行检验。结果和一维差不多，有 些指标表现好些，有的表现差(F成功率)。 表2底图是二维格子时运行结果 二维情况没有更好的表现，这有点出人意外。毕竟二维 位置分配更符合社会网络动力学特征，人们不是活在一个环 上的。数据在i维底图上遇死节点停止情况下的成功率大图 小图分别为0．26和0．42，J乓他值和低维大体相同。从以上 模拟可知算法在高维时总的来说表现不佧。 2000节．点的图有着和M样大小的模拟图几乎同样的平 均度，我们来比较它们的性能。真实数据比小上模拟数据在 理想模型的指标，在一些方面如F成功率比随机匹配表现好。 4000节点的图它的平均度比模拟图低很多，性能表现也 要差。这个图确实有很多节点只有很有限的邻居，算法不能 很好地定位。 结果好像不容乐观，但我们也有些许欣慰的地方。首先， 社会网络的搜索成功率从来就很低。文献[4]用真实的社会 数据进行路山，成功率是13％。他们所用网络比我们大很 多，没有我们稠密，但他们只要求查询能够到达R标节点的同 一城市。Milgram的成功率是20％，最近的用因特网做的重 复试验…成功率是1．5％。再者，类似路由算法还没有人提 出过，以前的搜索方法只有随机游走或者最大度方法。 4 结语 本文研究了在只给定一个图的情况下如何找到贪婪路 径，用到的方法是Metmplis-Hastings算法，计算机仿真和真实 数据结果表明贪婪搜索有很好的搜索效率，虽然不能总是达 到理想的效果，它比简单方法如随机游走更有效。算法并不 是完美的，本质上它依赖了选择节点来交换位置。目前节点 是随机选取的，也许还有更优秀的取样方法。算法能否用于 社会网络搜索并没有得到彻底的回答，从我们有限的数据来 看，它在一维底图上要比在高维情况下更加有效。 参考文献： 【l】DODDS P S，ROBY M，WATrs D J．An experimental study of search in global social networks[J】．Science，2003，301(5634)： 827—829． [21 KLEINBERG J．The small—world phenomenon：An algorithmic perspeefive[Cl／／Procmxlings of the 32nd ACM Symposium on Theory 0f Camputing．New York，NY，USA：ACM，2000；163—170． [31 MARTEL C，NGUYEN V．Analyzing Kleinberg’S(and other) small—world modelsI C l／／PODC’04：Proceedings of the Twentythird Annual ACM Symposium on Principles of Distributed Compu— ting．New York，NY，USA．ACM Press。2004：179—188． [41 LIBEN-NOWEI．I。D，NOVAK J，KUMAR R。et a1．Geo伊aph 1"011· ting in social networks【J1．Proceedings of the National Academy of Science，2005，102(33)：1 1623—1 1628． 【5】 ADAMIC L，ADAR E．How to search asocial network【J1．Social Networks。2005。27(3)：187—203． (上接第2579页) 显然，用户满意度是关乎系统可牛存性大小的一个主观 因素。图6和7显爪的是系统町生存性随着用户满意度不同 的变化情况。从图巾可以看出，s，的满意度对系统可生存性 影响最大，然后依次是s：和s。，主要原冈是相对s：和S。来 说，系统在S，的时间比较长。所以提高最差情况下用户满意 度可以比较明显地提高系统生存性。也就是说要在系统最差 的状态下，尽量多地提供基本服务，让用户觉得比较满意。这 在本质上与减少威胁L是相同的，都是要尽量满足用户的基 本服务，减少破坏基本服务的威胁。 4 结语 本文根据VANET的特点和实际应用，分析了VANET的 可生存性要素，给出rr VANET的可生存性定义，分析了 VANET的服务、威胁和策略，提出了基于马尔可夫链的平均 可生存性量化模型，并通过模拟验证了该模型的正确性。模 拟和理论结果都表明，保证基本服务和防止严重威胁可以有 效保障VANET的可生存性。 参考文献： 【1】 RAYA M，HUBAUX J-P．Securing vehicular ad hoe networks【J】． Journal 0f Computer Security．Special Issue on Security of Ad Hoe and Sensor Networks，2007，15(1)：39—68． 【2】 FRANK H。FRISCH I T．Analysis and design of survivable network 【J】．IEEE Transactions on Communication Technology，1970。218 (5)：501—519． 【3】MEAD N R，EU璐oN R J，LINGER R C，et a1．Survivable Network Analysis Method【R 1．Pittsburgh：Carnegie Mellon Software Engineering Institute，2000． 【4】PARK S，SONG J，KIM B．A survivability strategy in mobile networks【J】．IEEE Transactions on Vehicular Technology，2006，55 (1)：328—340． 【5】KIM D S，SIIAZZADK M，PARK J S．Aframework ofsurvivabilityroodd for wireless∞∞w network【C]／／Proceedings of the 1．Xrst Intemational c0娟煳on Availability，Reliability and Security(ARKS’06)．Wash— mDC：删匝Computer Soeiety，知6：515—522． 【61 WESTMARK V R．A definition for information system survivability f C1／／Hawaii：Proceedings of the 37th Hawaii International Conference on System Sciences．Washington。IX3：IEEE Computer Soeiety，2004：90303．1． 【71 MOI‘FRA S D，KONDA S L．A Simulation Model for Managing Survivability of Networked Information Systems【R】．Pittsburgh：Came· gie Mellon Software Engineering Institute。2000． f8】 苏驷希．通信网性能分析基础【M】．北京：北京邮电大学出版 社，2006． 爱_霸件 万方数据