摘要
实验和理论表明社会网络中存在着短路径,即人们可以在较少的步数内找到目标。研究了社会网络中的贪婪搜索现象,给出了将长程连接图嵌入底层一维和二维网格的马尔科夫链蒙特卡罗方法。该方法更符合现实情况,坐标体系只是用于网上距离的计算。将算法用于模拟数据(根据一维和二维理想模型产生的图)和真实的社会网络数据均有很好的查询效率,查询成功率高,成功查询平均步长短。
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.
出处
《计算机应用》
CSCD
北大核心
2008年第10期2600-2603,共4页
journal of Computer Applications
关键词
复杂网络
蒙特卡罗方法
小世界
贪婪搜索
~omplex network
Monte-Carlo algorithm
small world
greedy routing
