图聚类的质量有几个指标，例如 Newman 模块化。这些使您能够比较同一图表的两个候选聚类。
有谁知道一个指标可以回答“这个图有多模块化”这个问题？例如，这两个图表中的第一个比第二个更模块化：o===o-----o====o o----o===o-----o
可以选择一个聚类算法，运行它，然后计算你喜欢的模块化度量，以获得最佳聚类。但这只是一个下限，所以看起来不是很令人满意。
这个问题很重要。例如，如果生命的分子组织是模块化的，那么生命科学家的工作会比不是模块化的更容易。有一个强大的测试会很好 - 到目前为止的一些讨论似乎涉及一厢情愿的想法。
我对此的最佳尝试是：-如果叶子附近的边权重较高，树的模块化程度更高-图的模块化是其最小切割生成树的模块化有人知道这个问题的既定答案吗？
我不确定这个问题是否有明确的答案，尤其是因为这个问题现在似乎还没有得到很好的定义——你的“数字”似乎表示边缘权重，但你随后提到了节点权重，这是明显不同的东西。
如果问题是您是否可以找到将图拆分为两个较小模块的方法，那么您可能需要考虑应用Sparsest Cut技术 - 低成本的切割意味着（？）高度模块化。我相信这些可以很容易地修改以解释未标记、边缘标记或节点标记的图。
没有单一的答案。存在不同聚类算法的部分原因是聚类有不同的标准。一个是集群中三角形的数量，与跨越边界的数量相比 - 但这在二分图中没有用。Infomap 有一个微妙的，有时会产生好的结果。一个标准将集群内的边数（除以集群的大小）与离开集群的边数（除以图的其余部分的大小）进行比较。如前一个答案所建议的，如果可以合理地将边权重视为节点之间某些东西（例如信息）流动的能力，那么切割是非常合适的。在这种情况下，最小割生成树是图的合理总结。