391      阿里云  技术社区[云栖]

网络分析__使用手册(new)_机器学习-阿里云

目录

• k-Core

• 单源最短路径

• PageRank

• 标签传播聚类

• 标签传播分类

• Modularity

• 最大联通子图

• 点聚类系数

• 边聚类系数

• 计数三角形

• 树深度

网络分析栏提供的都是基于Graph数据结构的分析算法；下图是使用平台网络分析组件构建的一个分析流程实例：

网络分析栏的算法组件都需要设置运行参数，参数说明如下：进程数：参数代号workerNum，用于设置作业并行执行的节点数；数字越大并行度越高，但框架通讯开销会增大。进程内存：参数代号workerMem，用于设置单个 worker可使用的最大内存量，默认每个worker分配4096内存；实际使用内存超过该值，会抛出OutOfMemory异常。

k-Core

功能介绍

• 一个图的KCore是指反复去除度小于或等于k的节点后，所剩余的子图。若一个节点存在于KCore，而在(K+1)CORE中被移去，那么此节点的核数（coreness）为k。因此所有度为1的节点的核数必然为0，节点核数的最大值被称为图的核数。

参数设置

k：核数的值，必填，默认3

实例

测试数据

新建数据SQL

drop table if exists KCore_func_test_edge;
create table KCore_func_test_edge as
select * from
(
  select '1' as flow_out_id,'2' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'3' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'4' as flow_in_id from dual
  union all
  select '2' as flow_out_id,'3' as flow_in_id from dual
  union all
  select '2' as flow_out_id,'4' as flow_in_id from dual
  union all
  select '3' as flow_out_id,'4' as flow_in_id from dual
  union all
  select '3' as flow_out_id,'5' as flow_in_id from dual
  union all
  select '3' as flow_out_id,'6' as flow_in_id from dual
  union all
  select '5' as flow_out_id,'6' as flow_in_id from dual
)tmp;

数据对应的graph结构如下图：

运行结果

设定k = 2：运行结果：结果如下：

+-------+-------+
| node1 | node2 |
+-------+-------+
| 1     | 2     |
| 1     | 3     |
| 1     | 4     |
| 2     | 1     |
| 2     | 3     |
| 2     | 4     |
| 3     | 1     |
| 3     | 2     |
| 3     | 4     |
| 4     | 1     |
| 4     | 2     |
| 4     | 3     |
+-------+-------+

pai命令示例

pai -name KCore
    -project algo_public
    -DinputEdgeTableName=KCore_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=KCore_func_test_result
    -Dk=2;

算法参数

单源最短路径

功能介绍

• 单源最短路径参考Dijkstra算法，本算法中当给定起点，则输出该点和其他所有节点的最短路径。

参数设置

起始节点id：用于计算最短路径的起始节点，必填

实例

测试数据

新建数据的SQL语句：

drop table if exists SSSP_func_test_edge;
create table SSSP_func_test_edge as
select
    flow_out_id,flow_in_id,edge_weight
from
(
    select "a" as flow_out_id,"b" as flow_in_id,1.0 as edge_weight from dual
    union all
    select "b" as flow_out_id,"c" as flow_in_id,2.0 as edge_weight from dual
    union all
    select "c" as flow_out_id,"d" as flow_in_id,1.0 as edge_weight from dual
    union all
    select "b" as flow_out_id,"e" as flow_in_id,2.0 as edge_weight from dual
    union all
    select "e" as flow_out_id,"d" as flow_in_id,1.0 as edge_weight from dual
    union all
    select "c" as flow_out_id,"e" as flow_in_id,1.0 as edge_weight from dual
    union all
    select "f" as flow_out_id,"g" as flow_in_id,3.0 as edge_weight from dual
    union all
    select "a" as flow_out_id,"d" as flow_in_id,4.0 as edge_weight from dual
) tmp
;

数据对应的graph结构：

运行结果

