Spark GraphX 中 PageRank 图算法对于图中有些顶点与其他顶点不连通的情况适用么? 5C

我把问题再详细讲述一下,图是无向多重图,如下图所示的图 图片说明

0

3个回答

PageRank只能计算有向图,不过你可以把无向图有向图,转换成graph的时候要小心。
孤立点的权重将会是零,计算时可以预先去掉孤立点。
非连通图也无所谓,效果相当于把每个联通子图都分别计算了一遍。
重边的也可以,计算的时候相当于对边加权了,与去重边后计算效果不一样。

0
MF18211547635
MF18211547635 或者您能发我个邮箱吗?和您详细交流一下
一年多之前 回复
MF18211547635
MF18211547635 无向图转成有向图怎么转合适呢? 比如说上图两个点之间有一条边的,转成有向图就把这条边替换成两个相反方向的边么?
一年多之前 回复

是的,把一条无向边替换成两个相反的方向是可行的,相当于网页之间的相互引用。

0
-1
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
Spark组件之GraphX学习6--随机图生成和出度入度等信息显示
更多代码请见:https://github.com/xubo245/SparkLearning 1解释 简单不详述 2.代码: /** * @author xubo * ref http://spark.apache.org/docs/1.5.2/graphx-programming-guide.html * time 20160503 */ package
实战9.Spark图计算GraphX介绍及实例
1、GraphX介绍 1.1 GraphX应用背景 Spark GraphX是一个分布式图处理框架,它是基于Spark平台提供对图计算和图挖掘简洁易用的而丰富的接口,极大的方便了对分布式图处理的需求。 众所周知·,社交网络中人与人之间有很多关系链,例如Twitter、Facebook、微博和微信等,这些都是大数据产生的地方都需要图计算,现在的图处理基本都是分布式的图处理,而并非单机处理。Sp
并行图计算: GraphX 的 pregel 接口
pregel, 是一个计算模型, 由 Google 最先提出, 后来 Spark 采用它作为迭代图计算的一个通用编程接口.pregel 计算模型一个 pregel 程序由一系列叫做 超步(superstep) 的迭代构成, 在每个迭代中, 每个顶点会接收到它的邻居们在上一轮迭代发送的消息, 然后改变它的顶点和边. 此外, 在每个超步结束的时候, 每个顶点也会给它的邻居们发送消息. 通过将其看作顶点,
graphx之图迭代
迭代迭代思想是spark的精髓之一,所谓迭代,即每一步的输出结果作为下一步的输入,因而相邻迭代具有很强的关系。 graphx更是将这种迭代思想运用的灵活高效。联通分量通过graphx lib中的ConnectedComponents连通分量算法,简单介绍迭代和消息传播机制。示例见下图:在完成顶点的初始化后,连通分支开始迭代过程: 为区分顶点自身id与连通分支id,后者称作cid。 1. 发送消
Spark GraphX下强连通子图和社团发现算法在1T TPC-DS数据集下执行方法、优化和性能估算
概述: 下面内容说的是在TPC-DS 1T数据集上用web_sales表ws_bill_customer_sk, ws_ship_customer_sk作为起始点和结束点,以ws_quantity为权重跑Spark GraphX(2.0.0以上版本)程序的正确姿势。用下面程序跑可以避免Spark GraphX在大数据情况下的各种bug, 在程序效率,gc稳定性上都有增强。 数据特征:
【练习】图的出度计算
题目:有一个邻接表存储的图G,分别设计实现如下要求的算法: (1)求出图G中每个顶点的出度; (2)求出图G中出度最大的一个顶点,输出该顶点的编号; (3)计算图G中出度为零的顶点数; (4)判断图G中是否存在边i,j>。   分析:从图的表头结点出发,一次访问边表结点,并进行计数,就可得到相应每个顶点的出度。问题4可令p=G.vertex.firstarc,然后一次遍历p指向链表中的每
Spark GraphX原理介绍
背景现实应用中,数据内部可能存在较高的关联度,如图模型应用。在对这样的数据进行处理时,并行计算框架就会面临较大的挑战,会引入大量的数据连接(join)和聚合(aggregation)操作,带来大量的计算和数据迁移,严重消耗集群资源,因此对此类算法的优化就显得极为重要。 互联网上网页权值计算的PageRank算法是一个典型的图模型问题,它依据网页之间的链接指向关系来判断网页的重要性,指向一个网页的链
SparkGraphX快速入门
1       图 图是由顶点和边组成的,并非代数中的图。图可以对事物以及事物之间的关系建模,图可以用来表示自然发生的连接数据,如: 社交网络 互联网web页面 常用的应用有: 在地图应用中找到最短路径 基于与他人的相似度图,推荐产品、服务、人际关系或媒体 2       术语 2.1    顶点和边 一般关系图中,事物为顶点,关系为边 2.2    有向图和无向图
Spark 中 GraphX 指南(一)
问题导读 1.什么是GraphX? 2.如何将Spark和GraphX引入到项目中? 3.从一个图中取出顶点特征加入到另外一个图中如何实现? Spark中文手册-编程指南 GraphX编程指南 GraphX是一个新的(alpha)Spark API,它用于图和并行图(graph-parallel)的计算。GraphX通过引入Resilient
利用并查集进行图中两顶点是否连通的判断
//利用并查集判断图中两节点是否连通 #include #include using namespace std; const int maxn=100+5; int vset[maxn]; int Getparent(int i)                //路径压缩 {     if(i!=vset[i])         vset[i]=Getparent(vset
Spark Graphx图计算之二跳邻算法实战!
Spark Graphx图计算之二跳邻算法实战! def sendMsgFunc(edge:EdgeTriplet[Int, Int]) = { if(edge.srcAttr <= 0){ if(edge.dstAttr <= 0){ // 如果双方都小于0,则不发送信息 Iterator.empty
Spark之GraphX案例-PageRank算法与分析
1.算法原理PageRank算法即网页排名算法,是Google创始人拉里· 佩奇和谢尔盖· 布林与1997年构建早期的搜索系统原型时提出的链接分析算法。自从Google在商业上获得巨大成功后,该算法引起了研究者们的广泛关注,目前很多重要的链接算法都是在PageRank算法基础上衍生出来的。PageRank算法是Google用来标识网页等级的重要依据,是Google衡量一个网站的好坏的唯一标准。对网...
Spark中文手册9:spark GraphX编程指南(2)
问题导读 1.GraphX提供了几种方式从RDD或者磁盘上的顶点和边集合构造图? 2.PageRank算法在图中发挥什么作用? 3.三角形计数算法的作用是什么? Spark中文手册-编程指南 Spark之一个快速的例子Spark之基本概念 Spark之基本概念 Spark之基本概念(2) Spark之基本概念(3) Spark-sql由入门到精
数据结构---->图的连通性和最小生成树
图的连通性和最小生成树 四 图的连通性 生成树:是一个极小连通子图,它含有图中全部顶点,但只有n-1条边。 生成森林:由若干棵生成树组成,含全部顶点,但构成这些树的边是最少的。 1:对连通图进行遍历,得到的是什么? ——得到的将是一个极小连通子图,即图的生成树! 由深度优先搜索得到的生成树,称为深度优先搜索生成树。 由广度优先搜索得到的生成树,称为广度优先搜索生成树。 2:对非连通
Spark入门 -- Spark图计算GraphX介绍及实例
http://www.doc88.com/p-3874973145414.html https://www.cnblogs.com/shishanyuan/p/4747793.html https://endymecy.gitbooks.io/spark-graphx-source-analysis/content/
谈谈Spark GraphX吧!
一.浅谈Spark GraphX 1.首先,介绍下构成图的两大结构体。 1)一个是节点RDD,其结构体如下: VertexRDD[VertexProperty]=RDD[(VertexId,VertexProperty)] 2)一个是边RDD,其结构体如下: EdgeRDD[EdgeProperty]=RDD[Edge[EdgeProperty]]),附加一个既含有节
GraphX迭代的瓶颈与分析
背景测试了一个case,用GraphX 1.6跑标准的LPA算法,使用的是内置的LabelPropagation算法包。数据集是Google web graph,(忽略可能这个数据集不是很合适),资源情况是standalone模式,18个worker,每个worker起一个executor,50g内存,32核,数据加载成18个分区。case里执行200轮迭代,代码:import org.apache
Spark组件之GraphX学习10--PageRank学习和使用(From examples)
更多代码请见:https://github.com/xubo245/SparkLearning 1解释 原理在参考【3】中讲的很详细,包括MapReduce情况下的。 源码: /** * Run a dynamic version of PageRank returning a graph with vertex attributes containing the
推荐算法:基于图的算法:pagerank
基本模型*随机游走模型 针对浏览网页的用户行为建立的抽象模型 直接跳转:打开浏览器,输入网址,然后根据链接跳转转移概率矩阵 则可以组织这样一个N维矩阵:其中i行j列的值表示用户从页面j转到页面i的概率 M=⎡⎣⎢⎢⎢⎢01/31/31/31/201/2000011/21/200[AA,BA,CA,DA][AB,BB,CB,DB][AC,BC,CC,DC][AD,BD,CD,DD]⎤⎦⎥⎥⎥⎥M=
Graphx入门之简单pagerank
需求:有两份数据集,一份是边,一份是点。求点的PageRank 格式: 边:sourceID destID 点:name sourceIDspark-shellspark shell属于最简单入门的local版本。建图有很多的方式,如将边的集合转换为图,或者是直接将数据导出为图。我们使用最简单的导出为图 - 代码如下import org.apache.spark.graphx._#用绝对路径
图学习(1)
1、       连通图上各边权值均不相同,则该图的最小生成树是唯一的。 (是自由树,即根结点不确定)   2、       用n表示图中顶点数目,e表示边或弧的数目: (1)        对于无向图,e的取值范围是0~N(N-1)/2;有N(N-1)/2条边的无向图叫完全图。 (2)        对于有向图,e的取值范围0~N(N-1);相应的有N(N-1)条边的有向图叫有向完全图
图的相关算法(二):最小生成树算法
最小生成树 在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到最小,则称其为连通网的最小生成树。 例如,对于上图中的连通网可以有多棵权值总和不相同的生成树。 Kruskal算法 1.介绍 克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法。 基本思想:按...
GraphX学习之 根据边表和点表构建图
根据已知的边表和点表构建一个图。此处我没自己构建数据 一. 表 点表(VertexId,msg): (1L,&quot;Ann&quot;)   (2L,&quot;Bill&quot;) (3L,&quot;Charles&quot;)   (4L,&quot;Diane&quot;)   (5L,&quot;Likes-status&quot;)   边表: (1L,2L,“is-friends-with”) (2L,3L,“is-friends-with”) (3L,...
TriangleCount三角形计数
Graphx作为Spark的图计算组件,提供了丰富的图操作接口,以及6个常用的算法(在graphx lib中)。这里简单介绍下三角形计数TriangleCount算法原理;TriangleCount算法“统计每个顶点所在的三角形个数”。 关于三角形的定义,你一定不陌生。graphx是如何识别三角形,并做统计的呢 正如上图所示:每个顶点收集邻居点,如点1的邻居为(2,3,4),graphx中col
设计一个算法,求不权无向图连通图G中距离顶点v的最远的一个顶点
思想:图G是不带权的无向连通图,一条边的长度为1,因此,求距离顶点v的最远的顶点,即求距离顶点v的边数最多的顶点。利用广度优先遍历算法,从v出发进行广度遍历,类似于从顶点v出发一层层地向外扩展,到达j, …,最后到达的一个顶点k即为距离v最远的顶点。遍历时利用队列逐层暂存各个顶点,最后出队的一个顶点k即为所求。如图所示: 对
图的连通性和连通分量
1、无向图的连通性 运用深度优先搜索或广度优先搜索遍历无向图可以分析图的连通性。可通过额外设置计数器count(初始值0)统计出图的连通分量,每调用一次,计数器count增1。当遍历完无向图时,若count=1,则图连通,若count>1,图非连通,count的值就是该图的连通分量数。 #include using namespace std; #define INFINITY 6
判断任意两个顶点间是否存在路径
采用邻接表存储有向图,此算法可以判断任意两个顶点间是否存在路径
最短路径算法(1)—Dijkstra(迪杰斯特拉)算法
转载来源:http://www.wutianqi.com/?p=1890
经典算法之Floyd算法(求图中任意一对顶点间的最短路径)
/************************ author's email:wardseptember@gmail.com date:2018.1.30 ************************/ /* 佛洛伊德算法思想: 1)设置两个矩阵A和Path,初始时将图的邻接矩阵赋值给A,将矩阵Path中元素全部设置为-1 2)以顶点k为中间顶点,k取0——n-1(n为图中顶点个位),
算法之----欧拉回路,欧拉通路,半欧拉图
若图G中存在这样一条路径,使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈,则称为欧拉(Euler)回路。 (用于连通判断)DFS(Depth-First-Search)深度优先搜索算法,是搜索算法的一种。下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路
数据结构之基于深度优先搜索,输出无向图中给定的两个顶点之间的所有路径
#include &amp;lt;iostream&amp;gt;using namespace std;struct StackNode{ int data; StackNode *next;};void push(StackNode *&amp;amp;S,int e){ StackNode *p=new StackNode; p-&amp;gt;data=e; p-&amp;gt;next=S; S=p;}int pop(Stac...
图中任意两个顶点间的最短路径之——Floyd算法
1、基本原理。floyd算法原理ppt2、实现。//假定图中最大顶点个数为5 #define MAX_VERTEX 5 //采用二维数组来表示图 //两个顶点间的距离为1000 ,代表两顶点间无之间相连的边 int graph[MAX_VERTEX][MAX_VERTEX]= { {0,1,2,1000,4}, {1,0,1000,8,2}, {2,1000,0,1000,...
图之从一个顶点到其余各个顶点的最短路径(有向图)
目录 从一个顶点到其余各个顶点最短路径的简介 举例以及详细分析 代码块 测试结果 从一个顶点到其余各个顶点最短路径的简介1.定义概览Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,
快刀初试:Spark GraphX在淘宝的实践
摘要:由于Spark GraphX性能良好,又有丰富的功能和运算符,能在海量数据上自如运行复杂的图算法,淘宝尝试将它作为分布式图计算平台,进行各种算法尝试和生产应用。本文结合GraphX的原理和特点,分享其在淘宝的应用实践。 早在0.5版本,Spark就带了一个小型的Bagel模块,提供了类似Pregel的功能。当然,这个版本还非常原始,性能和功能都比较弱,属于实验型产品。到0.8版本时,鉴于业
图的基本算法(单源最短路径)
在许多路由问题中,寻找图中一个顶点到另一个顶点的最短路径或最小带权路径是非常重要的提炼过程。正式表述为,给定一个带权有向图G = (V, E) , 顶点s到v中顶点t的最短路径为在边集E中连接s到t代价最小的路径。要做到这一点首先要解决更为一般的单源最短路径问题。在单源最短路径问题中,计算从一个起始顶点s到其他与之相邻顶点之间的最短路劲。Dijkstra算法解决单源最短路径问题的方法之一就是Dijk
输出连通分量的个数和各连通分量的顶点集
深度优先遍历以邻接表表示的图G,输出连通分量的个数和各连通分量的顶点集
PAGE-RANK算法及SPARK实现分析
查看原文:http://www.wyblog.cn/2017/01/06/pagerank%e7%ae%97%e6%b3%95%e5%8f%8aspark%e5%ae%9e%e7%8e%b0%e5%88%86%e6%9e%90/算法 这里不总结算法,下面这篇博客总结的很清晰。 http://www.cnblogs.com/fengfenggirl/p/pagerank-introduction
图——从一个顶点到其余各顶点的最短路径——狄克斯特拉算法
/* *Copyright (c) 2015 , 烟台大学计算机学院 *All right resvered . *文件名称: Dijkstra算法.cpp *作 者: 郑兆涵 *图——从一个顶点到其余各顶点的最短路径——狄克斯特拉算法 */ 问题: 从一个顶点到其余各顶点的最短路径——狄克斯特拉算法 编程代码:
T1348 城市公交网建设问题(#Ⅲ- 4 - 5)
【题目描述】 有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少? 【输入】 n(城市数,1&amp;lt;≤n≤100) e(边数) 以下e行,每行3个数i,j,wij,表示在城市i,j之间修...
利用迪杰斯特拉算法求某一顶点到其余各顶点的最短路径
【迪杰斯特拉算法思想】      设有两个顶点集合S和T,集合S中存放图中已找到最短路径的顶点,集合T存放图中剩余顶点。初始状态下,集合S中只包含源点V0。然后不断从集合T中选取到顶点V0路径长度最短的顶点Vu并入集合S中。集合S中每次并入一个新的顶点Vu后,都要修改顶点V0到集合T中顶点的最短路径长度值。不断重复此过程,直到集合T中的顶点全部并入集合S中为止。【深入理解】      当集合T中的...
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 传统机器学习不适用大数据 大数据在学校中的应用情况