Note

Go to the end to download the full example code or to run this example in your browser via JupyterLite or Binder.

Wikipedia principal eigenvector#

A classical way to assert the relative importance of vertices in a graph is to compute the principal eigenvector of the adjacency matrix so as to assign to each vertex the values of the components of the first eigenvector as a centrality score: https://en.wikipedia.org/wiki/Eigenvector_centrality. On the graph of webpages and links those values are called the PageRank scores by Google.

The goal of this example is to analyze the graph of links inside wikipedia articles to rank articles by relative importance according to this eigenvector centrality.

The traditional way to compute the principal eigenvector is to use the power iteration method. Here the computation is achieved thanks to Martinsson’s Randomized SVD algorithm implemented in scikit-learn.

The graph data is fetched from the DBpedia dumps. DBpedia is an extraction of the latent structured data of the Wikipedia content.

# Authors: The scikit-learn developers
# SPDX-License-Identifier: BSD-3-Clause

from bz2 import BZ2File
from datetime import datetime
from pprint import pprint
from time import time

import matplotlib.pyplot as plt
import numpy as np
from scipy import sparse

from sklearn.datasets import fetch_file
from sklearn.decomposition import randomized_svd

Download data#

redirects_url = "https://downloads.dbpedia.org/3.5.1/en/redirects_en.nt.bz2"
redirects_filename = fetch_file(redirects_url)

page_links_url = "https://downloads.dbpedia.org/3.5.1/en/page_links_en.nt.bz2"
page_links_filename = fetch_file(page_links_url)

resources = [
    (redirects_url, redirects_filename),
    (page_links_url, page_links_filename),
]

Loading the redirect files#

def index(redirects, index_map, k):
    """Find the index of an article name after redirect resolution"""
    k = redirects.get(k, k)
    return index_map.setdefault(k, len(index_map))


DBPEDIA_RESOURCE_PREFIX_LEN = len("http://dbpedia.org/resource/")
SHORTNAME_SLICE = slice(DBPEDIA_RESOURCE_PREFIX_LEN + 1, -1)


def short_name(nt_uri):
    """Remove the < and > URI markers and the common URI prefix"""
    return nt_uri[SHORTNAME_SLICE]


def get_redirects(redirects_filename):
    """Parse the redirections and build a transitively closed map out of it"""
    redirects = {}
    print("Parsing the NT redirect file")
    for l, line in enumerate(BZ2File(redirects_filename)):
        split = line.split()
        if len(split) != 4:
            print("ignoring malformed line: " + line)
            continue
        redirects[short_name(split[0])] = short_name(split[2])
        if l % 1000000 == 0:
            print("[%s] line: %08d" % (datetime.now().isoformat(), l))

    # compute the transitive closure
    print("Computing the transitive closure of the redirect relation")
    for l, source in enumerate(redirects.keys()):
        transitive_target = None
        target = redirects[source]
        seen = {source}
        while True:
            transitive_target = target
            target = redirects.get(target)
            if target is None or target in seen:
                break
            seen.add(target)
        redirects[source] = transitive_target
        if l % 1000000 == 0:
            print("[%s] line: %08d" % (datetime.now().isoformat(), l))

    return redirects

Computing the Adjacency matrix#

def get_adjacency_matrix(redirects_filename, page_links_filename, limit=None):
    """Extract the adjacency graph as a scipy sparse matrix

    Redirects are resolved first.

    Returns X, the scipy sparse adjacency matrix, redirects as python
    dict from article names to article names and index_map a python dict
    from article names to python int (article indexes).
    """

    print("Computing the redirect map")
    redirects = get_redirects(redirects_filename)

    print("Computing the integer index map")
    index_map = dict()
    links = list()
    for l, line in enumerate(BZ2File(page_links_filename)):
        split = line.split()
        if len(split) != 4:
            print("ignoring malformed line: " + line)
            continue
        i = index(redirects, index_map, short_name(split[0]))
        j = index(redirects, index_map, short_name(split[2]))
        links.append((i, j))
        if l % 1000000 == 0:
            print("[%s] line: %08d" % (datetime.now().isoformat(), l))

        if limit is not None and l >= limit - 1:
            break

    print("Computing the adjacency matrix")
    n = len(index_map)
    rows, cols = np.array(links, dtype=np.int32).T
    del links
    data = np.ones(len(rows), dtype=np.float32)
    X = sparse.csr_array((data, (rows, cols)), shape=(n, n))
    # Multiple links between the same pair of pages must still count as a
    # single edge, so we set the data to 1 after the CSR matrix constructor
    # which sums duplicate (row, col) entries.
    X.data[:] = 1.0
    return X, redirects, index_map


# stop after 3M links so parsing stays fast and the graph stays small enough in memory.
X, redirects, index_map = get_adjacency_matrix(
    redirects_filename, page_links_filename, limit=3000000
)
names = {i: name for name, i in index_map.items()}

Computing the redirect map
Parsing the NT redirect file
[2026-09-23T17:48:21.577427] line: 00000000
[2026-09-23T17:48:24.508519] line: 01000000
[2026-09-23T17:48:27.443185] line: 02000000
[2026-09-23T17:48:30.484100] line: 03000000
[2026-09-23T17:48:33.218863] line: 04000000
Computing the transitive closure of the redirect relation
[2026-09-23T17:48:33.438884] line: 00000000
[2026-09-23T17:48:33.737049] line: 01000000
[2026-09-23T17:48:34.060812] line: 02000000
[2026-09-23T17:48:34.434843] line: 03000000
[2026-09-23T17:48:34.845624] line: 04000000
Computing the integer index map
[2026-09-23T17:48:34.887286] line: 00000000
[2026-09-23T17:48:37.375136] line: 01000000
[2026-09-23T17:48:39.817111] line: 02000000
Computing the adjacency matrix

