★ FEATURED ARTICLE 六度人脉真的存在吗用Floyd算法在社交网络里找最短关系链先问一个大家都有过疑问的问题你和任何一个陌生人之间最多隔着几个人早几十年Stanley Milgram用寄信实验给出过一个著名答案——平均大约6.6次转发一封陌生人之间的信就能到达目标。这个结论后来演化成六度人脉Six Degrees of Separation的说法任意两个人之间平均只需要6层朋友关系就能建立连接。如今社交网络的图模型让这个话题从社会学猜想变成了可计算的图论问题而Floyd算法正是理解最短人脉路径的一个绝佳入口。本文就沿着如何用Floyd算法在社交网络中寻找六度人脉最短路径这条线把原理、代码、复杂度、工程取舍一次讲透适合刚接触图算法的学生也适合在社交产品、风控、推荐系统里做关系分析的工程师参考。1. 六人脉背后的图论模型把社交关系变成一张带权图要用计算机解决两个人之间隔了几个人这个问题第一步必须把社交关系翻译成图结构。这步看起来简单但实际建模时有很多容易想当然的坑值得先铺开说清楚。1.1 什么是度六度人脉里的度不是节点的度很多教程一上来就混淆概念先做个辨析。六度人脉中的度指的是两点之间的路径长度——从A到B经过多少条边而图论里节点的度指的是这个节点连接了多少条边。这两个度完全是两个东西。比如我微信里有300个好友我的节点度数是300不考虑群聊隐藏关系。但我到某位明星的路径长度可能是4我直接认识某个记者1条边记者认识经纪人1条边经纪人认识明星1条边一共3条边也就是人们常说的3度人脉。在图模型里我们关注的是前者两个节点之间的最短路径长度。社交网络的边代表认识关系一个节点跳到另一个节点就相当于通过一次朋友介绍。路径越短关系链越紧密找到对方的成本就越低。1.2 把社交关系抽象成图节点、边、方向社交网络天然适合用无向图描述如果A认识B那么B也认识A。但在具体产品里关系可能是单向的比如微博的关注关系A关注了B但B没有回关这时候就需要用有向图建模。用Floyd算法处理有向图和无向图没有本质区别只需要注意邻接矩阵的对称性——无向图的矩阵是对称的有向图不一定对称。图的存储方式也需要提前想清楚。社交网络的规模动辄千万级、亿级节点但每个节点的平均好友数社交网络术语叫平均度往往只有几百。这种图是典型的大规模稀疏图有很多工程姿势可以应对。不过在讲优化之前先把最经典的Floyd算法吃透因为它是理解所有最短路径问题的地基。1.3 为什么六度人脉本质上是全源最短路径问题找到两个人之间的最短人脉链是一个单源最短路径问题Single Source Shortest Path——指定起点和终点求最短路径。但六度人脉这个宏观现象研究的是整张网络的性质任意两个节点之间的距离是否都限制在一个很小的常数附近。要回答这个问题最直接的做法是计算出所有节点对之间的最短距离然后看距离分布的统计特征。这就是全源最短路径问题All Pairs Shortest Path输入一张图输出一个矩阵矩阵中第i行第j列的值表示从节点i到节点j的最短距离。Floyd算法恰恰就是解决全源最短路径最经典的算法之一。和BFS广度优先搜索或Dijkstra算法一次只能求一个起点相比Floyd天然返回的是一个完整的距离矩阵直接就能统计平均隔着几个人有多少对节点超过6度这类指标。这在做网络拓扑分析、影响力扩散模拟、社群发现时非常方便。2. Floyd算法的核心递推逻辑在朋友的朋友中反复找桥梁Floyd算法的核心思想说出来非常朴素任意一条从i到j的路径都可以看作从i到某个中间点k的路径加上从k到j的路径拼起来的。如果中间点k能缩短i到j的距离那就更新它。这句话反复执行就是整个算法。2.1 动态规划的状态限制中间节点集合算法的官方表述是典型的动态规划。定义d[i][j]从节点i到节点j的当前最短距离考虑前k个节点编号0到k-1可以充当中间节点逐步放宽限制更形式化的递推是三维版本dp[k][i][j] 只允许经过编号不超过k的中间节点时从i到j的最短距离转移方程dp[k][i][j] min(dp[k-1][i][j], dp[k-1][i][k] dp[k-1][k][j])含义要么不使用第k个节点做中转保持原样要么使用i到k再k到j因为第k层的计算只依赖第k-1层所以可以滚动掉第一维直接在一个二维矩阵上原地更新d[i][j] min(d[i][j], d[i][k] d[k][j])2.2 这三重循环为什么能算出所有最短路径伪代码只有9行for k from 0 to n-1: for i from 0 to n-1: for j from 0 to n-1: if d[i][k] d[k][j] d[i][j]: d[i][j] d[i][k] d[k][j]理解这个算法的关键是k在最外层。很多人一开始容易写错成把i、j放外层结果算出的结果不对。为什么k必须在外层因为每个k代表一整轮允许使用第k个节点作为中转站的全局更新。当k轮结束时所有d[i][j]都已经考虑了经过节点0..k中任意组合的最短路径。第k1轮是在这个经过充分迭代的结果之上继续引入新中转保证每一步依赖的都是前面所有步骤算完的全局最优值。可以做个生活化类比你在一个几百人的聚会里想找某个陌生人你每认识一个新朋友都会拿着这个人的通讯录重新想一遍——我认识的人里有没有谁认识他当所有人都被你问过一遍之后你手上的关系链就都是最短的了。k就是那个新朋友i就是你认识的所有人j就是目标人物。每问完一个人全局关系网都会更新一轮。2.3 手算一个5人小圈子直观感受路径逐步缩短假设有5个人A、B、C、D、E。已知关系无向无权图边权均为1A-BA和B互为好友B-CC-DD-EA-EA和E也是好友也就是说这是一条A-B-C-D-E的链但A和E之间额外有一条直接边。初始化距离矩阵时直接有边相连的为1没边相连的为无穷大自己到自己是0初始时 d[A][D] 无穷大A不认识D。d[B][E] 无穷大。d[A][E] 1因为A-E有直接边。第一轮 kB检查所有i,j。发现 d[A][C] min(inf, d[A][B] d[B][C]) 2d[B][D] min(inf, d[B][C] d[C][D]) 2第二轮 kCd[A][D] min(inf, d[A][C] d[C][D]) 2 1 3。这时候A到D变成3跳A-B-C-Dd[B][E] min(inf, d[B][D] d[D][E]) 2 1 3第三轮 kDd[A][E] min(1, d[A][D] d[D][E]) min(1, 3 1) 1。咦A-E本来就是直接好友所以直接边保留。第四轮 kE对已有结果做终极检查看有没有通过E缩短的路径本例没有。最终得到的距离矩阵里A到D是3B到E是3A到C是2所有人之间的最短距离都确定下来了。整个过程可以清晰地看到每引入一个中转节点就有若干对节点之间的距离被打通。3. 用Python实现社交网络中的Floyd路径从距离到完整关系链理论讲通了进入代码环节。这里给出一个可以直接复制运行的最小实现并且包含路径还原功能——只算出隔着几个人还不够业务上往往还希望知道具体通过谁这样产品才能展示你的朋友小明认识目标用户这类引导文案。3.1 准备数据如何把好友关系装载成邻接矩阵在真实业务里好友关系一般存在关系数据库或者图数据库里表结构通常是两列user_id, friend_id。加载成邻接矩阵的步骤是给每个用户分配一个从0开始的连续编号做ID映射初始化一个 n×n 的矩阵所有值设为无穷大用float(inf)即可对角线上设为0自己到自己的距离是0遍历所有好友关系把对应的矩阵位置设为1无权图如果是有向的比如关注关系只设置matrix[u][v] 1如果是无向好友matrix[u][v] matrix[v][u] 1。3.2 核心代码Floyd算法与路径还原路径还原需要额外维护一个next_node矩阵记录从i到j的路径上i的下一个节点是谁。初始化时如果i到j有直接边next[i][j] j。在更新最短距离时同步更新next[i][j] next[i][k]。import math INF math.inf def floyd_warshall_with_path(adj_matrix): n len(adj_matrix) dist [row[:] for row in adj_matrix] nxt [[-1] * n for _ in range(n)] # 初始化 next 矩阵 for i in range(n): for j in range(n): if i ! j and dist[i][j] INF: nxt[i][j] j # Floyd 三重循环 for k in range(n): for i in range(n): if dist[i][k] INF: continue for j in range(n): if dist[k][j] INF: continue new_dist dist[i][k] dist[k][j] if new_dist dist[i][j]: dist[i][j] new_dist nxt[i][j] nxt[i][k] return dist, nxt def reconstruct_path(nxt, start, end): if nxt[start][end] -1: return None # 不可达 path [start] while start ! end: start nxt[start][end] path.append(start) return path使用时传入一个邻接矩阵即可# 示例5人小圈子0-A, 1-B, 2-C, 3-D, 4-E adj [ [0, 1, INF, INF, 1], # A 与 B、E 直接相连 [1, 0, 1, INF, INF], # B 与 A、C 相连 [INF, 1, 0, 1, INF], # C 与 B、D 相连 [INF, INF, 1, 0, 1], # D 与 C、E 相连 [1, INF, INF, 1, 0], # E 与 A、D 相连 ] dist, nxt floyd_warshall_with_path(adj) print(dist[0][3]) # A 到 D 的最短距离 2A-E-D print(reconstruct_path(nxt, 0, 3)) # [0, 4, 3] 即 A - E - D输出结果是A到D最短距离为2跳路径是A→E→D而不是直觉上可能认为的A→B→C→D3跳。这个例子极其适合用来向产品同学解释最短路径不一定按照列表顺序走中间节点的选择决定了答案。3.3 为什么用next[i][j] next[i][k]而不是next[i][j] k这是写路径还原最容易写错的地方。有些博客会写next[i][j] k即记录中间点是k。但这样做在递归输出时容易混乱。上面代码用的是记录路径上第一个下一步是谁的方案当发现i - k - j比i - j更短时说明从i出发的第一步应该走向i - k路径上的第一步。nxt[i][k]恰好就是这条路径的第一步所以直接赋值nxt[i][j] nxt[i][k]。这个方案实现简单不需要递归直接while循环就能输出整条路径工程上更顺手。在数据量小、迭代次数多的原生Floyd实现里我建议都用这种写法。4. 现实世界的复杂度拷问几亿用户时Floyd还能用吗算法看起来很美但社交网络工程师看到三重循环时脑子里第一个念头一定是复杂度真的可以接受吗这里必须把账算清楚。4.1 O(n^3) 意味着什么Floyd的时间复杂度是 O(n^3)。假设网络有n个节点n 10001e9次运算单机C大约几秒到几十秒Python需要几分钟到几十分钟n 1万1e12次运算单机基本不可行n 1亿1e24次运算哪怕用超算也接近天文数字所以在亿级节点社交图谱上直接跑完整Floyd是不现实的。这是所有讲Floyd的文章都必须坦诚承认的第一件事。4.2 邻接矩阵本身就可能存不下另一个被忽略的致命点是Floyd需要完整的邻接矩阵空间复杂度 O(n^2)。n1亿时n^21e16个数字。假如每个数字用8字节存储就是8e16字节 80000 TB。任何单机都扛不住这个存储量。这也是为什么工业界社交图谱分析几乎不用邻接矩阵存储而用邻接表、图数据库Neo4j等或分布式图计算框架Pregel、Giraph、GraphX。邻接表只存实际存在的边对稀疏社交网络极其友好。4.3 和其他最短路径算法的对比BFS、Dijkstra、双向BFS既然Floyd在超大图上不可行那实践中通常用什么做个对比表看得更清楚算法适用场景时间复杂度空间复杂度能得出完整路径BFS无权图单源O(VE)O(V)是Dijkstra非负权图单源O((VE)log V)O(V)是Floyd-Warshall任意权图全源O(V^3)O(V^2)是双向BFS无权图点对点O(b^(d/2))O(b^(d/2))是关键洞察六人脉问题里绝大多数社交关系不值得加权重后面会讲例外所以BFS和双向BFS反而是最常用工具。尤其是双向BFS——从起点和终点同时往里搜每层只扩展到一半深度在分支因子平均好友数几百的场景里效率提升是数量级的。4.4 小世界网络特性对数级路径长度是个好消息既然Floyd不能直接上为什么还要学它因为它帮助建立全源距离的思考框架。而六度人脉现象本身其实源自复杂网络理论的一个重要结论——小世界网络。Watts和Strogatz于1998年提出的WS小世界网络模型揭示了一个反直觉的事实即使节点总数n很大大多数节点之间的最短路径长度L仍然是对数级别的大致正比于log n。翻译成人话无向社交网络的平均最短路径很短虽然网络里有几亿人但你到任意一个人的距离大概率在3到7之间网络越大路径长度增长得越慢这意味着6度不是一个神奇常数而是小世界特性的自然结果。也正因路径长度这么短工程上可以放心地做深度限制搜索——比如限定最多搜6层因为超过6层的查询本来就极少且不满足业务直觉。5. 社交网络实战中的边权设计不是所有好友都同等重要前面讲的都是无权图认识就是1不认识就是无穷大。但真实业务里用户希望看到的人脉不应该是冷冰冰的隔了几个人而应该是通过多少亲近程度才能触达。边权设计会直接导致最短路径选择的不同这里面的门道值得单独讲。5.1 亲密度权重路径长度最小化并不总是最优举个例子。假设A想联系CA和B是大学同学几乎每天互动关系很近B和C仅仅是某次行业大会交换过名片多年没有交流A和D是普通朋友互动一般D和C是同事互动频繁无权图的视角A→B→C 是2跳A→D→C 也是2跳两条路径一样好。但从有效触达角度A通过D去找C的成功率远高于通过B。加权的方式可以这样设计定义疏远度distance weight和亲密度similarity成反比比如w(u,v) 1 / (1 interaction_count(u,v))互动多权重小关系近互动少权重大关系远此时最短路径就不再只是跳数最小而是综合亲密度最优。上面的例子中A-D-C的加权距离会明显小于A-B-CFloyd或Dijkstra都能正确选出后者。5.2 权重设计的具体方案与陷阱实际操作中有几种常用的权重映射方式各有局限性方案公式优点缺点跳数恒为1简单直观忽略关系强弱互动次数倒数1/(count1)反映活跃度次数高可能只是群发消息频率1/(msg_freq1)反映即时联系强度噪声大相似度倒数1/(相似度ε)可用于推荐系统相似度计算成本高一个很容易踩的坑是权重必须满足三角不等式。Floyd算法在数学上不要求权重满足三角不等式它会自行松弛但如果权重设计违背直觉比如A-B很近、B-C很近但A-C路径反而更长结果会很怪。建议先用小样本算出来做业务验证再推到全量。5.3 有向关系关注与被关注不是一回事微博、Twitter这类产品里A关注B不代表B关注A。用Floyd建模时矩阵就不该是对称的。有向图下的人脉定义也要调整从A到B的最短路径代表着A如何通过一连串关注关系触达到B而不是双向朋友链。在这种场景里一个节点若没有关注任何人它的出度就是0若没有人关注它它的入度就是0。算全源距离时很多点对会不可达距离无穷大这是有向图社交网络的正常现象。6. 规模过大时的务实降级方案不是非得用Floyd前面已经说过几十万甚至几亿节点的网络直接用Floyd不现实。那问题来了作为工程师我到底该怎么在真实项目里落实六度人脉最短路径这取决于你的业务形态。6.1 小规模全量计算什么时候可以直接上Floyd如果你的用户量是几千人或者你只是做一个脱敏数据集上的离线分析Floyd是一个非常好的基线工具。它能一次性输出所有用户对之间的距离矩阵后续要算网络平均距离有多少对节点小于6度都很方便。在这种场景下我建议直接用第3节的Python实现甚至可以加上multiprocessing加速。几千节点的稠密分析几分钟内一定能跑完比引入一堆复杂框架划算得多。6.2 点对点查询双向BFS是性价比之王如果业务是用户输入一个目标人物系统返回两人之间的人脉链那这就是单点查询。推荐双向BFS从起点和终点同时BFS每层交替扩展当两边的搜索frontier出现交集时路径就找到了加上深度限制比如最多6层就有很好的响应时间在平均度数几百的网络里6层双向BFS的搜索空间远小于单侧BFS配合Redis或图数据库缓存线上接口能做到毫秒级响应。6.3 Landmark地标法用近似代价换实时性如果产品要求所有用户之间的潜在推荐路径但数据量又大到不能全量Floyd可以考虑地标法Landmark based approximation在全图里选几十个中心用户尽量选高影响力节点比如按PageRank排序选Top-K离线预计算所有节点到这几十个地标的最短路径在线估算dist(u, v) ≈ min_L( dist(u, L) dist(v, L) )真实路径可以通过两个地标路径拼接近似得到地标法牺牲一定准确性但能把O(V^3)问题转化为O(V×K)的预计算加O(K)的在线查询。在六度这种对精度要求不苛刻的业务场景用户不会去验证精确步数性价比很高。6.4 图数据库与分布式图计算大厂常用的底座在工业级社交图谱里最终往往落在图数据库如Neo4j或分布式图计算框架如Spark GraphX、Pregel上Neo4j内置了Cypher shortestPath函数底层用BFS 双向搜索优化能直接从图遍历得到路径不需要手动造矩阵需要在全图上做复杂的距离统计时GraphX的Pregel模型可以分布式计算所有节点的传播路径思路可以看作是并行化的BFS/加权版标签传播如果只是做六度人脉这种深度限制很短的查询图数据库是最合适的载体查询语句几乎不用自己写算法我个人的经验是先明确业务到底是要所有点对距离统计还是单点对查询。前者在数据规模不大时才值得全量Floyd后者在几乎所有规模下都应该用BFS双向搜索 深度限制。Floyd的意义更多在于提供全源视角的思维框架以及在小规模、离线分析场景下做一个准确、可解释的baseline。6.5 六度上限剪枝小世界特性带来的工程红利由于小世界网络的路径长度是对数级绝大多数查询距离都在1到7之间。你可以放心地给搜索模块加一个最大深度6层的切断条件搜不到就返回未找到6度内路径或者转给异步离线任务做全量分析。这样既省了90%的在线计算量又不会让用户体验出现明显问题。这种剪枝在组织架构图谱里同样适用。比如企业内部的找专家功能只要限制协作关系在4跳以内通常就能覆盖绝大多数跨部门触达场景。多跳关系业务价值递减而且路径越长解释越牵强。7. 我实际做社交图谱分析时的一些体会最后说点没有写在算法书里的东西。我在做用户关系链挖掘项目时最开始很迷信全源最短路径这个指标排了一堆Spark任务去算全局距离矩阵结果线上跑了一个星期还没收敛。后来复盘发现产品要的其实只是用户A能不能通过不超过5层的熟人触达用户B并且最好能把中间路径显示出来。这个东西用Neo4j一秒钟就出结果了。为了全量统计而全量统计是最容易踩的坑。另外社交网络的数据清洗很容易让算法结果失真。比如僵尸号、营销号会制造大量假边把路径长度拉得很低一个人有几千好友可能大部分都是弱关系直接参与路径计算会严重偏离真实的人脉体验。我的建议是先把低活跃用户降权或者设置最小互动阈值把活跃度太低的边过滤掉再跑最短路径结果才有参考价值。Floyd算法也许不是工程上处理十亿节点社交网络的首选但它用极简的代码揭示了距离和中介节点的本质关系。当你理解了三重循环为什么k在最外层、理解了路径还原时next矩阵的更新逻辑你会发现BFS、Dijkstra、双向BFS乃至地标法都是在同一棵知识树上针对不同规模、不同约束做的优化分支。六度人脉这个说法再神奇落到计算层面也就是一张图、一个距离矩阵、一条最短路径而已。
阅读完成 · 觉得有帮助？
