Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

Column generation algorithms for exact modularity maximization in networks

Column generation algorithms for exact modularity maximization in networks Finding modules, or clusters, in networks currently attracts much attention in several domains. The most studied criterion for doing so, due to Newman and Girvan Phys. Rev. E 69 , 026113 ( 2004 ) 10.1103/PhysRevE.69.026113 , is modularity maximization. Many heuristics have been proposed for maximizing modularity and yield rapidly near optimal solution or sometimes optimal ones but without a guarantee of optimality. There are few exact algorithms, prominent among which is a paper by Xu Eur. Phys. J. B 60 , 231 ( 2007 ) 10.1140/epjb/e2007-00331-0 . Modularity maximization can also be expressed as a clique partitioning problem and the row generation algorithm of Grötschel and Wakabayashi Math. Program. 45 , 59 ( 1989 ) 10.1007/BF01589097 applied. We propose to extend both of these algorithms using the powerful column generation methods for linear and non linear integer programming. Performance of the four resulting algorithms is compared on problems from the literature. Instances with up to 512 entities are solved exactly. Moreover, the computing time of previously solved problems are reduced substantially. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Physical Review E American Physical Society (APS)

Column generation algorithms for exact modularity maximization in networks

Physical Review E , Volume 82 (4) – Oct 1, 2010
9 pages

Loading next page...
 
/lp/american-physical-society-aps/column-generation-algorithms-for-exact-modularity-maximization-in-bN9oUR6pTb

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
American Physical Society (APS)
Copyright
Copyright © 2010 The American Physical Society
ISSN
1550-2376
DOI
10.1103/PhysRevE.82.046112
pmid
21230350
Publisher site
See Article on Publisher Site

Abstract

Finding modules, or clusters, in networks currently attracts much attention in several domains. The most studied criterion for doing so, due to Newman and Girvan Phys. Rev. E 69 , 026113 ( 2004 ) 10.1103/PhysRevE.69.026113 , is modularity maximization. Many heuristics have been proposed for maximizing modularity and yield rapidly near optimal solution or sometimes optimal ones but without a guarantee of optimality. There are few exact algorithms, prominent among which is a paper by Xu Eur. Phys. J. B 60 , 231 ( 2007 ) 10.1140/epjb/e2007-00331-0 . Modularity maximization can also be expressed as a clique partitioning problem and the row generation algorithm of Grötschel and Wakabayashi Math. Program. 45 , 59 ( 1989 ) 10.1007/BF01589097 applied. We propose to extend both of these algorithms using the powerful column generation methods for linear and non linear integer programming. Performance of the four resulting algorithms is compared on problems from the literature. Instances with up to 512 entities are solved exactly. Moreover, the computing time of previously solved problems are reduced substantially.

Journal

Physical Review EAmerican Physical Society (APS)

Published: Oct 1, 2010

There are no references for this article.