Python中的网络图模块化

Question

我使用 Python 库 NetworkX 创建了一个图表，现在想要实现模块性算法来对我的图表中的节点进行聚类。我找到了下面这段代码：

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条边。结果图如下：

我有点困惑图形中的节点是如何聚集的。这些颜色的逻辑是什么？

- snake plissken

---

你为什么要计算“mod”？ - MERose

Answer 1

从文档中可以得知：

节点颜色。可以是单个颜色格式字符串，也可以是与nodelist长度相同的颜色序列。如果指定了数值，则将使用cmap和vmin、vmax参数将其映射到颜色上。更多详情请参见matplotlib.scatter。 part = community.best_partition(G)为每个节点分配一个社区 - part是一个字典，part[node]是节点所属的社区（每个都被分配一个整数）。然后，values = [part.get(node) for node in G.nodes()]创建了一个列表，其中按照G.nodes()中节点出现的顺序为每个节点指定了社区编号。

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

节点的物理位置由弹簧布局分配。你可以看到，弹簧布局似乎将节点放置在暗示某些不同于community.best_partition发现的社区的位置上。这或许有点令人惊讶，但肯定没有阻止它的发生。它让我想到你使用的算法没有适当地考虑网络中的所有结构。有关best_partition的文档提供了有关底层算法的一些解释。

- Joel

---

你使用的是什么版本的 community？我的 community(今天安装的)只有以下属性/方法:['__builtins__', '__doc__', '__file__', '__name__', '__package__', '__path__']。 - MERose

@MERose 我的电脑上实际上没有Community - 我自己从未使用过它。这个问题可能会有所帮助https://dev59.com/QYDba4cB1Zd3GeqPHrMB - Joel

我认为这个软件包已经损坏并且不再维护了：安装不完整，链接已过期，电子邮件帐户已失效。 - MERose

Answer 2

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

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

模块度是落在给定组内的边的分数减去如果边随机分布时预期的这种分数的分数。模块度的值在[−1/2，1)范围内。如果组内的边数超过根据机会预期的数量，则为正。对于网络顶点被划分为某些模块的给定划分，模块度反映了与所有节点之间的随机链接之间的链接相比，模块内边缘的浓度。

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

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

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

我能够从https://pypi.python.org/pypi/python-louvain上下载并在Windows上安装它。

- schiffli