| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 大数据 -> 大数据——Spark GraphX中算法介绍 -> 正文阅读 |
|
[大数据]大数据——Spark GraphX中算法介绍 |
一、ConnectedComponents算法???????ConnectedComponents即连通体算法用id标注图中每个连通体,将连通体中序号最小的顶点的id作为连通体的id。 图关系如下时:
?结果如下
图关系如下时: ?
?结果如下
二、StringlyConnectedComponents算法????????有向图中最大的强连通子,输出每个强连通子图顶点对应的最小顶点编号。 图关系如下:
结果如下:
解析:1、4、6顶点构不成环,所以在StronglyConnectedComponent下最小顶点id为自身 ? ? ? ? ? ?2 -> 5 -> 3构成强连通图,故其最小顶点id为2 应用场景★★★话单分析人物关系 三、ShortestPaths法????????ShortestPaths 是可以计算节点到节点的最短路径,该最小路径为最小步长,并非最短距离。 图关系如下:
结果如下:?
应用场景★★★物联网(物流) 四、LabelPropagation算法(没理解过程)LabelPropagation,是一种基于图的半监督学习算法(Semi-supervised learning),应用场景为:社区发现(Community detection)。传统意义上的社区指的是网络中的一组节点间具有较大的相似性,从而形成的一种内部连接紧密,而外部稀疏的群体结构,根据各社区节点有无交集,又可分为非重叠型社区和重叠型社区。对给定的网络图寻找其社区结构的过程称为“社区发现”。大体上看,社区发现的过程就是一种聚类的过程。 基本思想:标签传播算法的应用场景是不重叠社区发现,其基本思想是:将一个节点的邻居节点的标签中数量最多的标签作为该节点自身的标签。给每个节点添加标签(label)以代表它所属的社区,并通过标签的“传播”形成同一标签的“社区”结构。简而言之,你的邻居属于哪个label最多,你就属于哪个label。该算法的有点是收敛周期短,除了迭代次数无需任何先验参数(不需事先指定社区个数和大小),算法执行过程中不需要计算任何社区指标。 时间复杂度:对顶点分配标签的复杂度为O(n),每次迭代时间为O( m),找出所有社区的复杂度为O (n +m),这是一次迭代的时间复杂度,非多次。标签传播算法的计算复杂度十分便宜,但是它不保证收敛,且迭代次数足够多之后,所有联通节点最终收敛为一个社区。 传播过程:1)初始时,给每个节点一个唯一的标签; 2)每个节点使用其邻居节点的标签中最多的标签来更新自身的标签。 3)反复执行步骤2),直到每个节点的标签都不再发生变化为止。 一次迭代过程中一个节点标签的更新可以分为同步和异步两种。所谓同步更新,即节点z在第t次迭代的label依据于它的邻居节点在第t-1次迭代时所得的label;异步更新,即节点z在第t次迭代的label依据于第t次迭代已经更新过label的节点和第t次迭代未更新过label的节点在第t-1次迭代时的label。很拗口,简言之,同步指所有邻居节点这一轮都还未更新,t 节点是这其中的第一个更新者,异步指t不是其中的第一个更新者,邻居中同时存在此轮已更新和未更新者。 注意事项:1、迭代次数设定一个阈值,可以防止过度运算; 2、对于二分图等网络结构,同步更新会引起震荡; 3、类似(“强”社区>)定义的结构(该社区>=); 4、每个顶点在初始的时候赋予唯一的标签,即“重要性”相同,而迭代过程又采用随机序列,会导致同一初始状态不同结果甚至巨型社区的出现; 5、如果能预测“社区中心”点,能有效提高社区发现的准确度,大幅提高效率; 6、同一节点的邻居节点的标签可能存在多种社区最大数目相同的情况,取“随机”一个作为其标签 图关系如下:
结果如下:
解析: 第一次迭代后 ?第二次迭代 第三次迭代? 第四次迭代 应用场景★★★游戏通过聊天记录在玩家中找代理 五、TriangleCount算法Triangle Count的算法思想如下:
注意:计算三角形时,要有计算方向(如,起始结点id<中间结点id<目的结点id)。 图关系如下:
?结果如下:
应用场景★★★社群发现:社群耦合关系紧密程度(一个人的社交网络中三角形数量越多说明社交关系越稳定 |
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 | -2024/5/17 15:58:14- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |