Partitioning and modularity of graphs with arbitrary degree distribution
| dc.creator | Reichardt, Joerg | |
| dc.creator | Bornholdt, Stefan | |
| dc.date | 2006-06-12 | |
| dc.date | 2007-04-06 | |
| dc.date.accessioned | 2026-07-07T12:11:45Z | |
| dc.date.available | 2026-07-07T12:11:45Z | |
| dc.description | We solve the graph bi-partitioning problem in dense graphs with arbitrary degree distribution using the replica method. We find the cut-size to scale universally with <k^1/2>. In contrast, earlier results studying the problem in graphs with a Poissonian degree distribution had found a scaling with <k>^1/2 [Fu and Anderson, J. Phys. A: Math. Gen. 19, 1986]. The new results also generalize to the problem of q-partitioning. They can be used to find the expected modularity Q [Newman and Grivan, Phys. Rev. E, 69, 2004] of random graphs and allow for the assessment of statistical significance of the output of community detection algorithms. | |
| dc.description | Revised version including new plots and improved discussion of some mathematical details | |
| dc.identifier | https://arxiv.org/abs/cond-mat/0606295 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/0606295 | |
| dc.identifier | Phys. Rev. E 76, 015102(R) (2007) | |
| dc.identifier | doi:10.1103/PhysRevE.76.015102 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/210323 | |
| dc.subject | Disordered Systems and Neural Networks | |
| dc.subject | Statistical Mechanics | |
| dc.title | Partitioning and modularity of graphs with arbitrary degree distribution | |
| dc.type | text |