结果如下：
+------------+------------+------------+--------------+
| start_node | dest_node  | distance   | distance_cnt | 
+------------+------------+------------+--------------+
| a          | b          | 1.0        | 1            |
| a          | c          | 3.0        | 1            |
| a          | d          | 4.0        | 3            |
| a          | a          | 0.0        | 0            |
| a          | e          | 3.0        | 1            |
+------------+------------+------------+--------------+

pai命令示例

pai -name SSSP
    -project algo_public
    -DinputEdgeTableName=SSSP_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=SSSP_func_test_result
    -DhasEdgeWeight=true
    -DedgeWeightCol=edge_weight
    -DstartVertex=a;

算法参数

PageRank

功能介绍

• PageRank起于网页的搜索排序，google利用网页的链接结构计算每个网页的等级排名，其基本思路是：如果一个网页被其他多个网页指向，这说明该网页比较重要或者质量较高。除考虑网页的链接数量，还考虑网页本身的权重级别，以及该网页有多少条出链到其它网页。 对于用户构成的人际网络，除了用户本身的影响力之外，边的权重也是重要因素之一。例如：新浪微博的某个用户，会更容易影响粉丝中关系比较亲密的家人、同学、同事等，而对陌生的弱关系粉丝影响较小。在人际网络中，边的权重等价为用户-用户的关系强弱指数。带连接权重的PageRank公式为：其中，w(i)为节点i的权重，c(A,i)为链接权重，d为阻尼系数，算法迭代稳定后的节点权重W即为每个用户的影响力指数。

参数设置

最大迭代次数：算法自身会收敛并停止迭代，选填，默认30

实例

测试数据

新建数据的SQL语句：

drop table if exists PageRankWithWeight_func_test_edge;
create table PageRankWithWeight_func_test_edge as
select * from
(
    select 'a' as flow_out_id,'b' as flow_in_id,1.0 as weight from dual
    union all
    select 'a' as flow_out_id,'c' as flow_in_id,1.0 as weight from dual
    union all
    select 'b' as flow_out_id,'c' as flow_in_id,1.0 as weight from dual
    union all
    select 'b' as flow_out_id,'d' as flow_in_id,1.0 as weight from dual
    union all
    select 'c' as flow_out_id,'d' as flow_in_id,1.0 as weight from dual
)tmp
;

对应的graph结构：

运行结果

结果如下：
+------+------------+
| node | weight     |
+------+------------+
| a    | 0.0375     |
| b    | 0.06938    |
| c    | 0.12834    |
| d    | 0.20556    |
+------+------------+

pai命令示例

pai -name PageRankWithWeight
    -project algo_public
    -DinputEdgeTableName=PageRankWithWeight_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=PageRankWithWeight_func_test_result
    -DhasEdgeWeight=true
    -DedgeWeightCol=weight
    -DmaxIter 100;

算法参数

标签传播聚类

功能介绍

图聚类是根据图的拓扑结构，进行子图的划分，使得子图内部节点的链接较多，子图之间的连接较少。标签传播算法（Label Propagation Algorithm, LPA）是基于图的半监督学习方法，其基本思路是节点的标签（community）依赖其邻居节点的标签信息，影响程度由节点相似度决定，并通过传播迭代更新达到稳定。

参数介绍

最大迭代次数：选填，默认30

实例

测试数据

数据生成SQL:

