### Python 实现加权有向网络的 k-core 算法 对于加权有向图中的 k-core 计算，可以基于节点入度和出度以及边权重来定义核心数。下面是一个简单的 Python 实现方法： #### 定义函数 `weighted_directed_k_core` 此函数接收一个 NetworkX 图对象作为输入，并返回该图的最大 k-core 子图。 ```python import networkx as nx from collections import defaultdict def weighted_directed_k_core(G, weight='weight'): """ Compute the maximum-weighted directed k-core. Parameters: G : DiGraph or MultiDiGraph A NetworkX graph object representing a weighted directed graph. weight : string (default="weight") Edge attribute key containing the edge weights. Returns: core_number : dictionary Dictionary keyed by node to its highest core number so far. max_weighted_kcore_subgraph : Graph The subgraph induced over nodes in the largest weighted k-core. """ # Initialize dictionaries for storing current degree and final core numbers out_degrees = {n: d for n, d in G.out_degree(weight=weight)} in_degrees = {n: d for n, d in G.in_degree(weight=weight)} # Create an empty list where we will store removed edges temporarily temp_removed_edges = [] while True: changed = False # Check outgoing connections first for u in list(out_degrees.keys()): if out_degrees[u] < sum([G.edges[(u,v)][weight] for v in G.successors(u)]): successors_to_remove = set() for successor in G.successors(u): e_wt = G.edges[(u,successor)][weight] if e_wt > 0: successors_to_remove.add(successor) # Temporarily remove this edge from consideration del G.edges[(u,successor)] temp_removed_edges.append((u,successor,e_wt)) # Update degrees after removing each connection out_degrees[u] -= e_wt in_degrees[successor] -= e_wt changed = True # Remove all affected neighbors at once for neighbor in successors_to_remove: G.remove_edge(u,neighbor) # Then check incoming connections similarly... for v in list(in_degrees.keys()): if in_degrees[v] < sum([G.edges[(w,v)][weight] for w in G.predecessors(v)]): predecessors_to_remove = set() for predecessor in G.predecessors(v): e_wt = G.edges[(predecessor,v)][weight] if e_wt > 0: predecessors_to_remove.add(predecessor) # Restore any previously deleted but now valid again edges restored = [(p,q,w) for p,q,w in temp_removed_edges if q==v and p not in predecessors_to_remove] for p,q,w in restored: G.add_edge(p,q,weight=w) # Continue processing remaining deletions del G.edges[(predecessor,v)] temp_removed_edges.extend([(predecessor,v,G.edges[(predecessor,v)][weight])]) in_degrees[v] -= e_wt out_degrees[predecessor] -= e_wt changed = True # Finally delete these vertices' incident edges altogether for pred in predecessors_to_remove: G.remove_edge(pred,v) if not changed: break # After finishing iterations, compute actual core numbers based on updated degrees core_numbers_out = {} core_numbers_in = {} for n in G.nodes(): core_numbers_out[n] = min(int(sum([G.edges[e][weight] for e in G.out_edges(n)]) / len(list(G.neighbors(n)))), int(max(1,min([in_degrees[m]/len(list(G.predecessors(m))) for m in G.successors(n)])))) core_numbers_in[n] = min(int(sum([G.edges[e][weight] for e in G.in_edges(n)]) / len(list(G.predecessors(n)))), int(max(1,min([out_degrees[p]/len(list(G.successors(p))) for p in G.predecessors(n)])))) core_number = {node:max(core_numbers_out[node], core_numbers_in[node]) for node in G} return core_number, G.subgraph(node for node in core_number if core_number[node]>0) # Example usage if __name__ == "__main__": DG = nx.DiGraph() DG.add_weighted_edges_from([ ('A','B',3), ('C','D',7), ('E','F',9), ('B','C',5), ('D','E',2)]) cores, sg = weighted_directed_k_core(DG) print(f"Cores found:\n{cores}") ``` 上述代码实现了针对加权有向图的核心分解算法[^1]。通过迭代调整节点之间的连接关系直到达到稳定状态，从而找到满足条件的最大子图及其对应的核心编号。