链路预测中共同邻居算法

共同邻居算法是链路预测中比较经典的方法之一，它的基本思想是如果两个节点有许多共同的邻居节点，那么它们之间很可能存在一条边。下面是一个简单的Python代码示例，演示如何使用共同邻居算法进行链路预测：

import networkx as nx
import numpy as np

# 构造图
G = nx.karate_club_graph()

# 划分训练集和测试集
edges = np.array(G.edges())
num_test = int(len(edges) * 0.2)
np.random.shuffle(edges)
test_edges = edges[:num_test]
train_edges = edges[num_test:]

# 构造训练集和测试集
train_graph = nx.Graph()
train_graph.add_edges_from(train_edges)
test_graph = nx.Graph()
test_graph.add_edges_from(test_edges)

# 计算共同邻居数
common_neighbors = {}
for u, v in test_edges:
    neighbors1 = set(train_graph.neighbors(u))
    neighbors2 = set(train_graph.neighbors(v))
    common = neighbors1.intersection(neighbors2)
    common_neighbors[(u, v)] = len(common)

# 按共同邻居数排序，预测前K条边
k = 10
sorted_edges = sorted(common_neighbors.keys(), key=lambda x: -common_neighbors[x])
pred_edges = sorted_edges[:k]

# 计算准确率和召回率
true_positives = set(pred_edges).intersection(set(test_edges))
precision = len(true_positives) / k
recall = len(true_positives) / len(test_edges)
print('准确率：', precision)
print('召回率：', recall)

代码首先构造了一个karate_club_graph图，然后将图的边随机划分为训练集和测试集。接着使用训练集构造了一个新的图，然后对测试集中的每一条边计算共同邻居数，并按共同邻居数排序。预测前K条边作为预测结果，然后计算准确率和召回率。需要注意的是，在实际应用中还需要进行交叉验证等步骤来评估模型性能。