drop table if exists LabelPropagationClustering_func_test_edge;
create table LabelPropagationClustering_func_test_edge as
select * from
(
    select '1' as flow_out_id,'2' as flow_in_id,0.7 as edge_weight from dual
    union all
    select '1' as flow_out_id,'3' as flow_in_id,0.7 as edge_weight from dual
    union all
    select '1' as flow_out_id,'4' as flow_in_id,0.6 as edge_weight from dual
    union all
    select '2' as flow_out_id,'3' as flow_in_id,0.7 as edge_weight from dual
    union all
    select '2' as flow_out_id,'4' as flow_in_id,0.6 as edge_weight from dual
    union all
    select '3' as flow_out_id,'4' as flow_in_id,0.6 as edge_weight from dual
    union all
    select '4' as flow_out_id,'6' as flow_in_id,0.3 as edge_weight from dual
    union all
    select '5' as flow_out_id,'6' as flow_in_id,0.6 as edge_weight from dual
    union all
    select '5' as flow_out_id,'7' as flow_in_id,0.7 as edge_weight from dual
    union all
    select '5' as flow_out_id,'8' as flow_in_id,0.7 as edge_weight from dual
    union all
    select '6' as flow_out_id,'7' as flow_in_id,0.6 as edge_weight from dual
    union all
    select '6' as flow_out_id,'8' as flow_in_id,0.6 as edge_weight from dual
    union all
    select '7' as flow_out_id,'8' as flow_in_id,0.7 as edge_weight from dual
)tmp
;
drop table if exists LabelPropagationClustering_func_test_node;
create table LabelPropagationClustering_func_test_node as
select * from
(
    select '1' as node,0.7 as node_weight from dual
    union all
    select '2' as node,0.7 as node_weight from dual
    union all
    select '3' as node,0.7 as node_weight from dual
    union all
    select '4' as node,0.5 as node_weight from dual
    union all
    select '5' as node,0.7 as node_weight from dual
    union all
    select '6' as node,0.5 as node_weight from dual
    union all
    select '7' as node,0.7 as node_weight from dual
    union all
    select '8' as node,0.7 as node_weight from dual
)tmp
;

数据对应的group结构：

+------+------------+
| node | group_id   |
+------+------------+
| 1    | 1          |
| 2    | 1          |
| 3    | 1          |
| 4    | 1          |
| 5    | 5          |
| 6    | 5          |
| 7    | 5          |
| 8    | 5          |
+------+------------+

pai -name LabelPropagationClustering
    -project algo_public
    -DinputEdgeTableName=LabelPropagationClustering_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DinputVertexTableName=LabelPropagationClustering_func_test_node
    -DvertexCol=node
    -DoutputTableName=LabelPropagationClustering_func_test_result
    -DhasEdgeWeight=true
    -DedgeWeightCol=edge_weight
    -DhasVertexWeight=true
    -DvertexWeightCol=node_weight
    -DrandSelect=true
    -DmaxIter=100;

drop table if exists LabelPropagationClassification_func_test_edge;
create table LabelPropagationClassification_func_test_edge as
select * from
(
    select 'a' as flow_out_id, 'b' as flow_in_id, 0.2 as edge_weight from dual
    union all
    select 'a' as flow_out_id, 'c' as flow_in_id, 0.8 as edge_weight from dual
    union all
    select 'b' as flow_out_id, 'c' as flow_in_id, 1.0 as edge_weight from dual
    union all
    select 'd' as flow_out_id, 'b' as flow_in_id, 1.0 as edge_weight from dual
)tmp
;
drop table if exists LabelPropagationClassification_func_test_node;
create table LabelPropagationClassification_func_test_node as
select * from
(
    select 'a' as node,'X' as label, 1.0 as label_weight from dual
    union all
    select 'd' as node,'Y' as label, 1.0 as label_weight from dual
)tmp
;

结果如下：
+------+-----+------------+
| node | tag | weight     |
+------+-----+------------+
| a    | X   | 1.0        |
| b    | X   | 0.16667    |
| b    | Y   | 0.83333    |
| c    | X   | 0.53704    |
| c    | Y   | 0.46296    |
| d    | Y   | 1.0        |
+------+-----+------------+

pai -name LabelPropagationClassification
    -project algo_public
    -DinputEdgeTableName=LabelPropagationClassification_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DinputVertexTableName=LabelPropagationClassification_func_test_node
    -DvertexCol=node
    -DvertexLabelCol=label
    -DoutputTableName=LabelPropagationClassification_func_test_result
    -DhasEdgeWeight=true
    -DedgeWeightCol=edge_weight
    -DhasVertexWeight=true
    -DvertexWeightCol=label_weight
    -Dalpha=0.8
    -Depsilon=0.000001;

结果如下：
+--------------+
| val          |
+--------------+
| 0.4230769    |
+--------------+

