Abstract:It is known that complete graphs and complete multipartite graphs have modularity zero. We show that the least number of edges we may delete from the complete graph $K_n$ to obtain a graph with non-zero modularity is $\lfloor n/2\rfloor +1$. Similarly we determine the least number of edges we may delete from or add to a complete bipartite graph to reach non-zero modularity. We give some corresponding results for complete multipartite graphs, and a short proof that complete multipartite graphs have modularity zero.
We also analyse the modularity of very dense random graphs, and in particular we find that there is a transition to modularity zero when the average degree of the complementary graph drops below 1.
Finally we consider some natural variants of the definition of modularity; and investigate which graphs have corresponding modularity value 0, and the least number of edges we may delete from the complete graph $K_n$ to obtain a graph with non-zero modularity.
From: Fiona Skerman [view email]
[v1]
Sun, 12 Nov 2023 15:26:51 UTC (19 KB)
[v2]
Wed, 20 Dec 2023 17:25:39 UTC (21 KB)
[v3]
Wed, 22 Jul 2026 11:40:04 UTC (231 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。