| /* ----------------------------------------------------------------------- *//** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| * |
| * |
| * @file graph.sql_in |
| * |
| * @brief SQL functions for graph analytics |
| * @date Nov 2016 |
| * |
| * @sa Provides various graph algorithms. |
| * |
| *//* ----------------------------------------------------------------------- */ |
| m4_include(`SQLCommon.m4') |
| |
| |
| /** |
| @addtogroup grp_pagerank |
| |
| <div class="toc"><b>Contents</b> |
| <ul> |
| <li><a href="#pagerank">PageRank</a></li> |
| <li><a href="#examples">Examples</a></li> |
| <li><a href="#notes">Notes</a></li> |
| <li><a href="#literature">Literature</a></li> |
| </ul> |
| </div> |
| |
| @brief Find the PageRank of all vertices in a directed graph. |
| |
| Given a graph, the PageRank algorithm outputs a probability distribution representing the |
| likelihood that a person randomly traversing the graph will arrive at any particular vertex. |
| This algorithm was originally used by Google to rank websites where the World Wide Web was |
| modeled as a directed graph with the vertices representing the websites. The PageRank |
| algorithm initially proposed by Larry Page and Sergey Brin is implemented here [1]. |
| |
| We also implement personalized PageRank, in which a notion of importance |
| provides personalization to a query. |
| For example, importance scores can be biased according |
| to a specified set of vertices in the graph that are of interest or special in some way [2]. |
| |
| @anchor pagerank |
| @par PageRank |
| <pre class="syntax"> |
| pagerank( vertex_table, |
| vertex_id, |
| edge_table, |
| edge_args, |
| out_table, |
| damping_factor, |
| max_iter, |
| threshold, |
| grouping_cols, |
| personalization_vertices |
| ) |
| </pre> |
| |
| \b Arguments |
| <dl class="arglist"> |
| <dt>vertex_table</dt> |
| <dd>TEXT. Name of the table containing the vertex data for the graph. Must contain the |
| column specified in the 'vertex_id' parameter below.</dd> |
| |
| <dt>vertex_id</dt> |
| <dd>TEXT, default = 'id'. Name of the column in 'vertex_table' containing |
| vertex ids. The vertex ids can be of type INTEGER or BIGINT with no duplicates. |
| They do not need to be contiguous.</dd> |
| |
| <dt>edge_table</dt> |
| <dd>TEXT. Name of the table containing the edge data. The edge table must |
| contain columns for source vertex and destination vertex.</dd> |
| |
| <dt>edge_args</dt> |
| <dd>TEXT. A comma-delimited string containing multiple named arguments of |
| the form "name=value". The following parameters are supported for |
| this string argument: |
| - src (INTEGER or BIGINT): Name of the column containing the source vertex ids in the edge table. |
| Default column name is 'src'. |
| - dest (INTEGER or BIGINT): Name of the column containing the destination vertex ids in the edge table. |
| Default column name is 'dest'.</dd> |
| |
| <dt>out_table</dt> |
| <dd>TEXT. Name of the table to store the result of PageRank. |
| It will contain a row for every vertex from 'vertex_table' with |
| the following columns: |
| - vertex_id : The id of a vertex. Will use the input parameter 'vertex_id' for column naming. |
| - pagerank : The vertex's PageRank. |
| - grouping_cols : Grouping column (if any) values associated with the vertex_id.</dd> |
| |
| A summary table is also created that contains information |
| regarding the number of iterations required for convergence. |
| It is named by adding the suffix '_summary' to the 'out_table' |
| parameter. |
| |
| <dt>damping_factor (optional)</dt> |
| <dd>FLOAT8, default 0.85. The probability, at any step, that a user will continue following the links in a random surfer model.</dd> |
| |
| <dt>max_iter (optional)</dt> |
| <dd>INTEGER, default: 100. The maximum number of iterations allowed.</dd> |
| |
| <dt>threshold (optional)</dt> |
| <dd>FLOAT8, default: (1/number of vertices * 1000). If the difference between the PageRank of every vertex of two consecutive |
| iterations is smaller than 'threshold', or the iteration number is larger than 'max_iter', the |
| computation stops. If you set the threshold to zero, then you will force the algorithm to run for the full number of iterations specified in 'max_iter'. |
| It is advisable to set threshold to a value lower than 1/(number of vertices in the graph) since the PageRank value of nodes is initialized to that |
| value.</dd> |
| |
| <dt>grouping_cols (optional)</dt> |
| <dd>TEXT, default: NULL. A single column or a list of comma-separated |
| columns that divides the input data into discrete groups, resulting in one |
| distribution per group. When this value is NULL, no grouping is used and |
| a single model is generated for all data. |
| @note Expressions are not currently supported for 'grouping_cols'.</dd> |
| |
| <dt> personalization_vertices (optional)</dt> |
| <dd>INTEGER[] or BIGINT[], default: NULL. A comma separated list of vertices or nodes |
| for personalized PageRank. When this parameter is provided, personalized PageRank |
| will run. In the absence of this parameter, regular PageRank will run. |
| </dl> |
| |
| @anchor examples |
| @examp |
| |
| -# Create vertex and edge tables to represent the graph: |
| <pre class="syntax"> |
| DROP TABLE IF EXISTS vertex, edge; |
| CREATE TABLE vertex( |
| id INTEGER |
| ); |
| CREATE TABLE edge( |
| src INTEGER, |
| dest INTEGER, |
| user_id INTEGER |
| ); |
| INSERT INTO vertex VALUES |
| (0), |
| (1), |
| (2), |
| (3), |
| (4), |
| (5), |
| (6); |
| INSERT INTO edge VALUES |
| (0, 1, 1), |
| (0, 2, 1), |
| (0, 4, 1), |
| (1, 2, 1), |
| (1, 3, 1), |
| (2, 3, 1), |
| (2, 5, 1), |
| (2, 6, 1), |
| (3, 0, 1), |
| (4, 0, 1), |
| (5, 6, 1), |
| (6, 3, 1), |
| (0, 1, 2), |
| (0, 2, 2), |
| (0, 4, 2), |
| (1, 2, 2), |
| (1, 3, 2), |
| (2, 3, 2), |
| (3, 0, 2), |
| (4, 0, 2), |
| (5, 6, 2), |
| (6, 3, 2); |
| </pre> |
| |
| -# Running PageRank with default values for optional parameters: |
| <pre class="syntax"> |
| DROP TABLE IF EXISTS pagerank_out, pagerank_out_summary; |
| SELECT madlib.pagerank( |
| 'vertex', -- Vertex table |
| 'id', -- Vertix id column |
| 'edge', -- Edge table |
| 'src=src, dest=dest', -- Comma delimted string of edge arguments |
| 'pagerank_out'); -- Output table of PageRank |
| SELECT * FROM pagerank_out ORDER BY pagerank DESC; |
| </pre> |
| <pre class="result"> |
| id | pagerank |
| ----+------------------- |
| 0 | 0.28753749341184 |
| 3 | 0.21016988901855 |
| 2 | 0.14662683454062 |
| 4 | 0.10289614384217 |
| 1 | 0.10289614384217 |
| 6 | 0.09728637768887 |
| 5 | 0.05258711765692 |
| (7 rows) |
| </pre> |
| <pre class="syntax"> |
| SELECT * FROM pagerank_out_summary; |
| </pre> |
| <pre class="result"> |
| __iterations__ |
| ----------------+ |
| 16 |
| (1 row) |
| </pre> |
| |
| -# Running PageRank with a damping factor of 0.5 results in different final values: |
| <pre class="syntax"> |
| DROP TABLE IF EXISTS pagerank_out, pagerank_out_summary; |
| SELECT madlib.pagerank( |
| 'vertex', -- Vertex table |
| 'id', -- Vertix id column |
| 'edge', -- Edge table |
| 'src=src, dest=dest', -- Comma delimted string of edge arguments |
| 'pagerank_out', -- Output table of PageRank |
| 0.5); -- Damping factor |
| SELECT * FROM pagerank_out ORDER BY pagerank DESC; |
| </pre> |
| <pre class="result"> |
| id | pagerank |
| ----+-------------------- |
| 0 | 0.225477161441199 |
| 3 | 0.199090328586664 |
| 2 | 0.136261327206477 |
| 6 | 0.132691559968224 |
| 4 | 0.109009291409508 |
| 1 | 0.109009291409508 |
| 5 | 0.0884610399788161 |
| (7 rows) |
| </pre> |
| |
| -# Now compute the PageRank of vertices associated with each user |
| using the grouping feature: |
| <pre class="syntax"> |
| DROP TABLE IF EXISTS pagerank_out, pagerank_out_summary; |
| SELECT madlib.pagerank( |
| 'vertex', -- Vertex table |
| 'id', -- Vertix id column |
| 'edge', -- Edge table |
| 'src=src, dest=dest', -- Comma delimted string of edge arguments |
| 'pagerank_out', -- Output table of PageRank |
| NULL, -- Default damping factor (0.85) |
| NULL, -- Default max iters (100) |
| 0.00000001, -- Threshold |
| 'user_id'); -- Grouping column name |
| SELECT * FROM pagerank_out ORDER BY user_id, pagerank DESC; |
| </pre> |
| <pre class="result"> |
| user_id | id | pagerank |
| ---------+----+-------------------- |
| 1 | 0 | 0.27825488388552 |
| 1 | 3 | 0.20188114667075 |
| 1 | 2 | 0.14288112346059 |
| 1 | 6 | 0.11453637832147 |
| 1 | 1 | 0.10026745615438 |
| 1 | 4 | 0.10026745615438 |
| 1 | 5 | 0.06191155535288 |
| 2 | 0 | 0.31854625004173 |
| 2 | 3 | 0.23786686773343 |
| 2 | 2 | 0.15914876489397 |
| 2 | 1 | 0.11168334437971 |
| 2 | 4 | 0.11168334437971 |
| 2 | 6 | 0.03964285714285 |
| 2 | 5 | 0.02142857142857 |
| (14 rows) |
| </pre> |
| <pre class="syntax"> |
| SELECT * FROM pagerank_out_summary ORDER BY user_id; |
| </pre> |
| <pre class="result"> |
| user_id | __iterations__ |
| ---------+---------------- |
| 1 | 27 |
| 2 | 31 |
| (2 rows) |
| </pre> |
| |
| -# Personalized PageRank. Here we specify {2,4} |
| as the personalization vertices. This parameter |
| could be specified as ARRAY[2,4] as well. |
| <pre class="syntax"> |
| DROP TABLE IF EXISTS pagerank_out, pagerank_out_summary; |
| SELECT madlib.pagerank( |
| 'vertex', -- Vertex table |
| 'id', -- Vertix id column |
| 'edge', -- Edge table |
| 'src=src, dest=dest', -- Comma delimted string of edge arguments |
| 'pagerank_out', -- Output table of PageRank |
| NULL, -- Default damping factor (0.85) |
| NULL, -- Default max iters (100) |
| NULL, -- Default Threshold |
| NULL, -- No Grouping |
| '{2,4}'); -- Personalization vertices |
| SELECT * FROM pagerank_out ORDER BY pagerank DESC; |
| </pre> |
| <pre class="result"> |
| id | pagerank |
| ----+-------------------- |
| 0 | 0.565232961966315 |
| 2 | 0.378139420991773 |
| 3 | 0.355003292266017 |
| 4 | 0.310111215897626 |
| 1 | 0.160111215897626 |
| 6 | 0.148615315574136 |
| 5 | 0.0803403307142321 |
| (7 rows) |
| </pre> |
| <pre class="syntax"> |
| SELECT * FROM pagerank_out_summary; |
| </pre> |
| <pre class="result"> |
| __iterations__ |
| ----------------+ |
| 37 |
| (1 row) |
| </pre> |
| |
| @anchor notes |
| @par Notes |
| |
| 1. On a Greenplum cluster, the edge table should be distributed |
| by the source vertex id column for better performance. |
| |
| @anchor literature |
| @par Literature |
| |
| [1] Brin, S. and Page, L. (1998), "The anatomy of a large-scale hypertextual Web search engine", |
| Computer Networks and ISDN Systems. 30: 107–117, |
| http://infolab.stanford.edu/pub/papers/google.pdf |
| |
| [2] Jeh, Glen and Widom, Jennifer. "Scaling Personalized Web Search", |
| Proceedings of the 12th international conference on World Wide Web, Pages 271-279 |
| Budapest, Hungary, May 20-24, 2003, |
| http://ilpubs.stanford.edu:8090/530/1/2002-12.pdf |
| */ |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pagerank( |
| vertex_table TEXT, |
| vertex_id TEXT, |
| edge_table TEXT, |
| edge_args TEXT, |
| out_table TEXT, |
| damping_factor FLOAT8, |
| max_iter INTEGER, |
| threshold FLOAT8, |
| grouping_cols VARCHAR, |
| personalization_vertices BIGINT[] |
| ) RETURNS VOID AS $$ |
| PythonFunction(graph, pagerank, pagerank) |
| $$ LANGUAGE plpythonu VOLATILE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `'); |
| ------------------------------------------------------------------------- |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pagerank( |
| vertex_table TEXT, |
| vertex_id TEXT, |
| edge_table TEXT, |
| edge_args TEXT, |
| out_table TEXT, |
| damping_factor FLOAT8, |
| max_iter INTEGER, |
| threshold FLOAT8, |
| grouping_cols VARCHAR |
| ) RETURNS VOID AS $$ |
| SELECT MADLIB_SCHEMA.pagerank($1, $2, $3, $4, $5, $6, $7, $8, $9, NULL) |
| $$ LANGUAGE SQL |
| m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); |
| ------------------------------------------------------------------------- |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pagerank( |
| vertex_table TEXT, |
| vertex_id TEXT, |
| edge_table TEXT, |
| edge_args TEXT, |
| out_table TEXT, |
| damping_factor FLOAT8, |
| max_iter INTEGER, |
| threshold FLOAT8 |
| ) RETURNS VOID AS $$ |
| SELECT MADLIB_SCHEMA.pagerank($1, $2, $3, $4, $5, $6, $7, $8, NULL, NULL) |
| $$ LANGUAGE SQL |
| m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); |
| ------------------------------------------------------------------------- |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pagerank( |
| vertex_table TEXT, |
| vertex_id TEXT, |
| edge_table TEXT, |
| edge_args TEXT, |
| out_table TEXT, |
| damping_factor FLOAT8, |
| max_iter INTEGER |
| ) RETURNS VOID AS $$ |
| SELECT MADLIB_SCHEMA.pagerank($1, $2, $3, $4, $5, $6, $7, NULL, NULL, NULL) |
| $$ LANGUAGE SQL |
| m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); |
| ------------------------------------------------------------------------- |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pagerank( |
| vertex_table TEXT, |
| vertex_id TEXT, |
| edge_table TEXT, |
| edge_args TEXT, |
| out_table TEXT, |
| damping_factor FLOAT8 |
| ) RETURNS VOID AS $$ |
| SELECT MADLIB_SCHEMA.pagerank($1, $2, $3, $4, $5, $6, 100, NULL, NULL, NULL) |
| $$ LANGUAGE SQL |
| m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); |
| ------------------------------------------------------------------------- |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pagerank( |
| vertex_table TEXT, |
| vertex_id TEXT, |
| edge_table TEXT, |
| edge_args TEXT, |
| out_table TEXT |
| ) RETURNS VOID AS $$ |
| SELECT MADLIB_SCHEMA.pagerank($1, $2, $3, $4, $5, 0.85, 100, NULL, NULL, NULL) |
| $$ LANGUAGE SQL |
| m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); |
| ------------------------------------------------------------------------- |
| |
| -- Online help |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pagerank( |
| message VARCHAR |
| ) RETURNS VARCHAR AS $$ |
| PythonFunction(graph, pagerank, pagerank_help) |
| $$ LANGUAGE plpythonu IMMUTABLE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `'); |
| |
| -------------------------------------------------------------------------------- |
| |
| CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pagerank() |
| RETURNS VARCHAR AS $$ |
| SELECT MADLIB_SCHEMA.pagerank(''); |
| $$ LANGUAGE sql IMMUTABLE |
| m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `'); |
| -------------------------------------------------------------------------------- |