pai -name Modularity
    -project algo_public
    -DinputEdgeTableName=Modularity_func_test_edge
    -DfromVertexCol=flow_out_id
    -DfromGroupCol=group_out_id
    -DtoVertexCol=flow_in_id
    -DtoGroupCol=group_in_id
    -DoutputTableName=Modularity_func_test_result;

drop table if exists MaximalConnectedComponent_func_test_edge;
create table MaximalConnectedComponent_func_test_edge as
select * from
(
  select '1' as flow_out_id,'2' as flow_in_id from dual
  union all
  select '2' as flow_out_id,'3' as flow_in_id from dual
  union all
  select '3' as flow_out_id,'4' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'4' as flow_in_id from dual
  union all
  select 'a' as flow_out_id,'b' as flow_in_id from dual
  union all
  select 'b' as flow_out_id,'c' as flow_in_id from dual
)tmp;
drop table if exists MaximalConnectedComponent_func_test_result;
create table MaximalConnectedComponent_func_test_result
(
  node string,
  grp_id string
);

结果如下：
+-------+-------+
| node  | grp_id|
+-------+-------+
| 1     | 4     |
| 2     | 4     |
| 3     | 4     |
| 4     | 4     |
| a     | c     |
| b     | c     |
| c     | c     |
+-------+-------+

pai -name MaximalConnectedComponent 
    -project algo_public 
    -DinputEdgeTableName=MaximalConnectedComponent_func_test_edge 
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id 
    -DoutputTableName=MaximalConnectedComponent_func_test_result;

drop table if exists NodeDensity_func_test_edge;
create table NodeDensity_func_test_edge as
select * from
(
  select '1' as flow_out_id, '2' as flow_in_id from dual
  union all
  select '1' as flow_out_id, '3' as flow_in_id from dual
  union all
  select '1' as flow_out_id, '4' as flow_in_id from dual
  union all
  select '1' as flow_out_id, '5' as flow_in_id from dual
  union all
  select '1' as flow_out_id, '6' as flow_in_id from dual
  union all
  select '2' as flow_out_id, '3' as flow_in_id from dual
  union all
  select '3' as flow_out_id, '4' as flow_in_id from dual
  union all
  select '4' as flow_out_id, '5' as flow_in_id from dual
  union all
  select '5' as flow_out_id, '6' as flow_in_id from dual
  union all
  select '5' as flow_out_id, '7' as flow_in_id from dual
  union all
  select '6' as flow_out_id, '7' as flow_in_id from dual
)tmp;
drop table if exists NodeDensity_func_test_result;
create table NodeDensity_func_test_result
(
  node string,
  node_cnt bigint,
  edge_cnt bigint,
  density double,
  log_density double
);

结果如下：
1,5,4,0.4,1.45657
2,2,1,1.0,1.24696
3,3,2,0.66667,1.35204
4,3,2,0.66667,1.35204
5,4,3,0.5,1.41189
6,3,2,0.66667,1.35204
7,2,1,1.0,1.24696

pai -name NodeDensity
    -project algo_public
    -DinputEdgeTableName=NodeDensity_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=NodeDensity_func_test_result
    -DmaxEdgeCnt=500;

drop table if exists EdgeDensity_func_test_edge;
create table EdgeDensity_func_test_edge as
select * from
(
  select '1' as flow_out_id,'2' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'3' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'5' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'7' as flow_in_id from dual
  union all
  select '2' as flow_out_id,'5' as flow_in_id from dual
  union all
  select '2' as flow_out_id,'4' as flow_in_id from dual
  union all
  select '2' as flow_out_id,'3' as flow_in_id from dual
  union all
  select '3' as flow_out_id,'5' as flow_in_id from dual
  union all
  select '3' as flow_out_id,'4' as flow_in_id from dual
  union all
  select '4' as flow_out_id,'5' as flow_in_id from dual
  union all
  select '4' as flow_out_id,'8' as flow_in_id from dual
  union all
  select '5' as flow_out_id,'6' as flow_in_id from dual
  union all
  select '5' as flow_out_id,'7' as flow_in_id from dual
  union all
  select '5' as flow_out_id,'8' as flow_in_id from dual
  union all
  select '7' as flow_out_id,'6' as flow_in_id from dual
  union all
  select '6' as flow_out_id,'8' as flow_in_id from dual
)tmp;
drop table if exists EdgeDensity_func_test_result;
create table EdgeDensity_func_test_result
(
  node1 string,
  node2 string,
  node1_edge_cnt bigint,
  node2_edge_cnt bigint,
  triangle_cnt bigint,
  density double
);

