搜索服从幂律分布的网络 论文阅读

编程日常/2023/11/30 14:45:48

一、定义

1、幂律分布网络定义:
大部分通信网络和社会网络都具有幂律分布的特点,也即度数高的节点的数量少,度数低节点的数量多。

2、数学推导:

  1. 对于指数为τ、最小度数为k = 1、在m=kmaxm = k_{max}m=kmax处有突变截止点的幂律分布图,其生成函数为:在这里插入图片描述

  2. 节点总数为N的网络图中,所需搜索步骤数s约为ln2(N)ln^2(N)ln2(N)

3、搜索中的已知信息:
1.节点可以随机地将消息传递给它的一个邻居,也可以避免将消息传递给已经看到该消息的节点。
4. 节点可能只知道自己的属性(也即自己有几个邻居),也可能知道邻居的属性(比如该邻居有几个邻居),故可以选择将消息传递给邻居最多的邻居。
3.搜索过程中,每一步选择一个度比当前节点高的节点。

二、实验结果与贡献:

1、实验结果:
1.对实际的Gnutella网络的大约700个节点进行爬行,模拟搜索算法。假设每个文件只存储在一个节点上,那么在8个步骤或更少的时间内就可以找到50%的文件。此外,如果多个节点都存储了正在查找的文件,则搜索将更快。
2.大型社交网络指数基本都在(τ = 2.1 - 2.3)范围内,而对于非社交信息传递的网络,τ约为4,在不知道目标位置的情况下很难传递消息。
3.幂律分布网络与泊松分布网络的对比:
·在搜索某一点时,若幂律分布网络图中50%的部分节点已被访问过,则之后重复访问这些节点的时间约占80%,而随机分布的泊松图重复访问的时间为50%,也即:该搜索算法优先访问已经访问过的高度数节点,而非未访问过的低度数节点。
·在这种情况下,开始的节点只有一个连接边,但是两步之后,就能通过边到达一个度很高的节点。从此,就可以继续连接到度数很高的节点。该策略允许在最少的步骤数中扫描最大数量的节点。相比之下,即使这两个图有相当数量的节点和边泊松分布网络图的最大度节点为11,只有在第81步时才达到。
·下图显示了在10000个结点的图中,由随机策略和本文提出的策略访问到的随着步数增长访问到的结点总数。大约50%的节点在前10步内就能被扫描到;但是,有少量节点需要的查找步骤等于节点总数,甚至比节点总数还要多。
在这里插入图片描述

2、本文贡献:
在本文中,我们提出了一些消息传递算法,可以有效地用于在大型幂律网络(如Gnutella)中进行搜索。具体而言,本文优先利用度数高的节点进行局部搜索,与第5篇文献一样,算法使用结点本地信息,如邻居的身份和连通性,以及邻居的邻居,但不使用目标的全局位置,其搜索代价与图的规模呈次线性关系,并有助于减少网络搜索流量。


https://www.daipet.cn/news/4640.html

相关文章

LeetCode链表练习(上)

文章目录前言1.反转链表1.题目分析2.代码示例2.力扣203. 移除链表元素1.题目分析2.代码示例3.力扣876. 链表的中间结点1.题目分析2.代码示例4.链表倒数第k个节点1.题目分析2.代码示例5.总结前言 之前介绍了链表的实现,为了更好巩固所学的知识,刷题是很有…

【springboot】你了解@Autowired 和 @Resource吗?@Autowired 和 @Resource深入分析

Autowired 和 Resource深入分析“认祖归宗”--Autowired 和 Resource来源“通过现象看本质”--Autowired 和 Resource作用和区别1.现象一:一个业务接口只对应一个业务实现类2.现象二:一个业务接口 对应 两个或多个业务实现类我们在开发中,一直…

【数据结构】链表其实并不难 —— 手把手带你实现双向链表

文章目录0. 前言1. 双向链表的概念2. 双向链表的实现2.1 结构设计2.2 接口总览2.3 初始化2.4 创建新节点2.5 尾插2.6 头插2.7 尾删2.8 头删2.9 查找2.10 在pos位置之前插入2.11 在pos位置删除2.12 打印2.13 销毁3. 完整代码List.hList.ctest.c4. 结语0. 前言 之前,…

【路径规划】局部路径规划算法——DWA算法(动态窗口法)|(含python实现)

文章目录参考资料1. DWA算法原理1.1 简介1.2 算法原理1. 速度采样2. 轨迹预测(轨迹推算)3. 轨迹评价2. Python实现2.1 参数配置2.2 机器人运动学模型2.3 DWA算法类实现2.4 画图2.5 主函数3. 总结参考资料 The Dynamic Window Approach to Collision Avo…

【Python百日进阶-WEB开发】Day175 - Django案例:07状态保持

文章目录五、状态保持5.1 Django中状态保持5.1.1 状态保持概述5.1.2 Cookie5.1.2.1 Cookie的用处:5.1.2.1 Cookie的特点:5.1.2.1 Cookie的操作:5.1.3 session5.1.3.1 Session的特点:5.1.3.2 Session依赖于Cookie5.1.3.3 存储方式5…

网页数据抓取-网页实时数据抓取软件

网页数据抓取,随着社会的发展,互联网的普及,不管是企业还是个人都意识到数据的重要性。今天给大家分享一款免费的网页数据抓取软件。只要点点鼠标就能轻松采集你想要的内容不管是导出还是自动发布都支持!详细参考图片!…

Qlib股票数据获取与查看(Qlib学习1)

文章目录Qlib基本信息数据使用方法1. 借助Qlib下载数据2. 查看相关数据参考链接Qlib基本信息 Qlib Github主页:https://github.com/microsoft/qlib Qlib quickstart:https://qlib.readthedocs.io/en/latest/introduction/quick.html#introduction 基本…

二分查找的模板

这篇博客的二分用的都是左闭右闭的区间,对于二分来说还是我还是习惯这样写 最传统的二分查找,用左闭右闭写 int search(vector<int>& nums, int target) {int left 0;int right nums.size() - 1; // 定义target在左闭右闭的区间里&#xff0…

LeetCode刷题---142. 环形链表 II(双指针-快慢指针)

文章目录一、编程题:142. 环形链表 II(双指针-快慢指针)1.题目描述2.示例1:3.示例2:4.示例3:5.提示:6.提示:二、解题思路1.思路2.复杂度分析:3.算法图解三、代码实现总结…

Mybatis学习之动态Sql

目录 1. 什么是动态Sql 2. 动态Sql需要学习什么 3. 动态Sql之《if》 4. 动态Sql之《where》 5. 动态Sql之《foreach》 6. 动态Sql之《sql》 7. PageHelper分页插件的使用 1. 什么是动态Sql 答案:动态Sql指的是,Sql语句是变化的,不是固…