likes
comments
collection
share

29. 基于图的基础推荐方式-链路预测

作者站长头像
站长
· 阅读数 48

基于图的基础推荐方式-链路预测

在复杂网络中，链路预测是一种常用的推荐方法，主要用于预测网络中可能存在但尚未观察到的边。它广泛应用于社交网络推荐、生物信息网络、文献网络等多个领域。本文将介绍链路预测的基本概念、方法和数学原理。

什么是链路预测？

链路预测的目标是根据网络中已有的节点和边的信息，预测哪些节点对之间可能存在边。简单来说，它试图找出图中缺失的边或未来可能形成的边。

链路预测的基本方法

链路预测方法大体可以分为三类：基于邻近性的方法、基于路径的方法和基于学习的方法。

1. 基于邻近性的方法

在链路预测中，基于邻近性的方法是一种简单且直观的策略，通过计算节点对间的邻近性分数来预测它们之间是否可能存在边。这里将详细介绍几种常用的邻近性指标，并提供Python代码示例，使用NetworkX库来实现这些方法。

1. 共同邻居 (Common Neighbors)

共同邻居是两个节点共享的邻居节点的数量。如果两个节点有更多的共同邻居，它们之间存在边的可能性通常会更高。

公式:

CN(x,y)=∣Γ(x)∩Γ(y)∣CN(x, y) = |\Gamma(x) \cap \Gamma(y)|CN(x,y)=∣Γ(x)∩Γ(y)∣

其中，Γ(x)\Gamma(x)Γ(x) 是节点 xxx 的邻居集合。

代码示例:

import networkx as nx

# 创建图
G = nx.Graph()
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("D", "E")]
G.add_edges_from(edges)

# 计算节点A和节点D的共同邻居数量
common_neighbors = list(nx.common_neighbors(G, "A", "D"))
common_neighbors_count = len(common_neighbors)
print("共同邻居:", common_neighbors)
print("共同邻居数量:", common_neighbors_count)

2. Jaccard 系数

Jaccard 系数衡量两个集合的交集大小与并集大小的比例，用于评估两个节点邻居的相似度。

公式:

J(x,y)=∣Γ(x)∩Γ(y)∣∣Γ(x)∪Γ(y)∣J(x, y) = \frac{|\Gamma(x) \cap \Gamma(y)|}{|\Gamma(x) \cup \Gamma(y)|}J(x,y)=∣Γ(x)∪Γ(y)∣∣Γ(x)∩Γ(y)∣​

代码示例:

# 计算节点A和节点D的Jaccard系数
jaccard_coefficient = list(nx.jaccard_coefficient(G, [("A", "D")]))
print("Jaccard系数:", jaccard_coefficient)

3. Adamic/Adar 指数

这个指标是基于共同邻居，但给予那些邻居节点较少的节点更高的权重，认为这些节点的连接更为珍贵。

公式:

AA(x,y)=∑z∈Γ(x)∩Γ(y)1log⁡∣Γ(z)∣AA(x, y) = \sum_{z \in \Gamma(x) \cap \Gamma(y)} \frac{1}{\log |\Gamma(z)|}AA(x,y)=z∈Γ(x)∩Γ(y)∑​log∣Γ(z)∣1​

代码示例:

# 计算节点A和节点D的Adamic/Adar指数
adamic_adar_index = list(nx.adamic_adar_index(G, [("A", "D")]))
print("Adamic/Adar指数:", adamic_adar_index)

这些基于邻近性的方法非常适合于社交网络、合作网络等领域，可以有效地预测哪些人或实体可能会建立新的联系。通过简单的示例和代码，我们展示了如何使用NetworkX库来计算链路预测的关键指标，为进一步的网络分析和推荐系统提供支持。

2. 基于路径的方法

基于路径的方法在链路预测中尤其重要，因为它们不仅关注局部邻近性，还考虑了节点之间通过不同路径的远程连接。这类方法通常利用图中的全局信息，如路径长度和路径数目，来评估两个节点间的连接可能性。

1. Katz 指数

Katz 指数是一个经典的基于路径的链路预测指标，它直接总结了所有通过中间节点连接两个节点的路径，对较短的路径赋予更高的权重。公式如下：

Katz(x,y)=∑l=1∞βl⋅∣pathsx,y<l>∣Katz(x,y) = \sum_{l=1}^{\infty} \beta^l \cdot |paths_{x,y}^{<l>}|Katz(x,y)=l=1∑∞​βl⋅∣pathsx,y<l>​∣

其中，∣pathsx,y<l>∣|paths_{x,y}^{<l>}|∣pathsx,y<l>​∣ 是从节点 xxx 到节点 yyy 的长度为 lll 的路径数目，β\betaβ 是衰减因子，用于控制路径长度的影响力。β\betaβ 的值越小，对较长路径的惩罚越大。 我们可以使用 Python 的 networkx 库来演示如何计算 Katz 指数。假设我们有一个简单的网络图，我们将计算每对节点间的 Katz 指数。

import networkx as nx

# 创建图
G = nx.Graph()
edges = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')]
G.add_edges_from(edges)

# 计算 Katz 指数
# NetworkX 提供了一个方法来计算整个图的 Katz centrality
# 这里我们将使用较小的 beta 值
katz = nx.katz_centrality(G, alpha=0.005, beta=1.0)
print("Katz centrality:")
for node, centrality in katz.items():
    print(f"{node}: {centrality:.4f}")

在这个示例中，我们初始化了一个图并添加了几条边，然后计算了图中所有节点的 Katz centrality。在实际应用中，Katz 指数可用于预测节点之间未来可能形成的链路。

Katz 指数不仅可以用于社交网络分析，还可以用于推荐系统（如推荐可能感兴趣的朋友或产品）、生物信息学（如预测蛋白质间的交互关系）等场景。通过这种方法，我们可以利用图中的全局信息，比单纯基于邻近性的方法能提供更多的上下文和洞察力，特别是在网络结构复杂且节点间联系紧密的情况下。

2. Random Walk with Restart (RWR)

Random Walk with Restart 是一种基于随机游走模型的链路预测方法，它模拟了一个从一个指定节点开始随机游走并有一定概率返回起点的过程。RWR 特别适用于那些需要评估节点间重要性或相似度的应用场景。

rn+1=(1−c)⋅M⋅rn+c⋅er_{n+1} = (1-c) \cdot M \cdot r_n + c \cdot ern+1​=(1−c)⋅M⋅rn​+c⋅e

在上述公式中，rnr_nrn​ 是节点的重要性向量，在每一步中都会更新。MMM 是转移矩阵，eee 是起始节点向量，ccc 是重启概率。当ccc较大时，游走更倾向于返回初始节点，这增加了游走的局部性。

3. Rooted PageRank

Rooted PageRank 是 PageRank 的一个变体，用于链路预测。它结合了 PageRank 算法的全局评分系统和 RWR 的局部性特点，通过为每个节点定制 PageRank 计算来预测节点间的链路。

PR(u)=α∑v∈BuPR(v)L(v)+(1−α)1NPR(u) = \alpha \sum_{v \in B_u} \frac{PR(v)}{L(v)} + (1-\alpha) \frac{1}{N}PR(u)=αv∈Bu​∑​L(v)PR(v)​+(1−α)N1​

其中，BuB_uBu​ 是指向节点 uuu 的邻接节点集，L(v)L(v)L(v) 是节点 vvv 的链接数，α\alphaα 是转移概率，NNN 是网络中的节点总数。

4. Hitting Time

Hitting Time 是测量在随机游走中，从节点 uuu 开始首次到达节点 vvv 需要的平均步数。这个指标反映了两个节点间的连接紧密程度。如果 Hitting Time 值较低，意味着两个节点之间更可能存在直接或间接的强连接。

H(u,v)=E[steps from u to v]H(u, v) = E[\text{steps from } u \text{ to } v]H(u,v)=E[steps from u to v]

我们可以使用 Python 的 networkx 库来演示如何计算 Rooted PageRank。以下是一个简单的代码示例：

import networkx as nx

# 创建图
G = nx.DiGraph()
edges = [('A', 'B'), ('B', 'C'), ('A', 'C'), ('C', 'A')]
G.add_edges_from(edges)

# 计算 Rooted PageRank
personalized = {'A': 1}
rpr = nx.pagerank(G, alpha=0.85, personalization=personalized)
print("Rooted PageRank from node A:")
for node, score in rpr.items():
    print(f"{node}: {score:.4f}")

在这个示例中，我们计算了以节点 'A' 为起点的 Rooted PageRank，这有助于预测从 'A' 出发最可能到达哪些节点。

通过以上方法，基于路径的链路预测能够有效地利用网络中的路径信息，帮助预测和理解节点间潜在的关系。

3. 基于学习的方法

基于学习的方法在链路预测中使用数据驱动的技术来预测图中的潜在链接。这些方法通常依赖于机器学习和深度学习模型，以学习和挖掘节点特征和结构之间的复杂模式。

1.图神经网络（GNNs）

图神经网络（GNNs）是目前最流行的基于学习的方法之一。GNNs 能够直接在图结构上操作，通过聚合邻居信息来更新节点的表示。常见的GNN变体包括：

  • 图卷积网络（GCN） ：利用节点的邻域信息通过卷积层传播节点特征，从而学习节点的有效表示。
  • 图注意力网络（GAT） ：通过注意力机制来动态地权衡邻居节点的重要性。
  • 图自编码器（GAE） ：使用编码器将节点映射到低维空间，再通过解码器重建图的结构。

下面是使用 PyTorch Geometric 实现的 GCN 进行链路预测的简单示例：

    import torch
from torch_geometric.datasets import Planetoid
import torch_geometric.transforms as T
from torch_geometric.nn import GCNConv

# 加载数据集
dataset = Planetoid(root='/tmp/Cora', name='Cora', transform=T.NormalizeFeatures())

class GCN(torch.nn.Module):
    def __init__(self):
        super(GCN, self).__init__()
        self.conv1 = GCNConv(dataset.num_node_features, 16)
        self.conv2 = GCNConv(16, dataset.num_classes)

    def forward(self, data):
        x, edge_index = data.x, data.edge_index
        x = torch.relu(self.conv1(x, edge_index))
        x = torch.dropout(x, 0.5, training=self.training)
        x = self.conv2(x, edge_index)
        return torch.log_softmax(x, dim=1)

model = GCN()
data = dataset[0]
out = model(data)
print(out)

2. 自动编码器

自动编码器在图数据上的应用主要通过学习每个节点的压缩表示来预测节点间的潜在链接。图自编码器通常包括两部分：

  1. 编码器：将高维的节点特征压缩到低维空间。
  2. 解码器：使用低维表示来重建图的邻接矩阵。

3. 深度学习与传统特征结合

在一些高级的链路预测模型中，研究人员将传统的图特征（如共同邻居、Jaccard系数）与通过深度学习模型学习到的特征结合起来，以此来增强模型的预测能力。这种融合方法可以提高链路预测的准确率和鲁棒性。

应用示例

假设我们有一个社交网络图，我们想预测哪些用户可能会成为朋友。通过计算不同用户对的Jaccard系数，我们可以预测哪些用户对之间最可能形成新的连接。

结论

链路预测作为一种基于图的推荐方法，不仅可以帮助我们理解和预测社交网络中的关系形成，还可以用于推荐系统、生物网络分析等领域。随着图数据和图处理技术的发展，链路预测的准确性和应用范围预计将进一步扩大。

转载自:https://juejin.cn/post/7366824731955920948
评论
请登录