结果如下：
1,2,4,4,2,0.5
2,3,4,4,3,0.75
2,5,4,7,3,0.75
3,1,4,4,2,0.5
3,4,4,4,2,0.5
4,2,4,4,2,0.5
4,5,4,7,3,0.75
5,1,7,4,3,0.75
5,3,7,4,3,0.75
5,6,7,3,2,0.66667
5,8,7,3,2,0.66667
6,7,3,3,1,0.33333
7,1,3,4,1,0.33333
7,5,3,7,2,0.66667
8,4,3,4,1,0.33333
8,6,3,3,1,0.33333

pai -name EdgeDensity
    -project algo_public
    -DinputEdgeTableName=EdgeDensity_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=EdgeDensity_func_test_result;

drop table if exists TriangleCount_func_test_edge;
create table TriangleCount_func_test_edge as
select * from
(
  select '1' as flow_out_id,'2' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'3' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'4' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'5' as flow_in_id from dual
  union all
  select '1' as flow_out_id,'6' as flow_in_id from dual
  union all
  select '2' as flow_out_id,'3' as flow_in_id from dual
  union all
  select '3' as flow_out_id,'4' as flow_in_id from dual
  union all
  select '4' as flow_out_id,'5' as flow_in_id from dual
  union all
  select '5' as flow_out_id,'6' as flow_in_id from dual
  union all
  select '5' as flow_out_id,'7' as flow_in_id from dual
  union all
  select '6' as flow_out_id,'7' as flow_in_id from dual
)tmp;
drop table if exists TriangleCount_func_test_result;
create table TriangleCount_func_test_result
(
  node1 string,
  node2 string,
  node3 string
);

结果如下：
1,2,3
1,3,4
1,4,5
1,5,6
5,6,7

pai -name TriangleCount
    -project algo_public
    -DinputEdgeTableName=TriangleCount_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=TriangleCount_func_test_result;

drop table if exists TreeDepth_func_test_edge;
create table TreeDepth_func_test_edge as
select * from
(
    select '0' as flow_out_id, '1' as flow_in_id from dual
    union all
    select '0' as flow_out_id, '2' as flow_in_id from dual
    union all
    select '1' as flow_out_id, '3' as flow_in_id from dual
    union all
    select '1' as flow_out_id, '4' as flow_in_id from dual
    union all
    select '2' as flow_out_id, '4' as flow_in_id from dual
    union all
    select '2' as flow_out_id, '5' as flow_in_id from dual
    union all
    select '4' as flow_out_id, '6' as flow_in_id from dual
    union all
    select 'a' as flow_out_id, 'b' as flow_in_id from dual
    union all
    select 'a' as flow_out_id, 'c' as flow_in_id from dual
    union all
    select 'c' as flow_out_id, 'd' as flow_in_id from dual
    union all
    select 'c' as flow_out_id, 'e' as flow_in_id from dual
)tmp;
drop table if exists TreeDepth_func_test_result;
create table TreeDepth_func_test_result
(
  node string,
  root string,
  depth bigint
);

结果如下：
0,0,0
1,0,1
2,0,1
3,0,2
4,0,2
5,0,2
6,0,3
a,a,0
b,a,1
c,a,1
d,a,2
e,a,2

pai -name TreeDepth
    -project algo_public
    -DinputEdgeTableName=TreeDepth_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DoutputTableName=TreeDepth_func_test_result;