【作者】 吴艾； 刘心松； 皮建勇； 刘克剑；

【Author】 WU Ai LIU Xinsong PI Jianyong LIU Kejian School of Computer Science, University of Electronic Science & Technology of China, Chengdu 610054

【机构】 电子科技大学计算机学院；

【摘要】 网络结构及属性对节点搜索的影响是复杂网络研究中的一个重要内容。很多实际网络具有高聚集特性,文章研究了这一类网络中的节点搜索问题。改进现有的高聚集度网络生成算法,分析网络的度分布、聚集度特性及其对节点搜索的影响。采用无历史路径记忆、基于本地信息的搜索方法, 研究了随机搜索算法和三种与聚集度相关的搜索算法,算法中邻居节点的选择概率与聚集度大小相关, 仿真计算各算法的节点平均搜索时间。结果表明,聚集度较小时,随机搜索和聚集度居中的节点被选择的概率大的算法的效率最高,而聚集度较大时,选择邻居的概率与聚集度成反比的搜索算法可得到最小的平均搜索时间。更多还原

【Abstract】 Many real networks are high clustered, it is important to know the behavior of searching in these networks. Existed method is improved to generate networks with high clustering and power-law degree distribution. The average time taken to find a desired node in high clustering scale-free networks is studied in this paper. Based on local information and no memory of history searching path, Four searching algorithms relating to clustering are studied, The difference of them is the way to select a neighbor as next node.,average search time is attained by simulations. The result is that random selecting and media clustering corresponding to larger selecting probability algorithms can get the smallest search time when clustering coefficient is small, but when the clustering coefficient is large, algorithm of selecting probability is negative related to clustering has the highest efficiency. Conclusion indicates that appropriate searching algorithm must be employed for different network topologies.更多还原