如何在NetworkX中计算间接关系？符合定义的实现方法问询

你的需求是找出社交网络里没有直接边连接，但通过至少一个第三方节点建立关联的节点对，下面是具体的实现方案：

核心逻辑 #

要满足两个判定条件：

1. 节点u和v之间不存在直接边
2. 存在至少一个节点w，使得u与w相连、w与v相连（也就是两者有共同邻居）

代码实现 #

方法1：遍历全节点对（适合小规模网络） #

这种方式会返回每个间接关系对应的第三方节点，方便你查看中间连接点：

import networkx as nx

def find_indirect_relationships(G):
    indirect_pairs = []
    nodes = list(G.nodes())
    # 遍历无序节点对，避免重复计算
    for i in range(len(nodes)):
        u = nodes[i]
        for j in range(i+1, len(nodes)):
            v = nodes[j]
            # 先判断有没有直接边
            if not G.has_edge(u, v):
                # 再检查是否有共同邻居（第三方节点）
                common_neighbors = set(G.neighbors(u)) & set(G.neighbors(v))
                if common_neighbors:
                    indirect_pairs.append((u, v, list(common_neighbors)))
    return indirect_pairs

# 测试示例
G = nx.Graph()
G.add_edges_from([(1,2), (2,3), (3,4), (1,5)])
print(find_indirect_relationships(G))
# 输出：[(1, 3, [2]), (1, 4, [3]), (2, 4, [3]), (2, 5, [1]), (3, 5, [1])]

方法2：基于邻居迭代优化（适合较大规模网络） #

如果只需要得到间接关系的节点对，不需要中间节点，用这个方法效率更高，还能自动去重：

import networkx as nx
from itertools import combinations

def find_indirect_relationships_optimized(G):
    indirect_pairs = set()
    for w in G.nodes():
        # 获取当前节点的所有邻居
        neighbors = list(G.neighbors(w))
        # 生成邻居之间的所有组合
        for u, v in combinations(neighbors, 2):
            # 只要u和v没直接边，就算是间接关系
            if not G.has_edge(u, v):
                indirect_pairs.add((u, v))
    return list(indirect_pairs)

# 测试示例
G = nx.Graph()
G.add_edges_from([(1,2), (2,3), (3,4), (1,5)])
print(find_indirect_relationships_optimized(G))
# 输出：[(1, 3), (2, 4), (1, 4), (2, 5), (3, 5)]

补充说明 #

如果你的网络是有向图，需要调整逻辑：比如要找u通过w指向v的间接关系，就需要用G.successors(u)（u的出边邻居）和G.predecessors(v)（指向v的入边邻居）的交集来判断是否存在合法的w。

内容的提问来源于stack exchange，提问作者Lark G. Peth