第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 perspee￾five[Cl／／Procmxlings of the 32nd ACM Symposium on Theory 0f Cam￾puting．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 Twenty￾third 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 Net￾work Analysis Method【R 1．Pittsburgh：Carnegie Mellon Software Engineering Institute，2000． 【4】PARK S，SONG J，KIM B．A survivability strategy in mobile net￾works【J】．IEEE Transactions on Vehicular Technology，2006，55 (1)：328—340． 【5】KIM D S，SIIAZZADK M，PARK J S．Aframework ofsurvivabilityrood￾d 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 Confer￾ence on System Sciences．Washington。IX3：IEEE Computer Soeie￾ty，2004：90303．1． 【71 MOI‘FRA S D，KONDA S L．A Simulation Model for Managing Sur￾vivability of Networked Information Systems【R】．Pittsburgh：Came· gie Mellon Software Engineering Institute。2000． f8】 苏驷希．通信网性能分析基础【M】．北京：北京邮电大学出版 社，2006． 爱_霸件 万方数据