Python案例如何用Networkx做网络对齐

wen python案例 2026-07-15 120

本文目录导读：

基于网络拓扑结构的对齐
基于特征向量中心性的对齐
基于图核的对齐
基于相似度矩阵的对齐
可视化对齐结果
完整的对齐评估
注意事项

我来介绍如何使用NetworkX进行网络对齐，网络对齐是一种将不同网络的节点进行匹配的技术,这里介绍几种常见的方法：

基于网络拓扑结构的对齐

基本图匹配示例

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import linear_sum_assignment
# 创建两个相似的图
def create_example_graphs():
    # 图1：原始图
    G1 = nx.Graph()
    edges1 = [(1,2), (1,3), (2,3), (3,4), (4,5)]
    G1.add_edges_from(edges1)
    # 图2：带有噪声的图（某些节点被重标号）
    G2 = nx.Graph()
    edges2 = [(6,7), (6,8), (7,8), (8,9), (9,10)]  # 类似结构但不同标签
    G2.add_edges_from(edges2)
    return G1, G2
# 基于度的简单对齐方法
def degree_based_alignment(G1, G2):
    """基于节点度进行对齐"""
    # 获取每个图的节点度排序
    degrees1 = sorted([(d, n) for n, d in G1.degree()], reverse=True)
    degrees2 = sorted([(d, n) for n, d in G2.degree()], reverse=True)
    alignment = {}
    for (d1, n1), (d2, n2) in zip(degrees1, degrees2):
        alignment[n1] = n2
    return alignment
# 示例使用
G1, G2 = create_example_graphs()
alignment = degree_based_alignment(G1, G2)
print("基于度的对齐结果：")
for n1, n2 in alignment.items():
    print(f"节点 {n1} (度={G1.degree(n1)}) <-> 节点 {n2} (度={G2.degree(n2)})")

基于特征向量中心性的对齐

def eigenvector_alignment(G1, G2):
    """基于特征向量中心性进行对齐"""
    # 计算特征向量中心性
    cent1 = nx.eigenvector_centrality(G1)
    cent2 = nx.eigenvector_centrality(G2)
    # 按中心性排序
    nodes1 = sorted(cent1.keys(), key=lambda x: cent1[x], reverse=True)
    nodes2 = sorted(cent2.keys(), key=lambda x: cent2[x], reverse=True)
    alignment = {}
    for n1, n2 in zip(nodes1, nodes2):
        alignment[n1] = n2
    return alignment
# 示例
eig_alignment = eigenvector_alignment(G1, G2)
print("\n基于特征向量中心性的对齐结果：")
for n1, n2 in eig_alignment.items():
    print(f"节点 {n1} (中心性={eig_alignment[n1]:.3f}) <-> 节点 {n2}")

基于图核的对齐

def weisfeiler_lehman_alignment(G1, G2, iterations=3):
    """基于Weisfeiler-Lehman图核的对齐"""
    from networkx.algorithms.graph_hashing import weisfeiler_lehman_graph_hash
    # 对每个节点获取其WL特征
    def get_wl_features(G, iterations):
        features = {}
        for node in G.nodes():
            # 创建以该节点为中心的局部子图
            subgraph = nx.ego_graph(G, node, radius=iterations)
            features[node] = weisfeiler_lehman_graph_hash(subgraph, iterations=iterations)
        return features
    features1 = get_wl_features(G1, iterations)
    features2 = get_wl_features(G2, iterations)
    # 匹配具有相同特征的节点
    alignment = {}
    matched2 = set()
    for n1, feat1 in features1.items():
        best_match = None
        for n2, feat2 in features2.items():
            if n2 not in matched2 and feat1 == feat2:
                best_match = n2
                break
        if best_match:
            alignment[n1] = best_match
            matched2.add(best_match)
    return alignment
# 示例
wl_alignment = weisfeiler_lehman_alignment(G1, G2)
print("\n基于WL图核的对齐结果：")
for n1, n2 in wl_alignment.items():
    print(f"节点 {n1} <-> 节点 {n2}")

