Identification of community structure in networks with convex optimization

Details Identification of community structure in networks with convex optimization Identification of community structure in networks with convex optimization

2008-06-11

arxiv.org/abs/0806.1896v2

Physics

Data Analysis, Statistics and Probability

Scientific paper

We reformulate the problem of modularity maximization over the set of partitions of a network as a conic optimization problem over the completely positive cone, converting it from a combinatorial optimization problem to a convex continuous one. A semidefinite relaxation of this conic program then allows to compute upper bounds on the maximum modularity of the network. Based on the solution of the corresponding semidefinite program, we design a randomized algorithm generating partitions of the network with suboptimal modularities. We apply this algorithm to several benchmark networks, demonstrating that it is competitive in accuracy with the best algorithms previously known. We use our method to provide the first proof of optimality of a partition for a real-world network.

Affiliated with

Also associated with

No associations

Rating

Identification of community structure in networks with convex optimization 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 Identification of community structure in networks with convex optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Identification of community structure in networks with convex optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-266021