python网络中的图形模块化

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是一个dict，而part[node]是该节点所属的社区（每个都分配了一个整数）。稍后values = [part.get(node) for node in G.nodes()]按照节点在G.nodes()中出现的顺序为每个节点创建一个带有社区号的列表。

然后在plotting命令中，它将使用这些社区编号来确定节点的颜色。分配给同一社区的所有节点都将具有相同的颜色。

节点的物理位置由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.

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

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

大型网络中社区的快速发展。 布朗德尔大道，纪尧姆路，兰比奥特路，勒斐伏尔路 统计力学学报：理论与实验2008（10），P10008

（我可以从https://pypi.python.org/pypi/python-louvain检索并安装到windows上）