我最早写爬虫的时候觉得这玩意儿和数学八竿子打不着。无非就是发HTTP请求、解析HTML、把数据塞进数据库顶多再处理一下并发、反爬策略哪儿用得上图论这种听起来就很学院的玩意儿直到有一次我写的一个抓取程序在中型站点上莫名卡死排查了一下午最后发现是一个URL参数在无限生成新链接程序在一个永远走不完的循环里空转。那天晚上翻着图论的笔记我突然意识到爬虫做得越深图论就越绕不开。这篇文章想聊清楚一件事图论和网络爬虫到底是怎么绑定在一起的。从网页关系的图模型到抓取顺序背后的遍历策略再到蜘蛛陷阱里的环检测最后是PageRank这类链接分析算法怎么反过来指导爬虫干活。无论你是刚写完第一个爬虫的初学者还是正在为抓取效率头疼的工程师这篇文章都能帮你在只会调库写循环和真正理解爬虫原理之间跨过那个坎。1. 整个互联网本来就是一张巨图爬虫的数学底色1.1 网页、链接和图爬虫早就跑在图上了先做一个非常简单的抽象把每一个网页当做一个节点把网页里的每一个超链接当做一条从当前页面指向目标页面的边那么整个互联网就是一张巨大的有向图。这里的方向很关键A页面链向B页面并不代表B页面会链回A页面所以这是一张有向图不能拿无向图的思维去理解它。爬虫做的事情本质上就是在这张有向图上做遍历和采样。我们选定一批种子URL作为起点抓取页面、解析出边超链接、再沿着边走向新的节点不断重复。这个过程和你在图上做深度优先搜索、广度优先搜索没有任何本质区别只是边上附带了一个额外的动作——下载并解析HTML。这个视角一旦建立起来很多问题会变得清晰得多。为什么爬虫需要去重因为图里天然存在大量指向同一节点的多条路径不维护一个visited集合就会重复抓取。为什么爬虫最怕蜘蛛陷阱因为带环的图会让遍历永远无法结束。为什么搜索引擎的结果排序如此重要因为图里某些节点就是比另一些节点承载了更多的流量权重。图论不会直接帮你写出一个能跑的爬虫但它给了你一张地图。你手上的爬虫框架只是交通工具而图论告诉你目的地在哪个方向、路况如何、什么时候该掉头。1.2 动态、不完整、超大爬虫面对的不是教科书里的图你可能在教科书里见过那种规规矩矩的图节点有限、边固定、结构清楚。但互联网这张图完全不是这样它有几个和教科书截然不同的特征。第一它在持续变化。页面会新增、删除、改版超链接会失效今天存在的节点明天可能就返回404。爬虫永远在追赶一张不断变化的快照无法拿到完整的全量图。第二它的规模极其庞大。哪怕只是一个中型垂直站点的子图节点数量也可能轻松达到百万级。搜索引擎面对的图是百亿甚至千亿级节点的动态网络任何O(n²)级别的算法在这种规模上都是灾难。第三我们永远只能观察到局部。爬虫不是上帝视角它只能通过已经抓到的页面发现新的链接视野永远受限于已探索的部分。这和图论里的在线算法、采样算法所面对的局面非常像。理解这三点你就能明白为什么爬虫工程里没有那么多完美算法更多的是在效率和资源之间的妥协。教科书上的图论算法往往假设拥有完整信息而爬虫场景要求把算法改造成可以接受不完整输入、允许小概率出错的版本。这一点在后面谈布隆过滤器和环检测工程落地时你会有更深的体会。2. 抓取顺序就是图的遍历策略从BFS到有优先级的搜索2.1 BFS和DFS不只是教科书概念爬虫从种子URL出发解析页面里的链接放进待抓取队列然后循环处理。这一步最基础的策略选择其实就是图遍历里的BFS和DFS。BFS用先进先出的队列一层一层往外扩先抓离种子页面近的、深度浅的URL。DFS用后进先出的栈一条道走到黑适合在一个网站里深挖某个特定方向的内容。不少爬虫新手写代码的时候根本没有区分过这两者反正都是解析链接塞列表再来个循环但实际表现出来的行为差异非常大。维度BFS广度优先DFS深度优先数据结构FIFO队列LIFO栈爬取效果优先覆盖站点首页、列表页容易钻进某个栏目出不来对目标站点的压力分布均匀相对友好可能短时间集中请求同一路径触发风控典型场景通用爬虫、搜索引擎爬虫定向采集某个专栏、回溯历史页面我自己早期写爬虫时习惯用列表的append和pop(0)模拟队列纯BFS。后来发现对某些站点来说BFS会抓太多低价值的列表页而DFS又容易在深链里迷路最后选择的是折中方案先BFS铺几层再对高价值子树做有限深度的DFS。这个套路在垂直采集场景里很实用。2.2 带权重的待抓队列工程版的最佳优先搜索纯粹的BFS有一个天生的问题它把所有相邻节点一视同仁但工程上我们明明知道有些链接更值得抓。举个例子一个新闻站点的首页和栏目页重要性远高于某个随机文章的标签聚合页一个包含大量出链的导航页比一个孤零零的图片页更有抓取价值。如果待抓队列只按先进先出的顺序处理重要页面可能会被大量低价值页面挤到后面。所以真实爬虫的待抓队列几乎都不会是朴素的FIFO而是带权重的优先队列。每个URL根据某种启发式规则算出一个分数分数高的先抓。这不是什么高深的技巧Scrapy里也有内置的优先级参数但我见过不少团队把这个参数当作摆设。我的经验是优先级函数里至少可以包含这几个信号URL所在域名的历史数据质量该域名下内容页占比高不高URL在已抓页面中出现的位置首页、正文区域里出现的链接比评论区、底部推荐的链接更有价值URL模式的匹配度符合已知内容页模式的URL直接加分页面深度离种子页面越远新鲜感越低但某些特定路径例外。这个思路和图论里的最佳优先搜索异曲同工——用代价函数或价值函数指导搜索方向而不是机械地按深度铺开。所谓智能爬虫很大一部分智能就体现在这个优先级的计算上。2.3 URL去重图遍历里的visited集合还有布隆过滤器图遍历一定离不开visited集合爬虫也一样。稍有规模的爬虫待去重的URL数量很快就会突破千万级别这时候如果直接用Python的set或者Redis的Set存储每一个完整URL内存和存储成本都相当可观。我算过一笔账一个URL平均按200字节算一亿个URL就是20GB。哪怕压缩存储对在线服务来说也是一笔不小的开销。这时候就该布隆过滤器上场了。布隆过滤器的核心思想是用一个位数组配合多个哈希函数来表示一个集合。插入一个URL时用k个哈希函数把它映射到位数组的k个位置全部置为1查询时只要发现任何一个位置是0就说明这个URL肯定没被访问过。如果所有位置都是1那只能说很可能访问过存在一定误判率。误判率也不是拍脑袋定的它和位数组长度m、哈希函数个数k、已插入元素数量n有关大约等于(1 - e^(-kn/m))^k。工程上常见做法是让m/n约等于10k约等于7误判率能压到1%左右。这个代价完全可控换来的是内存占用降一个数量级。import mmh3 import math class BloomFilter: def __init__(self, capacity, error_rate0.01): self.bit_size int(-capacity * math.log(error_rate) / (math.log(2) ** 2)) self.k max(1, int(self.bit_size / capacity * math.log(2))) self.bits bytearray(math.ceil(self.bit_size / 8)) def _hashes(self, url): return [mmh3.hash(url.encode(), i) % self.bit_size for i in range(self.k)] def add(self, url): for h in self._hashes(url): self.bits[h // 8] | 1 (h % 8) def contains(self, url): return all(self.bits[h // 8] (1 (h % 8)) for h in self._hashes(url))上面是最简实现真正的生产环境可以直接用pybloom_live或者Redis的布隆模块。这里想强调一个坑标准布隆过滤器不支持删除操作。如果你抓某个URL失败了想把它重新放回待抓队列标准的布隆过滤器里它已经留下了已访问标记你没法撤销。我当时的解决办法是成功的URL进布隆过滤器失败的URL单独记在一个带过期时间的Redis Set里允许重试N次超过N次才放弃。这套组合比较稳。3. 蜘蛛陷阱与环路检测被图论救活的爬虫3.1 蜘蛛陷阱的图论本质无穷路径和环蜘蛛陷阱是每个爬虫工程师早晚会遇到的问题。表现形式千奇百怪但图论视角下无非两种无穷路径或者环。无穷路径很好理解。站点通过动态参数、日历翻页、排序组合等机制可以无止境地生成新URL。比如一个商品筛选页把品牌、价格、颜色、尺寸的参数排列组合一下就能变出几百万个URL再比如日历组件可以一年一年往下翻翻到2050年还有新页面。每个页面内容都大同小异但URL各不相同如果只靠字符串去重根本防不住。环则更阴险。A页面链向BB链向CC又链回A。程序在A→B→C→A的循环里开心地跑着每次都会抓到相同或相近的内容但不会报错、不会有异常就是一直空转浪费带宽和存储。很多新手遇到蜘蛛陷阱的第一反应是加去重但去重只能解决URL完全相同的情况。面对参数排列组合和动态token字符串级别的去重完全无效。这时候需要的是真正的图论思维判断遍历路径上是否出现了环路或者对路径深度做硬限制。3.2 三色标记法DFS环检测的标准解法图论里检测有向图是否有环最经典的做法是在DFS过程中维护三种颜色状态白色该节点还没被访问灰色该节点在当前递归栈中即正在被探索黑色该节点已经完成所有子节点的探索不可能再形成环。如果在DFS过程中遇到一条边指向一个灰色节点说明我们找到了一个环。WHITE, GRAY, BLACK 0, 1, 2 def has_cycle(graph): color {node: WHITE for node in graph} def dfs(node): color[node] GRAY for nxt in graph.get(node, []): if color[nxt] GRAY: return True if color[nxt] WHITE and dfs(nxt): return True color[node] BLACK return False return any(color[node] WHITE and dfs(node) for node in graph)这段代码在教科书图上是没问题的但放到真实爬虫里直接套用会碰到一个很现实的问题真实爬虫是分布式的、多线程的、异步的没有一个统一的递归栈可以维护颜色状态。你没法在分布式环境下维护一个完整的当前调用路径。所以工程上需要把环检测转化成更容易落地的等价策略。我常用的手段是给每个请求附带一条路径上下文记录当前URL是从哪个页面跳过来的、已经连续跳了几层、这条路径上的URL列表是什么。如果新解析出的URL出现在当前路径里就说明已经踩进环了停止沿这条路径继续扩展。3.3 从算法到工程环检测的真正落地姿势算法归算法工程落地还得靠几板斧。我在处理蜘蛛陷阱时靠的不是单一招数而是组合策略。第一是URL标准化。把统计参数utm_source、from等、排序参数、session参数全部剔除只保留真正决定页面内容的参数。很多看起来不同的URL标准化之后其实是同一个页面。第二是单站点路径深度限制。在爬虫配置里对每个域名单独设定最大深度限制比如首页算第0层最多允许往下钻5层。就算站点有无限翻页的日历深度限制也能保证程序在有限步内收敛。第三是内容相似度去重。这是对付URL不同但内容相同类陷阱的有力手段。抓下来的HTML算一个simhash指纹或者抽取正文后算MD5摘要如果和最近一段时间抓过的内容重复率过高就判定为低价值页面不入库也不扩展其链接。这个方法在抓动态页面时尤其好用。第四是单域页面上限。无论一个站点多么庞大设定单次抓取任务内的页面数量上限。比如一个域名最多抓2万个页面到了就停。这是最简单粗暴但永远有效的兜底策略。想起那个让我排查了一下午的日历bug最终修复用的就是URL标准化白名单加内容摘要去重双管齐下。日历URL后面的随机token每次都不一样字符串层面完全防不住但页面正文摘要几乎一模一样内容去重一抓一个准。4. 抓完之后的图分析PageRank和链接结构4.1 PageRank的数学直觉和计算过程如果说遍历和环检测是爬虫过程中的图论那PageRank就是爬虫之后的图论。早期的通用搜索引擎面临的问题很简单网页这么多用户输入一个查询哪个结果应该排在前面PageRank的想法非常优雅把互联网想象成一个用户随机点击链接的模型。一个用户在某个网页上以概率d点击页面里的一个随机链接跳转到下一页以概率1-d直接跳到互联网上任意一个随机页面。长时间下来用户停留在每个页面上的概率就反映了这个页面的重要程度。用图论的数学语言说PageRank就是这个马尔可夫链的平稳分布是转移矩阵的主导特征向量。公式表达是PR(A) (1-d) d × Σ(PR(Ti) / C(Ti))其中Ti是链向A的所有页面C(Ti)是Ti的出链数量d是阻尼因子一般取0.85。用代码算就简单多了。大多数时候我不手写迭代直接套NetworkXimport networkx as nx G nx.DiGraph() G.add_edges_from([ (a, b), (b, c), (c, a), (d, a), (a, d), ]) pr nx.pagerank(G, alpha0.85, max_iter100, tol1e-06) print(pr)注意一个细节阻尼因子取0.85是经验值它的含义是用户大概有85%的概率继续沿着链接点击15%的概率随机跳到别的页面。这个值调大PageRank会更倾向于被高权重页面链接的节点调小则会更倾向于入链数量多的节点。具体场景下值得多试几组参数。4.2 让PageRank反过来指导爬虫调度大多数人把PageRank理解成搜索引擎排名算法和爬虫没什么直接关系。但实际上这是一个很好的闭环爬虫抓下来的链接结构可以用来计算页面重要度反过来重要度高的页面应该被更频繁地重新抓取。我当时接手的一个垂直资讯爬虫就遇到过这个问题所有页面统一更新频率导致高价值页面的更新被低价值页面的抓取任务拖累。后来按PageRank把已抓页面分成三档高权重页每天重抓中权重页每周重抓低权重页只在有新链接指向它时才抓。同样的带宽核心内容的新鲜度明显提升。这个思路对未抓取的URL同样有效。当我们估算一个未知URL的重要度时虽然没法直接算PageRank但可以根据它出现在哪些页面里做个近似——一个链接如果同时出现在多个高权重页面的正文区域那它极大概率是个值得抓的页面给它提高优先级就对了。4.3 入度、强连通分量、社区发现爬虫工具箱里的其他图算法PageRank之外图论还给爬虫工程师备了不少趁手工具。入度和出度分析最直观。一个页面入链多说明它被广泛引用是权威页一个页面出链多说明它是导航页、目录页是爬虫扩展路径的枢纽。我经常在抓完一轮后统计一下出入度分布快速找出站点里的门户页和内容页再针对不同页面类型设计不同的抓取频率。强连通分量检测也很实用。站点之间的互链经常形成集团比如几个垂直社区互相引用、互相推荐构成一个紧密的强连通分量。这意味着抓取A站时很可能会顺着链接发现B站、C站而且它们内容高度相关。如果平台对同一集团内的站点统一调度可以有效控制对同一内容源的多路冗余抓取。社区发现算法则适合做垂直采集的主题聚类。把URL按链接关系聚成社区每个社区代表一个话题或一类业务爬虫可以按社区分配资源而不是一个域名一个域名机械地抓。这些分析不必实时跑离线批处理就够。把已抓数据导出成图结构跑一遍分析把结果同步到在线存储供调度模块读取。这个离线图分析在线调度的架构是性价比非常高的做法。5. 一次真实重构把爬虫从无脑抓取改成图驱动5.1 问题的表象是入库率低根子是链路缺失当时的情况是这样一个垂直资讯聚合爬虫覆盖几十个站点每天抓几十万页面但真正能进内容库、能被搜索引擎收录的不到三成。大量带宽和存储都浪费在低质量的列表页、标签页、翻页副本和动态生成的相似页面上。团队一开始讨论的方案都是加大反爬力度提高并发数多挂代理这些都是在抓得更快上做文章但根本问题其实是我们根本不知道哪些页面值得抓、哪些页面抓了纯属浪费。用图论的话说我们手里有一堆节点但完全没利用节点之间的关系信息。后来我们做的事情本质上就是把抓取从无脑BFS升级成图驱动的最优搜索。5.2 图建模和优先队列的改造路径改造分四步走。第一步把已抓页面建立成有向图。节点是URL的标准化形式边是页面间的链接关系图的存储用的是离线导出的CSV加NetworkX分析。第二步离线跑图分析。用PageRank给所有已抓页面打分同时统计每个页面的入度、出度、所在强连通分量等基础指标。分析结果写回Rediskey就是页面URLvalue是JSON包含各种图指标。第三步改造待抓队列的优先级函数。对新URL做估算如果它出现在多个高权重页面的正文区直接给高分如果它的URL模式和历史低质量页面相似就给低分甚至直接过滤如果它所在的域名整体图指标很差那就延迟抓取。第四步动态更新抓取计划。每轮抓取结束后把新抓到的页面加入图模型增量更新相关页面的权重让调度策略可以跟着网络结构的变化走。改造上线后入库率从不到三成提到了接近六成由于少抓了大量低价值页面整体请求量下降被站点屏蔽的次数反而少了。更重要的是团队后续做内容推荐、页面更新调度时手里有了一套基于图结构的数据资产很多决策都变得有据可依。5.3 关于图计算选型和工程落地的几点经验关于选型我的建议是先想清楚数据量级再决定上不上图数据库。百万节点以下NetworkX完全够用离线算完导结果就行没必要为了用了图数据库而上图数据库。千万级以上再考虑Neo4j或JanusGraph这类分布式图数据库。还有几个实际踩过的坑可以分享。PageRank迭代次数不足会导致结果偏向初始值max_iter至少给100收敛容差tol给到1e-06不然排名会出现上轮结果惯性。强连通分量检测在大图上很吃内存。我曾在千万级图上跑tarjan算法直接把内存打满了。正确姿势是先做抽样验证确认连通性预估没问题再在核心子图上跑分析避免在异常图上浪费资源。不要把图分析和在线抓取耦合在一起。离线分析和在线调度必须解耦图分析跑挂了不能影响抓取服务继续运行。我们当时的做法是图分析结果写Redis抓取服务只读Redis里的结果如果分析结果过期抓取服务自动退化成BFS模式保证整体可用性。最后再分享一个小技巧写爬虫之前先别急着写代码。花半小时把目标网络的图结构在脑子里过一遍甚至手画一张草图种子页面有哪些、哪些页面是枢纽页、哪些页面可能形成环、哪些页面才有真实价值。这个过程就像打仗前看地图画完之后你写代码的思路会完全不一样。另外遇到爬虫难题时可以多问自己一句这个问题能不能建模成图问题URL无限生成就是无穷路径抓取卡死就是环抓取质量差就是节点权重没算对抓取浪费资源就是没做社区聚类。把问题翻译成图论语言能用的成熟算法和工具就多出来了。这大概就是数学之美在工程里最实在的体现——它不直接给你答案但帮你把问题看清楚。