### 复杂代码实例：基于Louvain算法的社区发现 为了展示一个多模块化的复杂系统应用，下面提供了一个Python实现的Louvain算法用于社交网络中的社区发现。此示例不仅展示了如何构建和优化大型图结构的数据集上的社区检测方法，还体现了良好的软件工程实践。 #### 导入必要的库 ```python import networkx as nx from collections import defaultdict, Counter import matplotlib.pyplot as plt ``` #### 定义辅助函数 定义一些帮助函数来初始化图形、绘制结果以及计算模块度： ```python def init_graph(edges): G = nx.Graph() G.add_edges_from(edges) return G def draw_communities(G, partition): pos = nx.spring_layout(G) colors = list(dict(Counter(partition.values())).keys()) for community in set(partition.values()): nodes_in_community = [ node for node in partition.keys() if partition[node] == community] color = colors.pop() nx.draw_networkx_nodes( G, pos, nodelist=nodes_in_community, node_color=color, alpha=0.8) nx.draw_networkx_labels(G, pos) nx.draw_networkx_edges(G, pos, alpha=0.5) def modularity(partition, A): m = sum(A.values()) / 2. Q = 0. for i in range(len(A)): ki = sum([A[i][j] for j in A]) kj = sum([A[j][i] for j in A]) ci = partition.get(i, -1) cj = partition.get(j, -1) if ci == cj and ci != -1: Q += A[i][j] - ((ki * kj) / (2 * m)) return Q / (2 * m) ``` #### 实现Louvain算法的核心逻辑 以下是Louvain算法的主要部分，它负责执行两阶段的过程——局部最优解寻找与凝聚层次聚类： ```python class LouvainAlgorithm: def __init__(self, graph): self.graph = graph self.A = {node: dict(graph[node]) for node in graph} self.partition = {} def phase_one(self): improvement = True while improvement: improvement = False for v in self.graph.nodes(): best_mod_gain = None original_community = self.partition[v] neighbors = list(self.graph.neighbors(v)) gains = [] communities_of_neighbors = set([ self.partition[w] for w in neighbors]) for c in communities_of_neighbors.union({-1}): gain = self._modularity_gain(v, c) if not best_mod_gain or gain > best_mod_gain[0]: best_mod_gain = (gain, c) new_community = best_mod_gain[-1] if new_community != original_community: self.partition[v] = new_community improvement = True return self.partition def _modularity_gain(self, vertex, target_community): """Calculate the change of modularities.""" pass # Implementation omitted for brevity def run(self): current_partition = self.phase_one() mapping = { old_node_id: idx for idx, old_node_id in enumerate(set(current_partition.values())) } contracted_graph = nx.contracted_nodes( self.graph.copy(), u=mapping[current_partition[u]], v=u, self_loops=False ) next_level = LouvainAlgorithm(contracted_graph) next_partition = next_level.run() final_mapping = {} for k, v in mapping.items(): final_mapping[k] = next_partition[v] return final_mapping ``` 请注意，在上述`_modularity_gain()`方法中省略了一些具体细节以保持简洁；实际应用时应补充完整的模体增益计算公式[^1]。