Prokhorenkova et al.'s modularity conjecture for preferential attachment graphs

Less than 1 year old · traced to

Let h≥2h\geq 2 and let G∼GnhG\sim G^h_n be the preferential attachment graph with parameter hh. Write q∗(G)q^*(G) for its modularity value.

Prokhorenkova et al.'s modularity conjecture. With high probability,

q∗(G)=Θ(h−1/2).q^*(G)=\Theta(h^{-1/2}).

This conjecture predicts the asymptotic order of the modularity of GnhG^h_n as the parameter hh varies. The source attributes it to Prokhorenkova et al.; the paper establishes an upper bound bounded away from 11 for fixed h≥2h\geq2, but does not resolve the conjectured order.

References

Primary source

Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman and Małgorzata Sulkowska, “Note on edge expansion and modularity in preferential attachment graphs”, arXiv:2601.05953 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.