Partitioning and modularity of graphs with arbitrary degree distribution

Details Partitioning and modularity of graphs with arbitrary degree distribution Partitioning and modularity of graphs with arbitrary degree distribution

2006-06-12

arxiv.org/abs/cond-mat/0606295v2

Phys. Rev. E 76, 015102(R) (2007)

Physics

Condensed Matter

Disordered Systems and Neural Networks

Revised version including new plots and improved discussion of some mathematical details

Scientific paper

10.1103/PhysRevE.76.015102

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 . In contrast, earlier results studying the problem in graphs with a Poissonian degree distribution had found a scaling with ^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.

Affiliated with

Also associated with

No associations

Rating

Partitioning and modularity of graphs with arbitrary degree distribution does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Partitioning and modularity of graphs with arbitrary degree distribution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioning and modularity of graphs with arbitrary degree distribution will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647729