Modularity functions maximization with nonnegative relaxation facilitates community detection in networks

Details Modularity functions maximization with nonnegative relaxation facilitates community detection in networks Modularity functions maximization with nonnegative relaxation facilitates community detection in networks

2011-03-21

arxiv.org/abs/1103.4072v2

Physics

Physics and Society

Scientific paper

We show here that the problem of maximizing a family of quantitative functions, encompassing both the modularity (Q-measure) and modularity density (D-measure), for community detection can be uniformly understood as a combinatoric optimization involving the trace of a matrix called modularity Laplacian. Instead of using traditional spectral relaxation, we apply additional nonnegative constraint into this graph clustering problem and design efficient algorithms to optimize the new objective. With the explicit nonnegative constraint, our solutions are very close to the ideal community indicator matrix and can directly assign nodes into communities. The near-orthogonal columns of the solution can be reformulated as the posterior probability of corresponding node belonging to each community. Therefore, the proposed method can be exploited to identify the fuzzy or overlapping communities and thus facilitates the understanding of the intrinsic structure of networks. Experimental results show that our new algorithm consistently, sometimes significantly, outperforms the traditional spectral relaxation approaches.

Affiliated with

Also associated with

No associations

Rating

Modularity functions maximization with nonnegative relaxation facilitates community detection in networks 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 Modularity functions maximization with nonnegative relaxation facilitates community detection in networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modularity functions maximization with nonnegative relaxation facilitates community detection in networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-323716