用Python+NetworkX实战：手把手教你用传统图算法实现社交好友推荐

社交网络中的好友推荐一直是互联网产品提升用户粘性的核心功能。与深度学习等"黑箱"方法相比，基于图特征的传统算法具有可解释性强、计算资源消耗低等独特优势。本文将以微信/微博好友关系为场景，使用NetworkX库演示如何通过 共同邻居 、 Adamic-Adar指数 等经典图特征，构建一个可解释的推荐系统。

1. 环境准备与数据建模

在开始之前，我们需要准备Python环境和示例数据集。推荐使用Jupyter Notebook进行交互式开发：

pip install networkx pandas numpy matplotlib scikit-learn

假设我们已经从社交平台API获取了好友关系数据，可以将其建模为无向图。这里用模拟数据演示构建邻接矩阵的过程：

import networkx as nx
import pandas as pd

# 模拟用户好友关系数据
relations = [
    ("小明", "小红"), ("小明", "小刚"), 
    ("小红", "小美"), ("小刚", "小强"),
    ("小美", "小丽"), ("小强", "小丽")
]

# 创建无向图
G = nx.Graph()
G.add_edges_from(relations)

使用NetworkX的可视化功能可以直观查看社交网络结构：

import matplotlib.pyplot as plt

plt.figure(figsize=(8,6))
nx.draw(G, with_labels=True, node_color='lightblue', 
        edge_color='gray', node_size=800)
plt.title("社交网络关系图")
plt.show()

2. 关键图特征计算实战

传统图算法依赖精心设计的特征工程。下面介绍三种在社交网络中表现优异的特征计算方法。

2.1 共同邻居(Common Neighbors)

这是最直观的相似度度量，计算公式简单：

CN(u,v) = |N(u) ∩ N(v)|

其中N(u)表示用户u的好友集合。NetworkX内置了计算方法：

# 计算所有可能的用户对
all_pairs = [(u, v) for u in G.nodes() for v in G.nodes() if u < v]

# 计算共同邻居特征
cn_features = {}
for u, v in all_pairs:
    cn_features[(u, v)] = len(list(nx.common_neighbors(G, u, v)))

pd.DataFrame.from_dict(cn_features, orient='index', columns=['CN'])

结果显示小美和小强有1个共同邻居(小丽)，而小明和小丽没有共同好友。

2.2 Adamic-Adar指数

该算法改进了共同邻居方法，给予低度数共同好友更高权重：

AA(u,v) = Σ(1/log|N(z)|) ，z∈N(u)∩N(v)

实现代码：

aa_features = {}
for u, v in all_pairs:
    aa_features[(u, v)] = nx.adamic_adar_index(G, [(u, v)])[0][2]

pd.DataFrame.from_dict(aa_features, orient='index', columns=['AA'])

2.3 Katz指数

考虑全局网络结构的特征，计算所有长度路径的加权和：

Katz(u,v) = Σβ^l * |paths(u,v) of length l|

β是衰减因子(通常取0.005-0.05)：

def katz_index(graph, beta=0.02):
    A = nx.adjacency_matrix(graph).todense()
    I = np.identity(len(graph.nodes()))
    S = np.linalg.inv(I - beta * A) - I
    return S

katz_scores = katz_index(G)

3. 构建推荐系统流水线

有了特征后，我们需要将其整合到机器学习流程中。以下是完整实现步骤：

3.1 特征矩阵构建

将多种特征组合成训练数据：

features = []
for u, v in all_pairs:
    features.append([
        len(list(nx.common_neighbors(G, u, v))),
        nx.adamic_adar_index(G, [(u, v)])[0][2],
        katz_scores[list(G.nodes()).index(u), list(G.nodes()).index(v)]
    ])

X = pd.DataFrame(features, columns=['CN', 'AA', 'Katz'])

3.2 标签生成与模型训练

假设我们已经通过业务规则生成了标签(1表示应该推荐，0表示不推荐)：

from sklearn.linear_model import LogisticRegression

# 示例标签 (实际应从业务数据获取)
y = [0, 1, 0, 0, 1, 0, 0, 0, 0, 1]  

model = LogisticRegression()
model.fit(X, y)

3.3 推荐结果生成

对新用户对进行预测：

def recommend_new_pairs(model, graph, user_list, threshold=0.7):
    recommendations = []
    for u in user_list:
        for v in graph.nodes():
            if u != v and not graph.has_edge(u, v):
                cn = len(list(nx.common_neighbors(graph, u, v)))
                aa = nx.adamic_adar_index(graph, [(u, v)])[0][2]
                katz = katz_scores[list(graph.nodes()).index(u), list(graph.nodes()).index(v)]
                proba = model.predict_proba([[cn, aa, katz]])[0][1]
                if proba >= threshold:
                    recommendations.append((u, v, proba))
    return sorted(recommendations, key=lambda x: -x[2])

recommend_new_pairs(model, G, ['小明', '小美'])

4. 方案优化与生产部署

在实际业务场景中，我们还需要考虑以下优化方向：

4.1 特征工程增强

特征类型	计算方法	适用场景
资源分配指数	RA = Σ(1/	N(z)
Jaccard系数	J =	N(u)∩N(v)
偏好依附	PA =	N(u)

4.2 负样本策略

社交网络中的隐式负样本(未连接的用户对)需要谨慎处理：

1. 随机采样：从无连接的节点对中随机选择
2. 基于距离：选择超过2跳的节点对
3. 基于时间：选择近期活跃但未连接的用户

4.3 工程化部署建议

# 生产环境推荐使用稀疏矩阵存储
from scipy import sparse

def large_scale_katz_index(graph, beta=0.02, iterations=100):
    """迭代法计算Katz指数，适用于大规模图"""
    A = nx.adjacency_matrix(graph)
    x = np.ones(A.shape[0])
    katz = x.copy()
    for _ in range(iterations):
        x = beta * A.dot(x)
        katz += x
    return katz

对于超大规模社交网络(>100万节点)，可以考虑：

• 使用Spark GraphX进行分布式计算
• 对图进行社区检测后分块处理
• 采用近似算法降低计算复杂度

5. 传统方法的独特价值

尽管深度学习在推荐系统中大放异彩，传统图算法仍具有不可替代的优势：

1. 可解释性 ：每个特征都有明确的网络学含义
2. 冷启动友好 ：不需要大量训练数据
3. 计算高效 ：适合实时性要求高的场景
4. 可组合性 ：可以作为深度学习模型的输入特征

在实际项目中，我通常采用混合策略：先用传统方法快速搭建基线系统，再逐步引入深度学习组件。特别是在数据稀疏的业务初期，基于共同邻居的简单方法往往能带来出乎意料的好效果。