最大連通子圖算法用于識別無向圖中最大的連通部分,即圖中最大的節點集合,其中任意兩節點間都可通過路徑相連。該算法常用于網絡分析、圖像處理等領域。它通過深度優先搜索(DFS)或廣度優先搜索(BFS)來遍歷圖,識別所有連通組件,再從中找出包含節點最多的子圖。
配置組件
方法一:可視化方式
在Designer工作流頁面添加最大連通子圖組件,并在界面右側配置相關參數:
參數類型 | 參數 | 描述 |
字段設置 | 起始節點 | 邊表的起點所在列。 |
結束節點 | 邊表的終點所在列。 | |
執行調優 | 進程數量 | 作業并行執行的節點數。數字越大并行度越高,但是框架通訊開銷會增大。 |
進程內存 | 單個作業可使用的最大內存量,單位:MB,默認值為4096。 如果實際使用內存超過該值,會拋出 | |
數據切分大小 | 數據切分的大小,單位:MB,默認值為64。 |
方法二:PAI命令方式
使用PAI命令配置最大連通子圖組件參數。您可以使用SQL腳本組件進行PAI命令調用,詳情請參見場景4:在SQL腳本組件中執行PAI命令。
PAI -name MaximalConnectedComponent
-project algo_public
-DinputEdgeTableName=MaximalConnectedComponent_func_test_edge
-DfromVertexCol=flow_out_id
-DtoVertexCol=flow_in_id
-DoutputTableName=MaximalConnectedComponent_func_test_result;
參數 | 是否必選 | 默認值 | 描述 |
inputEdgeTableName | 是 | 無 | 輸入邊表名。 |
inputEdgeTablePartitions | 否 | 全表讀入 | 輸入邊表的分區。 |
fromVertexCol | 是 | 無 | 輸入邊表的起點所在列。 |
toVertexCol | 是 | 無 | 輸入邊表的終點所在列。 |
outputTableName | 是 | 無 | 輸出表名。 |
outputTablePartitions | 否 | 無 | 輸出表的分區。 |
lifecycle | 否 | 無 | 輸出表的生命周期。 |
workerNum | 否 | 未設置 | 作業并行執行的節點數。數字越大并行度越高,但是框架通訊開銷會增大。 |
workerMem | 否 | 4096 | 單個作業可使用的最大內存量,單位:MB,默認值為4096。 如果實際使用內存超過該值,會拋出 |
splitSize | 否 | 64 | 數據切分的大小,單位:MB。 |
使用示例
添加SQL腳本組件,輸入以下SQL語句生成訓練數據。
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 union all select '2' as flow_out_id,'3' as flow_in_id union all select '3' as flow_out_id,'4' as flow_in_id union all select '1' as flow_out_id,'4' as flow_in_id union all select 'a' as flow_out_id,'b' as flow_in_id union all select 'b' as flow_out_id,'c' as flow_in_id )tmp; drop table if exists MaximalConnectedComponent_func_test_result; create table MaximalConnectedComponent_func_test_result ( node string, grp_id string );
對應的數據結構圖:
添加SQL腳本組件,輸入以下PAI命令進行訓練。
drop table if exists ${o1}; PAI -name MaximalConnectedComponent -project algo_public -DinputEdgeTableName=MaximalConnectedComponent_func_test_edge -DfromVertexCol=flow_out_id -DtoVertexCol=flow_in_id -DoutputTableName=${o1};
右擊上一步的組件,選擇查看數據 > SQL腳本的輸出,查看訓練結果。
| node1 | grp_id | | ----- | ------ | | a | c | | b | c | | c | c | | 1 | 4 | | 2 | 4 | | 3 | 4 | | 4 | 4 |