Python爬虫实战：基于维基百科的六度分隔遍历算法

维基百科六度分隔理论背景

即便未接触过“维基百科六度分隔理论”，许多人也可能熟悉“凯文·贝肯六度分隔”游戏。两者的核心目标一致：通过一个包含至多6个节点（含起始与终点）的链条，将两个看似无关的主题连接起来。前者基于维基百科词条间的超链接关系，后者则基于共同出演电影演员的关联。

举例而言，埃里克·艾德尔与布兰登·弗雷泽共同出演了电影《骑警杜德雷》，而布兰登·弗雷泽又与凯文·贝肯共同出演了《我呼吸的空气》。据此逻辑，从埃里克·艾德尔到凯文·贝肯的路径长度仅为3个主题节点。

The Oracle of Bacon 网站的存在，满足了人们对这类关系链查询的好奇心。

爬虫项目目标与服务器负载分析

本节将构建一个项目，旨在实现“维基百科六度分隔理论”的查找算法。具体而言，程序将从埃里克·艾德尔的词条页面（https://en.wikipedia.org/wiki/Eric_Idle）出发，通过最少次数的链接点击，尝试找到凯文·贝肯的词条页面（https://en.wikipedia.org/wiki/Kevin_Bacon）。

这种操作对维基百科服务器造成的负载影响究竟有多大？

据维基媒体基金会（维基百科运营组织）统计，该网站每秒接收约2500次点击，其中99%以上的流量指向维基百科域名（详见“维基媒体统计图”中的“流量数据”部分）。鉴于巨大的网站流量，单个网络爬虫对服务器负载的影响微乎其微。然而，若频繁运行本书代码示例或自行开发抓取项目，建议向维基媒体基金会捐赠。这既是为了补偿占用的服务器资源，也是支持维基百科作为教育资源的持续运营。

链接提取与过滤策略

此外，若计划利用维基百科数据开展大型项目，应优先确认数据是否可通过维基百科API获取。维基百科因HTML结构简单且稳定，常被用作爬虫演示案例，但其API通常能提供更高效的数据获取方式。读者应已掌握使用Python代码获取任意维基百科页面并提取页面内链接的基本技能。

from urllib.request import urlopen from bs4 import BeautifulSoup
html = urlopen('http://en.wikipedia.org/wiki/Kevin_Bacon') 
bs = BeautifulSoup(html, 'html.parser') 
for link in bs.find_all('a'):  
if 'href' in link.attrs:    
print(link.attrs['href'])

观察生成的链接列表，其中包含所需的所有词条链接，如“Apollo 13”、“Philadelphia”、“Primetime Emmy Award”等。然而，列表中同时也混杂了无需关注的链接：

//wikimediafoundation.org/wiki/Privacy_policy //en.wikipedia.org/wiki/Wikipedia:Contact_us

实际上，维基百科每个页面均包含大量侧边栏、页眉和页脚链接，以及指向分类页面、讨论页面和其他非词条页面的链接：

/wiki/Category:Articles_with_unsourced_statements_from_April_2014 
/wiki/Talk:Kevin_Bacon

近期，一位朋友在进行类似的维基百科抓取项目时，为判断内部链接是否指向词条页面，编写了一个超过100行的复杂过滤函数。遗憾的是，他未提前花时间寻找“词条链接”与“其他链接”之间的规律，尽管后续可能已发现。仔细观察指向词条页面（非其他内部页面）的链接，可发现它们具备三个共同特征：

• 均位于id为bodyContent的div标签内部
• URL中不包含冒号
• URL均以/wiki/开头

基于上述规则，我们可以调整代码以仅获取词条链接，使用的正则表达式为 ^(/wiki/)((?!:).)*$：

from urllib.request import urlopen 
from bs4 import BeautifulSoup 
import re
html = urlopen('http://en.wikipedia.org/wiki/Kevin_Bacon') 
bs = BeautifulSoup(html, 'html.parser') 
for link in bs.find('div', {'id':'bodyContent'}).find_all(  
'a', href=re.compile('^(/wiki/)((?!:).)*$')):  
if 'href' in link.attrs:    
print(link.attrs['href'])

运行上述代码后，即可看到凯文·贝肯词条页面上所有指向其他有效词条的链接列表。

核心算法实现：getLinks与主函数

虽然编写程序来提取静态维基百科词条中的所有链接颇具趣味，但实际应用价值有限。我们需要将程序重构为以下形式：

• 定义一个getLinks函数，接收格式为/wiki/<词条名称>的维基百科词条URL作为参数，并返回包含所有有效词条URL的列表。
• 定义一个主函数，以起始词条为参数调用getLinks，从返回的URL列表中随机选择一个词条链接，再次调用getLinks，直至用户主动停止程序或新页面不再包含有效词条链接。

完整代码实现如下：

from urllib.request import urlopen 
from bs4 import BeautifulSoup 
import datetime 
import random 
import re

random.seed(datetime.datetime.now()) 
def getLinks(articleUrl):  html = urlopen('http://en.wikipedia.org{}'.format(articleUrl))  
bs = BeautifulSoup(html, 'html.parser')  
return bs.find('div', {'id':'bodyContent'}).find_all('a',    
href=re.compile('^(/wiki/)((?!:).)*$'))
links = getLinks('/wiki/Kevin_Bacon') 
while len(links) > 0:
newArticle = links[random.randint(0, len(links)-1)].attrs['href']  
print(newArticle)  
links = getLinks(newArticle)

随机数种子与梅森旋转算法

导入必要的Python库后，程序首先利用系统当前时间设置随机数生成器的种子。此举确保每次程序运行时，维基百科词条的选择路径均为全新的随机序列。

伪随机数与随机数种子机制

在前面的示例中，为了实现维基百科的连续随机遍历，我使用Python的随机数生成器在每个页面上随机选择一个词条链接。然而，使用随机数时需格外谨慎。

尽管计算机擅长精确计算，但在处理随机事件时往往表现不可靠，因此随机数生成是一个难题。大多数算法旨在生成均匀分布且难以预测的数字序列，但在初始化阶段必须提供一个随机数“种子”（random seed）。若种子完全相同，每次生成的“随机”数序列也将一致。因此，我将系统时间作为生成新随机数序列（以及新随机词条序列）的起点，从而增加程序运行的随机性。

实际上，Python的伪随机数生成器采用梅森旋转（Mersenne Twister）算法，其生成的随机数难以预测且分布均匀，但相对消耗CPU资源。高质量的随机数生成确实成本较高。随后，程序定义getLinks函数，接收格式为/wiki/<词条名称>的维基百科词条URL作为参数，在URL前拼接维基百科域名http://en.wikipedia.org，并利用该域名的HTML内容生成BeautifulSoup对象。接着，基于前述参数，抽取包含词条链接的a标签并返回。主函数首先将起始页面https://en.wikipedia.org/wiki/Kevin_Bacon的词条链接列表赋值给变量links。随后进入循环，从页面中随机选取一个词条链接标签，提取其href属性并打印该页面，再将此链接传入getLinks函数以获取新的链接列表。

当然，上述代码仅构建了从一个页面到另一个页面的简单爬虫。若要真正解决“维基百科六度分隔理论”问题，还需进一步工作，包括存储URL链接数据并进行数据分析。

以上即为Python爬虫遍历单个域名相关的全部知识点，感谢大家的学习与支持。