Regensburg 2007 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe
DY: Fachverband Dynamik und Statistische Physik
DY 4: Statistical physics of complex networks I
DY 4.4: Vortrag
Montag, 26. März 2007, 12:45–13:00, H3
Graphpartitioning and modularity of graphs with arbitrary degree distribution — •Jörg Reichardt1 and Stefan Bornholdt2 — 1Universität Würzburg, Institut für Theoretische Physik III, Am Hubland, 97074 Würzburg — 2Universität Bremen, Institut für Theoretische Physik, Otto-Hahn-Allee, 28359 Bremen
We solve the graph bi-partitioning problem in dense random graphs with arbitrary degree distribution using the replica method. We find the cut-size to scale universally with ⟨ √k ⟩, regardless of the degree distribution. In contrast, earlier results studying the problem only in graphs with a Poissonian degree distribution had found a scaling with √⟨ k⟩ [Fu and Anderson, J. Phys. A: Math. Gen. 19, 1986], which, however, does not generalize to other degree distributions. The new scaling also applies to the problem of q-partitioning. Further, the result can be used to find expectation values of an important quality measure for graph clusterings, namely the modularity Q [Newman and Grivan, Phys. Rev. E, 69, 2004] , which allows for assessing the statistical significance of the output of community detection or graph clustering algorithms.