  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.
