How PageRank Powers Trust Scoring: Theory, Example, and Graphene Implementation

PageRank Overview

PageRank is a link‑analysis algorithm created by Google to evaluate the reliability and importance of web pages. It is based on two assumptions: the more inbound links a page has, the higher its importance, and high‑quality inbound links contribute more weight.

Simplified Formula

In the formula, L(v) denotes the number of outgoing links of page v , PR(v) is the PageRank value of v , and Bu represents the set of inbound links to page u . The PageRank of a page is the sum of the PageRank values of all pages linking to it.

Damping Factor

To avoid rank sink problems where pages have only inbound links, a damping factor d (commonly 0.85) is introduced to simulate random jumps. The revised formula is:

Graphene Implementation of PageRank

Graphene, developed by Transwarp, is a distributed graph‑computing platform designed for large‑scale graph data such as web graphs, social networks, and knowledge graphs. It provides a ready‑made graph_pagerank() function that abstracts the parallel computation details.

Operation Steps

Data preparation: collect trust‑relationship data and store it as an edge list in HDFS, then create an external table to read the list.

DROP TABLE IF EXISTS credit_data;
CREATE EXTERNAL TABLE credit_data(src int, dst int)
ROW FORMAT DELIMITED FIELDS TERMINATED BY '\t'
LOCATION '/tmp/graphsql/credit_data';
DROP TABLE IF EXISTS pagerank_credit_data_result;
CREATE TABLE pagerank_credit_data_result (vertex int, rank double);
INSERT OVERWRITE TABLE pagerank_credit_data_result
SELECT graph_pagerank(src,dst) FROM credit_data;
INSERT OVERWRITE LOCAL DIRECTORY '/tmp/D_pagerank_credit_data_result'
SELECT * FROM pagerank_credit_data_result ORDER BY rank DESC;

Trust‑score calculation: execute graph_pagerank() with optional parameters (half, factor, iters) to obtain each member’s “integrity index”.

Result collection: the platform writes the (vertex, rank) pairs to a local directory; the top ranks correspond to the most trustworthy members (e.g., IDs 92 and 99 in the example).

Function signature:

graph_pagerank(vertex_caller, vertex_callee [, half = false] [, factor = 0.85] [, iters = 10])

Parameters:

vertex_caller : source node column (primitive type).

vertex_callee : target node column.

half : set true for undirected graphs with only one direction stored.

factor : damping factor (0 ≤ factor ≤ 1, default 0.85).

iters : number of iterations (default 10).

Performance Evaluation

Tests on SNAP datasets (scaled multiples of the Facebook graph) show that Graphene’s PageRank runtime grows linearly with edge count, demonstrating efficient handling of massive graphs. Compared with Spark GraphX and Facebook Giraph on a 33.5 GB, 6.5 M‑vertex, 1.8 B‑edge Friendster dataset, Graphene completed ten iterations while the other platforms ran out of memory.