基于矩阵与向量的PageRank数据查询函数实现技术咨询

Alright, let's build that PageRank function you're working on. I’ll break this down into clear, actionable steps so you can follow along and understand each part. We’ll use Python (with NumPy for efficient matrix operations) since it’s the go-to for this kind of task, but I’ll note how to adjust if you can’t use NumPy.

Step 1: Identify all unique nodes (states) #

First, we need to know how many distinct nodes we’re dealing with. Your edges list includes nodes 0 through 6, so we’ll have 7 states total. To make this code work for any edge list (even if nodes aren’t consecutive), we’ll extract all unique nodes from the edges:

def get_unique_nodes(edges):
    nodes = set()
    for from_node, to_node in edges:
        nodes.add(from_node)
        nodes.add(to_node)
    return sorted(nodes)

We’ll also create a quick mapping from node number to index (useful if nodes aren’t 0-based and continuous):

nodes = get_unique_nodes(edges)
N = len(nodes)
node_to_idx = {node: idx for idx, node in enumerate(nodes)}

Step 2: Build the base transition matrix #

The base transition matrix M captures raw link-following probabilities without accounting for random jumps. For each node, we first count its out-degree (how many outgoing edges it has), then assign equal probability to each outgoing edge. We also handle dangling nodes (nodes with no outgoing edges) by having them jump uniformly to all nodes:

import numpy as np

def build_transition_matrix(edges, nodes, node_to_idx):
    N = len(nodes)
    transition_matrix = np.zeros((N, N))
    out_degree = {node: 0 for node in nodes}

    # Count outgoing edges per node
    for from_node, to_node in edges:
        out_degree[from_node] += 1

    # Fill in transition probabilities
    for from_node, to_node in edges:
        from_idx = node_to_idx[from_node]
        to_idx = node_to_idx[to_node]
        transition_matrix[to_idx][from_idx] += 1 / out_degree[from_node]

    # Handle dangling nodes (no outgoing edges)
    for node in nodes:
        if out_degree[node] == 0:
            node_idx = node_to_idx[node]
            transition_matrix[:, node_idx] = 1 / N  # Uniform jump to all nodes

    return transition_matrix

Step 3: Add the damping factor (jump probability) #

PageRank includes a damping factor a (your "jump probability") which accounts for the chance a user randomly jumps to any node instead of following links. The final transition matrix P is calculated as:

P = a * M + (1 - a) * (1/N) * full_matrix_of_ones

Here’s the code for that:

def build_pagerank_matrix(base_matrix, damping_factor, num_nodes):
    uniform_jump = np.ones((num_nodes, num_nodes)) / num_nodes
    return damping_factor * base_matrix + (1 - damping_factor) * uniform_jump

Step 4: Iterate the probability vector #

We start with a uniform probability vector (all nodes have equal initial weight: 1/N). Then we multiply this vector by the transition matrix iters times to get the final PageRank scores. We’ll use row vectors here, so each iteration is a matrix multiplication vec = vec @ P:

def pagerank(edges, damping_factor, iters):
    # Get nodes and index mapping
    nodes = get_unique_nodes(edges)
    num_nodes = len(nodes)
    node_to_idx = {node: idx for idx, node in enumerate(nodes)}

    # Build base transition matrix
    base_matrix = build_transition_matrix(edges, nodes, node_to_idx)

    # Build final PageRank transition matrix
    pagerank_matrix = build_pagerank_matrix(base_matrix, damping_factor, num_nodes)

    # Initialize uniform probability vector
    prob_vector = np.ones(num_nodes) / num_nodes

    # Iterate for the specified number of steps
    for _ in range(iters):
        prob_vector = prob_vector @ pagerank_matrix

    # Map scores back to original node numbers
    pagerank_scores = {node: prob_vector[idx] for node, idx in node_to_idx.items()}
    return pagerank_scores

Test with your edge list #

Let’s run this with your example edges, a standard damping factor of 0.85, and 100 iterations:

edges = [[0,1], [1,1], [2,0], [2,2], [2,3], [3,3], [3,4], [4,6], [5,5], [6,6], [6,3]]
scores = pagerank(edges, damping_factor=0.85, iters=100)
print(scores)

You’ll get a dictionary where each key is a node and the value is its PageRank score. For your edge list, nodes like 1, 3, and 6 should have higher scores since they have self-loops or are linked to by other nodes.

Quick Notes #

• If you can’t use NumPy, you can implement matrix multiplication manually with nested lists, but it’ll be slower for large node sets.
• 50-100 iterations is usually enough for convergence (scores stop changing much), so your iters parameter can be adjusted based on precision needs.
• The function handles non-consecutive nodes automatically, so it works for any edge list, not just your example.

内容的提问来源于stack exchange，提问作者g singh