Python读取城市数据文件异常，求多种图中心性手动实现方法

错误原因 #

代码中使用split('\t')按制表符分割行，但实际文件是用多个空格作为分隔符，且部分城市名包含空格（如Rimnicu Vilcea），导致分割后无法解包为city, latitude, longitude三个变量，触发ValueError。

修复后的代码 #

def read_city_data(file_path):
    cities = {}
    with open(file_path, 'r') as file:
        next(file)  # 跳过表头行
        for line in file:
            line = line.strip()
            if not line:
                continue  # 跳过空行
            try:
                # 使用maxsplit=2分割，确保城市名中的空格被保留
                parts = line.split(maxsplit=2)
                if len(parts) != 3:
                    print("skipped: 格式错误")
                    continue
                city, latitude, longitude = parts
                cities[city] = (float(latitude), float(longitude))
            except ValueError as e:
                print(f"skipped: {str(e)}")
                continue
    return cities

假设图用邻接表表示（示例结构如下）：

# 示例城市连接图，需根据实际关系补充完整
graph = {
    'Oradea': ['Zerind', 'Sibiu'],
    'Zerind': ['Oradea', 'Arad'],
    'Arad': ['Zerind', 'Timisoara', 'Sibiu'],
    'Timisoara': ['Arad', 'Lugoj'],
    # 其他城市连接关系...
}

1. 度中心性（Degree Centrality） #

节点的直接连接数占总节点数的比例，归一化后更具可比性：

def degree_centrality(graph):
    total_nodes = len(graph)
    if total_nodes <= 1:
        return {node: 0.0 for node in graph}
    centrality = {}
    for node in graph:
        degree = len(graph[node])
        centrality[node] = degree / (total_nodes - 1)
    return centrality

2. 接近中心性（Closeness Centrality） #

节点到所有其他节点最短路径平均长度的倒数，反映节点在图中的“可达性”：

import math

def bfs_shortest_paths(graph, start):
    """用BFS计算从起点到所有节点的最短路径长度"""
    distances = {node: math.inf for node in graph}
    distances[start] = 0
    queue = [start]
    while queue:
        current = queue.pop(0)
        for neighbor in graph[current]:
            if distances[neighbor] == math.inf:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    return distances

def closeness_centrality(graph):
    total_nodes = len(graph)
    if total_nodes <= 1:
        return {node: 0.0 for node in graph}
    centrality = {}
    for node in graph:
        distances = bfs_shortest_paths(graph, node)
        # 过滤无法到达的节点（连通图可忽略此步骤）
        reachable_dists = [d for d in distances.values() if d != math.inf]
        if not reachable_dists:
            centrality[node] = 0.0
            continue
        sum_dist = sum(reachable_dists)
        # 归一化处理
        centrality[node] = (len(reachable_dists) - 1) / sum_dist
    return centrality

3. 介数中心性（Betweenness Centrality） #

计算节点作为其他节点对最短路径中间节点的次数占比，反映节点的“桥梁”作用：

def betweenness_centrality(graph):
    total_nodes = len(graph)
    if total_nodes <= 2:
        return {node: 0.0 for node in graph}
    centrality = {node: 0.0 for node in graph}
    
    for s in graph:
        # BFS统计最短路径数和前驱节点
        stack = []
        predecessors = {node: [] for node in graph}
        path_counts = {node: 0 for node in graph}
        distances = {node: math.inf for node in graph}
        distances[s] = 0
        path_counts[s] = 1
        queue = [s]
        
        while queue:
            v = queue.pop(0)
            stack.append(v)
            for w in graph[v]:
                if distances[w] == math.inf:
                    distances[w] = distances[v] + 1
                    queue.append(w)
                if distances[w] == distances[v] + 1:
                    path_counts[w] += path_counts[v]
                    predecessors[w].append(v)
        
        # 累积介数值
        dependency = {node: 0.0 for node in graph}
        while stack:
            w = stack.pop()
            for v in predecessors[w]:
                dependency[v] += (path_counts[v] / path_counts[w]) * (1 + dependency[w])
                if w != s:
                    centrality[w] += dependency[w]
    
    # 归一化（无向图公式）
    norm = (total_nodes - 1) * (total_nodes - 2)
    if norm != 0:
        for node in centrality:
            centrality[node] /= norm
    return centrality

4. 特征向量中心性（Eigenvector Centrality） #

基于邻接矩阵特征向量计算，优先考虑连接高中心性节点的节点：

def eigenvector_centrality(graph, max_iter=100, tol=1e-6):
    nodes = list(graph.keys())
    n = len(nodes)
    if n == 0:
        return {}
    # 初始化中心性值
    centrality = {node: 1.0 for node in nodes}
    
    for _ in range(max_iter):
        new_centrality = {}
        max_diff = 0.0
        # 计算每个节点的邻居中心性之和
        for node in nodes:
            new_centrality[node] = sum(centrality[neigh] for neigh in graph[node])
        # L2范数归一化
        norm = math.sqrt(sum(v**2 for v in new_centrality.values()))
        if norm == 0:
            break
        for node in nodes:
            new_centrality[node] /= norm
            max_diff = max(max_diff, abs(new_centrality[node] - centrality[node]))
        centrality = new_centrality
        if max_diff < tol:
            break
    return centrality

5. Katz中心性（Katz Centrality） #

考虑所有路径并引入衰减因子，平衡短路径和长路径的影响：

def katz_centrality(graph, alpha=0.1, beta=1.0, max_iter=100, tol=1e-6):
    nodes = list(graph.keys())
    n = len(nodes)
    if n == 0:
        return {}
    # 初始化中心性为基础值beta
    centrality = {node: beta for node in nodes}
    
    for _ in range(max_iter):
        new_centrality = {}
        max_diff = 0.0
        for node in nodes:
            # 累加邻居的中心性（带衰减因子alpha）
            neighbor_sum = sum(alpha * centrality[neigh] for neigh in graph[node])
            new_centrality[node] = beta + neighbor_sum
        # 检查收敛
        for node in nodes:
            max_diff = max(max_diff, abs(new_centrality[node] - centrality[node]))
        centrality = new_centrality
        if max_diff < tol:
            break
    return centrality

6. PageRank中心性 #

模拟网页链接权重，引入阻尼因子，优先考虑被高权重节点指向的节点：

def pagerank_centrality(graph, d=0.85, max_iter=100, tol=1e-6):
    nodes = list(graph.keys())
    n = len(nodes)
    if n == 0:
        return {}
    # 初始化每个节点的初始Rank值
    centrality = {node: 1.0 / n for node in nodes}
    # 计算每个节点的出度
    out_degree = {node: len(graph[node]) for node in nodes}
    
    for _ in range(max_iter):
        new_centrality = {}
        max_diff = 0.0
        for node in nodes:
            rank_sum = 0.0
            # 累加所有指向当前节点的邻居的Rank贡献
            for neigh in graph:
                if node in graph[neigh] and out_degree[neigh] > 0:
                    rank_sum += centrality[neigh] / out_degree[neigh]
            # 应用阻尼因子公式
            new_centrality[node] = (1 - d) / n + d * rank_sum
        # 检查收敛
        for node in nodes:
            max_diff = max(max_diff, abs(new_centrality[node] - centrality[node]))
        centrality = new_centrality
        if max_diff < tol:
            break
    return centrality

内容的提问来源于stack exchange，提问作者luhy