python networkx 中的图模块化

Question

我在 python lib NetorwkX 中创建了一个图，我想实现一个模块化算法以便对我的图的节点进行聚类。我遇到了以下代码：

import community
import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()

G = nx.read_weighted_edgelist('graphs/fashionGraph_1.edgelist')
nx.transitivity(G)

# Find modularity
part = community.best_partition(G)
mod = community.modularity(part,G)

# Plot, color nodes using community structure
values = [part.get(node) for node in G.nodes()]
nx.draw_spring(G, cmap=plt.get_cmap('jet'), node_color = values, node_size=30, with_labels=False)
plt.show()

我的图有 4267 条和 3692 条边。结果图是这样的：

我对图的节点如何聚类有点困惑。颜色的逻辑到底是什么？

Answer 1

来自documentation：

Node color. Can be a single color format string, or a sequence of colors with the same length as nodelist. If numeric values are specified they will be mapped to colors using the cmap and vmin,vmax parameters. See matplotlib.scatter for more details.

part = community.best_partition(G) 为每个节点分配一个社区 - part 是一个字典，part[node] 是该节点所属的社区（每个分配一个整数）。稍后 values = [part.get(node) for node in G.nodes()] 按照节点在 G.nodes() 中出现的顺序为每个节点创建一个包含社区编号的列表。

然后在绘图命令中，它将使用这些社区编号来确定节点的颜色。所有被分配到同一个社区的节点将被赋予相同的颜色。

节点的物理位置由spring布局分配。您可以看到 spring 布局似乎将节点置于暗示某些社区与 community.best_partition 发现的社区不同的位置。这也许有点令人惊讶，但肯定没有什么能阻止它。它确实让我觉得你使用的算法没有适当地解释网络中的所有结构。 best_partition 的 documentation 给出了一些底层算法的解释。

Answer 2

粗略地说，节点被分组到社区中，这样社区内连接与社区间连接的比率（模块化度量）得到优化。

来自wikipedia的模块化的精确定义：

Modularity is the fraction of the edges that fall within the given groups minus the expected such fraction if edges were distributed at random. The value of the modularity lies in the range [−1/2,1). It is positive if the number of edges within groups exceeds the number expected on the basis of chance. For a given division of the network's vertices into some modules, modularity reflects the concentration of edges within modules compared with random distribution of links between all nodes regardless of modules.

社区包实现的算法使用迭代过程找到近似解（社区分离），该过程在开始时将每个节点定义为一个社区并不断合并它们直到模块化被优化。

更准确的信息可以在描述算法的论文中找到：

大型网络中社区的快速展开。 VD Blondel、JL Guillaume、R Lambiotte、E Lefebvre 统计力学学报：理论与实验2008（10），P10008

（我能够从 https://pypi.python.org/pypi/python-louvain 检索并安装它到 windows）

python networkx 中的图模块化

Graph modularity in python networkx

python

graph

networkx

modularity