修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

v5.0
搜索
    v5.0

      PageRank

      HDC 分布式

      概述

      PageRank(网页排名)最初是在万维网(WWW)的背景下提出的,它利用WWW的链接结构来产生全局、客观的网页“重要性”排名供搜索引擎使用。该算法由Google联合创始人Larry Page和Sergey Brin于1997-1998年提出:

      随着技术的发展与大量关联性数据的产生,PageRank也被许多其他领域采用。

      基本概念

      链接结构与PageRank

      在WWW中,网页中包含的超文本在网页之间创建链接。每个网页(节点)都可以有一些前链(通过出边连接)和后链(通过入边连接)。在下图中,A和B是C的后链,D是C的前链。

      不同网页在后链数量方面差异很大。在自然状态下,那些重要、权威或高质量的网页会获得更多或更重要的后链。

      PageRank的核心思想是:一个网页的后链的排名总和越高,则该网页的排名就越高。这同时涵盖了两种情况,一是网页有大量的后链,二是网页的后链尽管数量不多但排名很高。

      排名传递

      所有网页的排名(分值)是以递归的方式计算的,所有网页的初始排名分值可以是任意的,然后进行迭代计算直至收敛。在每次迭代中,每个网页均匀地将其自身的排名分值传递给其所有的前链;同时,每个网页都从其所有后链获得排名分值。因此,网页u在一次迭代后的排名分值为:

      其中Bu是网页u的后链集合。

      以下是一组网页间的排名传递达到稳定的状态:

      阻尼系数

      考虑以下几种类型的网页:

      • 没有后链的网页。它们获得的排名是0,但它们仍需被浏览到。
      • 没有前链的网页。它们的排名分值会从系统中消失。
      • 对于一组网页,它们只指向组内的网页,而不指向任何组外的网页。

      为了克服这些问题,我们引入阻尼系数(Damping Factor),其值介于0和1之间。它为每个网页提供一个保底排名分值,同时削弱从后链传递过来的排名分值。一次迭代后网页u的排名变为:

      其中d是阻尼系数。例如,当d=0.7时,如果一个网页从后链接收到的排名总和为8,则该网页在本轮的排名为0.7*8 + (1-0.7) = 5.9

      阻尼系数也可以理解为浏览者随机跳转到不是当前网页的前链之一的其他网页的概率。

      特殊说明

      • 孤点的排名将为(1-d)。
      • 自环边被视为一条入边和一条出边,网页会通过自环边会将一部分排名传递给自身。有大量自环边的图通常需要较多次的迭代才能趋于稳定。

      示例图集

      创建示例图集:

      // 在空图集中逐行运行以下语句
      create().node_schema("account").edge_schema("follow")
      insert().into(@account).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}, {_id:"H"}, {_id:"I"}, {_id:"J"}, {_id:"K"}, {_id:"L"}, {_id:"M"}, {_id:"N"}])
      insert().into(@follow).edges([{_from:"A", _to:"E"}, {_from:"B", _to:"E"}, {_from:"C", _to:"A"}, {_from:"C", _to:"H"}, {_from:"D", _to:"J"}, {_from:"E", _to:"G"}, {_from:"E", _to:"G"},{_from:"E", _to:"I"}, {_from:"E", _to:"N"}, {_from:"F", _to:"L"}, {_from:"F", _to:"B"}, {_from:"H", _to:"C"}, {_from:"H", _to:"E"}, {_from:"I", _to:"E"}, {_from:"J", _to:"E"}, {_from:"K", _to:"E"}, {_from:"K", _to:"M"}, {_from:"L", _to:"E"}, {_from:"L", _to:"F"}, {_from:"L", _to:"N"}, {_from:"M", _to:"E"}, {_from:"N", _to:"F"}])
      

      在HDC图集上运行算法

      创建HDC图集

      将当前图集全部加载到HDC服务器hdc-server-1上,并命名为 hdc_pagerank

      CALL hdc.graph.create("hdc-server-1", "hdc_pagerank", {
        nodes: {"*": ["*"]},
        edges: {"*": ["*"]},
        direction: "undirected",
        load_id: true,
        update: "static",
        query: "query",
        default: false
      })
      

      hdc.graph.create("hdc_pagerank", {
        nodes: {"*": ["*"]},
        edges: {"*": ["*"]},
        direction: "undirected",
        load_id: true,
        update: "static",
        query: "query",
        default: false
      }).to("hdc-server-1")
      

      参数

      算法名:page_rank

      参数名
      类型
      规范
      默认值
      可选
      描述
      init_value Float >0 0.2 所有点的初始排名
      loop_num Integer ≥1 5 最大迭代轮数。算法将在完成所有轮次后停止
      damping Float (0,1) 0.8 阻尼系数
      weaken Integer 1, 2 1 设置为1时计算PageRank;设置为2时计算ArticleRank
      return_id_uuid String uuid, id, both uuid 在结果中使用_uuid_id或同时使用两者来表示点
      limit Integer ≥-1 -1 限制返回的结果数;-1返回所有结果
      order String asc, desc / 根据rank分值对结果排序

      文件回写

      CALL algo.page_rank.write("hdc_pagerank", {
        params: {
          return_id_uuid: "id",
          init_value: 1,
          loop_num: 50,
          damping: 0.8,
          weaken: 1,
          order: 'desc'
        },
        return_params: {
          file: {
            filename: "rank"
          }
        }
      })
      

      algo(page_rank).params({
        project: "hdc_pagerank",
        return_id_uuid: "id",
        init_value: 1,
        loop_num: 50,
        damping: 0.8,
        weaken: 1,
        order: 'desc'
      }).write({
        file: {
          filename: "rank"
        }
      })
      

      结果:

      _id,rank
      E,2.3906
      G,1.15624
      F,1.03774
      N,0.842146
      I,0.67812
      B,0.615097
      L,0.615097
      J,0.36
      C,0.333333
      A,0.333333
      H,0.333333
      M,0.28
      K,0.2
      D,0.2
      

      数据库回写

      将结果中的rank值写入指定点属性。该属性类型为float

      CALL algo.page_rank.write("hdc_pagerank", {
        params: {
          loop_num: 50,
          weaken: 1
        },
        return_params: {
          db: {
            property: "rank"
          }
        }
      })
      

      algo(page_rank).params({
        project: "hdc_pagerank",
        loop_num: 50,
        weaken: 1
      }).write({
        db:{ 
          property: 'rank'
        }
      })
      

      完整返回

      CALL algo.page_rank("hdc_pagerank", {
        params: {
          return_id_uuid: "id",    
          init_value: 1,
          loop_num: 50,
          damping: 0.8,
          weaken: 1,
          order: 'desc',
          limit: 5
        },
        return_params: {}
      }) YIELD PR
      RETURN PR
      

      exec{
        algo(page_rank).params({
          return_id_uuid: "id",    
          init_value: 1,
          loop_num: 50,
          damping: 0.8,
          weaken: 1,
          order: 'desc',
          limit: 5
        }) as PR
        return PR
      } on hdc_pagerank
      

      结果:

      _id rank
      E 2.390599
      G 1.15624
      F 1.037742
      N 0.842146
      I 0.67812

      流式返回

      CALL algo.page_rank("hdc_pagerank", {
        params: {
          return_id_uuid: "id",
          loop_num: 50,
          damping: 0.8,
          weaken: 1,
          order: 'desc',
          limit: 5
        },
        return_params: {
        	stream: {}
        }
      }) YIELD PR
      RETURN PR
      

      exec{
        algo(page_rank).params({
          return_id_uuid: "id",
          loop_num: 50,
          damping: 0.8,
          weaken: 1,
          order: 'desc',
          limit: 5
        }).stream() as PR
        return PR
      } on hdc_pagerank
      

      结果:

      _id rank
      E 2.390599
      G 1.15624
      F 1.037742
      N 0.842146
      I 0.67812

      在分布式投影上运行算法

      创建分布式投影

      将图集全部投影到shard服务器上并命名为dist_pagerank

      create().projection("dist_pagerank", {
        nodes: {"*": ["*"]}, 
        edges: {"*": ["*"]},
        direction: "undirected",
        load_id: true
      })
      

      参数

      算法名:page_rank

      参数名
      类型
      规范
      默认值
      可选
      描述
      init_value Float >0 0.2 所有点的初始排名
      loop_num Integer ≥1 10 最大迭代轮数。算法将在完成所有轮次后停止
      damping Float (0,1) 0.8 阻尼系数
      weaken Integer 1, 2 1 设置为1时计算PageRank;设置为2时计算ArticleRank
      limit Integer ≥-1 -1 限制返回的结果数;-1返回所有结果
      order String asc, desc / 根据rank分值对结果排序

      文件回写

      CALL algo.page_rank.write("dist_pagerank", {
        params: {
          init_value: 1,
          loop_num: 50,
          damping: 0.8,
          weaken: 1,
          order: "desc"
        },
        return_params: {
          file: {
            filename: "rank"
          }
        }
      })
      

      algo(page_rank).params({
        project: "dist_pagerank",
        init_value: 1,
        loop_num: 50,
        damping: 0.8,
        weaken: 1,
        order: "desc"
      }).write({
        file: {
          filename: "rank"
        }
      })
      

      结果:

      _id,rank
      E,2.4451734081316898184
      G,1.1753836278518499103
      F,1.072201237069960067
      N,0.86041240546502095743
      I,0.68769181392592604318
      B,0.62905439446913602453
      L,0.62905439446913602453
      J,0.35999999999999998668
      H,0.33350809599999997612
      A,0.33350809599999997612
      C,0.33350809599999997612
      M,0.28000000000000002665
      D,0.2000000000000000111
      K,0.2000000000000000111
      

      数据库回写

      将结果中的rank值写入指定点属性。该属性类型为double

      CALL algo.page_rank.write("dist_pagerank", {
        params: {
          loop_num: 50,
          weaken: 1
        },
        return_params: {
          db: {
            property: "rank"
          }
        }
      })
      

      algo(page_rank).params({
        project: "dist_pagerank",
        loop_num: 50,
        weaken: 1
      }).write({
        db:{ 
          property: 'rank'
        }
      })
      
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写