Loops and multiple edges in modularity maximization of networks

The modularity maximization model proposed by Newman and Girvan for the identification of communities in networks works for general graphs possibly with loops and multiple edges. However, the applications usually correspond to simple graphs. These graphs are compared to a null model where the degree distribution is maintained but edges are placed at random. Therefore, in this null model there will be loops and possibly multiple edges. Sharp bounds on the expected number of loops, and their impact on the modularity, are derived. Then, building upon the work of Massen and Doye, but using algebra rather than simulation, we propose modified null models associated with graphs without loops but with multiple edges, graphs with loops but without multiple edges and graphs without loops nor multiple edges. We validate our models by using the exact algorithm for clique partitioning of Groumltschel and Wakabayashi.

纽曼（Newman）和吉尔万（Girvan）提出的用于识别网络中社区的模块性最大化模型适用于可能带有环和多重边的一般图。然而，应用通常对应于简单图。这些图与一个零模型进行比较，在该零模型中，度分布保持不变，但边是随机放置的。因此，在这个零模型中会有环，可能还有多重边。推导了环的期望数量的精确界限及其对模块性的影响。然后，基于马森（Massen）和多伊（Doye）的工作，但使用代数而非模拟，我们提出了与无环但有多重边的图、有环但无多重边的图以及既无环也无多重边的图相关的修正零模型。我们通过使用格罗特谢尔（Groumltschel）和若林（Wakabayashi）的团划分精确算法来验证我们的模型。