Computing Principal Singular Vector using Randomized SVD#

print("Computing the principal singular vectors using randomized_svd")
t0 = time()
U, s, V = randomized_svd(X, 5, n_iter=3)
print("done in %0.3fs" % (time() - t0))

# print the names of the wikipedia related strongest components of the
# principal singular vector which should be similar to the highest eigenvector
print("Top wikipedia pages according to principal singular vectors")
pprint([names[i] for i in np.abs(U.T[0]).argsort()[-10:]])
pprint([names[i] for i in np.abs(V[0]).argsort()[-10:]])

Computing the principal singular vectors using randomized_svd
done in 0.873s
Top wikipedia pages according to principal singular vectors
[b'1980',
 b'1990',
 b'1975',
 b'1970',
 b'1996',
 b'1972',
 b'2006',
 b'1966',
 b'1967',
 b'2007']
[b'2006',
 b'1945',
 b'2007',
 b'Soviet_Union',
 b'Japan',
 b'Germany',
 b'World_War_II',
 b'France',
 b'United_Kingdom',
 b'United_States']

Computing Centrality scores#

def centrality_scores(X, alpha=0.85, max_iter=100, tol=1e-10):
    """Power iteration computation of the principal eigenvector

    This method is also known as Google PageRank and the implementation
    is based on the one from the NetworkX project (BSD licensed too)
    with copyrights by:

      Aric Hagberg <hagberg@lanl.gov>
      Dan Schult <dschult@colgate.edu>
      Pieter Swart <swart@lanl.gov>
    """
    n = X.shape[0]
    X = X.copy()
    incoming_counts = np.asarray(X.sum(axis=1)).ravel()

    print("Normalizing the graph")
    for i in incoming_counts.nonzero()[0]:
        X.data[X.indptr[i] : X.indptr[i + 1]] *= 1.0 / incoming_counts[i]
    dangle = np.asarray(np.where(np.isclose(X.sum(axis=1), 0), 1.0 / n, 0)).ravel()

    scores = np.full(n, 1.0 / n, dtype=np.float32)  # initial guess
    errors = []
    for i in range(max_iter):
        print("power iteration #%d" % i)
        prev_scores = scores
        scores = (
            alpha * (scores @ X + dangle @ prev_scores)
            + (1 - alpha) * prev_scores.sum() / n
        )
        # check convergence: normalized l_inf norm
        scores_max = np.abs(scores).max()
        if scores_max == 0.0:
            scores_max = 1.0
        err = np.abs(scores - prev_scores).max() / scores_max
        errors.append(err)
        print("error: %0.6f" % err)
        if err < n * tol:
            break

    return scores, np.asarray(errors)


print("Computing principal eigenvector score using a power iteration method")
t0 = time()
scores, errors = centrality_scores(X, max_iter=100)
print("done in %0.3fs" % (time() - t0))
top_abs_score_indices = np.abs(scores).argsort()[-5:]
pprint([names[i] for i in top_abs_score_indices])

Computing principal eigenvector score using a power iteration method
Normalizing the graph
power iteration #0
error: 0.975444
power iteration #1
error: 0.484346
power iteration #2
error: 0.296256
power iteration #3
error: 0.201524
power iteration #4
error: 0.145967
power iteration #5
error: 0.110055
power iteration #6
error: 0.085267
power iteration #7
error: 0.067351
power iteration #8
error: 0.053963
power iteration #9
error: 0.043704
power iteration #10
error: 0.035693
power iteration #11
error: 0.029342
power iteration #12
error: 0.024247
power iteration #13
error: 0.020122
power iteration #14
error: 0.016756
power iteration #15
error: 0.013992
power iteration #16
error: 0.011712
power iteration #17
error: 0.009821
power iteration #18
error: 0.008249
power iteration #19
error: 0.006938
power iteration #20
error: 0.005841
power iteration #21
error: 0.004923
power iteration #22
error: 0.004152
power iteration #23
error: 0.003504
power iteration #24
error: 0.002959
power iteration #25
error: 0.002500
power iteration #26
error: 0.002112
power iteration #27
error: 0.001786
power iteration #28
error: 0.001510
power iteration #29
error: 0.001277
power iteration #30
error: 0.001081
power iteration #31
error: 0.000914
power iteration #32
error: 0.000774
power iteration #33
error: 0.000655
power iteration #34
error: 0.000554
power iteration #35
error: 0.000469
power iteration #36
error: 0.000397
power iteration #37
error: 0.000336
power iteration #38
error: 0.000285
power iteration #39
error: 0.000241
power iteration #40
error: 0.000204
power iteration #41
error: 0.000173
power iteration #42
error: 0.000146
power iteration #43
error: 0.000124
power iteration #44
error: 0.000105
power iteration #45
error: 0.000089
power iteration #46
error: 0.000075
done in 0.220s
[b'Philosophy', b'New_York_City', b'World_War_I', b'France', b'United_States']

Plot results#

fig, ax = plt.subplots()
ax.semilogy(range(1, len(errors) + 1), errors)
ax.set_xlabel("power iteration")
ax.set_ylabel("convergence error (normalized $\\ell_\\infty$)")
ax.set_title("PageRank power-iteration convergence")
plt.show()

fig, ax = plt.subplots()
ax.barh([names[i] for i in top_abs_score_indices], scores[top_abs_score_indices])
ax.set_xlabel("PageRank score")
ax.set_title("Wikipedia pages with the highest eigenvector centrality")
plt.tight_layout()
plt.show()