基于相似度矩阵的对齐

def similarity_matrix_alignment(G1, G2):
    """基于节点相似度矩阵的对齐方法"""
    # 计算节点特征
    def get_node_features(G):
        features = []
        for node in G.nodes():
            # 提取特征：度、聚类系数、PageRank值等
            deg = G.degree(node)
            cluster_coef = nx.clustering(G, node)
            pagerank = nx.pagerank(G)[node]
            features.append([deg, cluster_coef, pagerank])
        return np.array(features)
    # 获取特征矩阵
    features1 = get_node_features(G1)
    features2 = get_node_features(G2)
    # 计算相似度矩阵（使用欧氏距离）
    n1, n2 = len(features1), len(features2)
    similarity_matrix = np.zeros((n1, n2))
    for i in range(n1):
        for j in range(n2):
            # 使用负的欧氏距离作为相似度
            dist = np.linalg.norm(features1[i] - features2[j])
            similarity_matrix[i][j] = -dist
    # 使用匈牙利算法找到最优匹配
    row_ind, col_ind = linear_sum_assignment(-similarity_matrix)
    # 构建对齐
    nodes1 = list(G1.nodes())
    nodes2 = list(G2.nodes())
    alignment = {}
    for i, j in zip(row_ind, col_ind):
        alignment[nodes1[i]] = nodes2[j]
    return alignment
# 示例
sim_alignment = similarity_matrix_alignment(G1, G2)
print("\n基于相似度矩阵的对齐结果：")
for n1, n2 in sim_alignment.items():
    print(f"节点 {n1} <-> 节点 {n2}")

可视化对齐结果

def visualize_alignment(G1, G2, alignment, title="Network Alignment"):
    """可视化两个网络的对齐结果"""
    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5))
    # 绘制第一个网络
    pos1 = nx.spring_layout(G1)
    nx.draw(G1, pos1, with_labels=True, node_color='lightblue', 
            node_size=500, font_size=10, font_weight='bold', ax=ax1)
    ax1.set_title("Graph 1")
    # 绘制第二个网络
    pos2 = nx.spring_layout(G2)
    nx.draw(G2, pos2, with_labels=True, node_color='lightgreen', 
            node_size=500, font_size=10, font_weight='bold', ax=ax2)
    ax2.set_title("Graph 2")
    plt.suptitle(title)
    plt.tight_layout()
    plt.show()
    # 打印对齐关系
    print("\n对齐映射：")
    print("="*30)
    for n1, n2 in alignment.items():
        color1 = 'blue' if G1.has_edge(*list(alignment.keys())[:2]) else 'black'
        print(f"Source: {n1} -> Target: {n2}")
# 执行可视化
if __name__ == "__main__":
    G1, G2 = create_example_graphs()
    alignment = similarity_matrix_alignment(G1, G2)
    visualize_alignment(G1, G2, alignment)

完整的对齐评估

def evaluate_alignment(G1, G2, alignment):
    """评估对齐质量"""
    # 计算边缘保守性
    edge_preservation = 0
    total_edges1 = G1.number_of_edges()
    for u, v in G1.edges():
        if u in alignment and v in alignment:
            u2, v2 = alignment[u], alignment[v]
            if G2.has_edge(u2, v2):
                edge_preservation += 1
    edge_preservation_ratio = edge_preservation / total_edges1 if total_edges1 > 0 else 0
    # 计算节点度差异
    degree_diff = 0
    for u, v in alignment.items():
        degree_diff += abs(G1.degree(u) - G2.degree(v))
    avg_degree_diff = degree_diff / len(alignment) if alignment else 0
    print("对齐评估结果：")
    print(f"边缘保守性：{edge_preservation_ratio:.2%}")
    print(f"平均度差异：{avg_degree_diff:.2f}")
    return {
        'edge_preservation': edge_preservation_ratio,
        'avg_degree_diff': avg_degree_diff
    }
# 评估示例
results = evaluate_alignment(G1, G2, alignment)