社交网络中的图算法：好友推荐、影响力传播与社区发现
一、社交网络不是一张表，是一张有几十亿节点和几百亿边的图
把社交网络当成数据库表来存储和查询，会遗漏其中最核心的信息——关系。用户 A 关注了用户 B，这条关系不仅意味着 A 和 B 有关联，还意味着 A 可能通过 B 认识了 C、A 的社交圈和 B 的社交圈有一定的重叠。这些信息只有在图数据结构中才能被充分利用。
社交网络中的图算法回答这样几个典型的问题：我应该给 A 推荐哪些可能认识的人？B 的一条动态会影响多少人？整个社交网络可以划分成哪几个社区？这三个问题分别对应好友推荐、影响力传播和社区发现——社交网络图算法的三大核心应用。
二、好友推荐的三种算法路径
共同好友（Jaccard 相似度）：这是最直观也最基础的推荐算法。计算两个用户共同好友集合的 Jaccard 相似度：|A的好友 ∩ B的好友| / |A的好友 ∪ B的好友|。相似度高的两个人可能认识。优缺点都很明显：实现简单、可解释性强（"你们有 12 个共同好友"），但只能发现"二度人脉"，无法发现不同社交圈之间潜在的连接。
随机游走（Personalized PageRank）：从一个用户节点出发，在图上游走若干步，统计到达各节点的概率分布。经常被"游走"到的节点就是潜在的推荐对象。随机游走能发现远距离的关系，但计算成本高于共同好友法。
图神经网络 Embedding：用 GraphSAGE 或 GAT 等 GNN 模型，为每个用户学习一个低维 embedding 向量。向量距离近的用户就是潜在的推荐对象。GNN 方案的优势是能学到非线性的复杂关系模式，但需要大量训练数据和 GPU 算力。
""" 二度好友推荐算法实现 基于 BFS 遍历：找出"好友的好友"中非好友的用户 用共同好友数排序，推荐 Top K 时间复杂度：O(K * avg_degree^2) 空间复杂度：O(N) 用于存储访问标记 为什么在实际社交网络中复杂度可接受： - avg_degree 通常在几十到几百之间（不是稠密图） - 每个用户的好友推荐计算是独立的，可以并行 """ from collections import defaultdict, deque class FriendRecommendation: def recommend(self, graph, user_id, top_k=10): """ 为指定用户推荐可能认识的人 Args: graph: 邻接表形式 {user_id: set(friend_ids)} user_id: 目标用户 top_k: 推荐数量 """ if user_id not in graph: return [] user_friends = graph[user_id] candidates = defaultdict(int) # 候选用户 → 共同好友数 # 遍历所有直接好友 for friend in user_friends: # 遍历好友的好友 if friend not in graph: continue for friend_of_friend in graph[friend]: # 排除自己、已经是好友的人 if (friend_of_friend != user_id and friend_of_friend not in user_friends): candidates[friend_of_friend] += 1 # 按共同好友数降序排列 sorted_candidates = sorted( candidates.items(), key=lambda x: x[1], reverse=True ) return [ { "user_id": uid, "common_friends": count, "reason": f"你们有 {count} 个共同好友" } for uid, count in sorted_candidates[:top_k] ]三、影响力传播与关键节点发现
影响力传播要解决的问题是：如果用户 A 发布了一条信息，这条信息会通过社交网络传播到哪里？一个相关的问题是：如果要让一条信息覆盖尽可能多的用户，应该先从哪些用户开始推广？
独立级联模型（IC Model）：每条边有一个传播概率 p。当一个节点被激活（接收到信息）时，它会以概率 p 尝试激活它的每个邻居。这个过程不断重复，直到没有新节点被激活。通过蒙特卡洛模拟多次，可以估算影响力传播的范围。
关键节点发现：找出社交网络中对信息传播贡献最大的节点。常用的方法包括度中心性（好友数量多）、介数中心性（处于最多最短路径上的节点）、PageRank 值高。在商业场景中，这些就是"关键意见领袖"（KOL）的算法化识别。
四、社区发现的实际应用
社区发现把社交网络中的用户划分成若干个内部联系紧密、外部联系稀疏的群体。在工程中，这不仅是一个图算法的结果，更是一个可以服务于业务推荐的基础设施。
- 精准推荐：同一个社区内用户的行为模式相似，社区内热门的内容可以作为推荐项。
- 用户画像：一个用户所属的社区反映了其社交圈层特征（如"技术讨论圈"、"游戏爱好者圈"）。
- 舆情监控：不同社区对同一事件的观点可能不同，社区发现可以帮助追踪舆情在不同圈层的传播差异。
Louvain 算法是最广泛使用的社区发现算法之一。它通过迭代优化"模块度"（modularity，衡量社区内连接密度与随机期望的差异）来发现社区结构。算法过程是：初始化每个节点为一个社区 → 逐个尝试将节点移到邻居社区，若模块度提升则移动 → 将社区压缩为超节点 → 重复以上步骤直到模块度不再提升。
五、总结
图算法给社交网络的数据分析提供了一套独特的视角。共同好友算法让好友推荐有了最简单有效的基线，随机游走和图神经网络在不同复杂度的场景下有各自的适用空间。影响力传播让信息扩散从"拍脑袋估算"变成了可量化的模拟。社区发现在用户画像和精准推荐中持续发挥作用。对这些算法的理解，不需要深入到每个数学公式的推导细节，但需要知道它们各自解决什么问题、输入输出是什么、复杂度大概是多少——这样才能在实际的社交网络工程中做出正确的算法选型。
