IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v245y2015i1p14-21.html
   My bibliography  Save this article

MILP formulations for the modularity density maximization problem

Author

Listed:
  • Costa, Alberto

Abstract

Cluster analysis refers to finding subsets of vertices of a graph (called clusters) which are more likely to be joined pairwise than vertices in different clusters. In the last years this topic has been studied by many researchers, and several methods have been proposed. One of the most popular is to maximize the modularity, which represents the fraction of edges within clusters minus the expected fraction of such edges in a random graph with the same degree distribution. However, this criterion presents some issues, for example the resolution limit, i.e., the difficulty to detect clusters having small sizes. In this paper we focus on a recent measure, called modularity density, which improves the resolution limit issue of modularity. The problem of maximizing the modularity density can be described by means of a 0–1 NLP formulation. We derive some properties of the optimal solution which will be used to tighten the formulation, and we propose some MILP reformulations which yield an improvement of the resolution time.

Suggested Citation

  • Costa, Alberto, 2015. "MILP formulations for the modularity density maximization problem," European Journal of Operational Research, Elsevier, vol. 245(1), pages 14-21.
    • Handle: RePEc:eee:ejores:v:245:y:2015:i:1:p:14-21
    DOI: 10.1016/j.ejor.2015.03.012
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715002052
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.03.012?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Sonia Cafieri & Alberto Costa & Pierre Hansen, 2014. "Reformulation of a model for hierarchical divisive graph modularity maximization," Annals of Operations Research, Springer, vol. 222(1), pages 213-226, November.
    2. G. Xu & S. Tsoka & L. G. Papageorgiou, 2007. "Finding community structures in complex networks using mixed integer optimisation," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 60(2), pages 231-239, November.
    3. Plastria, Frank, 2002. "Formulating logical implications in combinatorial optimisation," European Journal of Operational Research, Elsevier, vol. 140(2), pages 338-353, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Santiago, Rafael & Lamb, Luís C., 2017. "Efficient modularity density heuristics for large graphs," European Journal of Operational Research, Elsevier, vol. 258(3), pages 844-865.
    2. Sukeda, Issey & Miyauchi, Atsushi & Takeda, Akiko, 2023. "A study on modularity density maximization: Column generation acceleration and computational complexity analysis," European Journal of Operational Research, Elsevier, vol. 309(2), pages 516-528.
    3. Baghersad, Milad & Emadikhiav, Mohsen & Huang, C. Derrick & Behara, Ravi S., 2023. "Modularity maximization to design contiguous policy zones for pandemic response," European Journal of Operational Research, Elsevier, vol. 304(1), pages 99-112.
    4. Ponce, Diego & Puerto, Justo & Temprano, Francisco, 2024. "Mixed-integer linear programming formulations and column generation algorithms for the Minimum Normalized Cuts problem on networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 519-538.
    5. Van Nguyen, Truong & Zhang, Jie & Zhou, Li & Meng, Meng & He, Yong, 2020. "A data-driven optimization of large-scale dry port location using the hybrid approach of data mining and complex network theory," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 134(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Santiago, Rafael & Lamb, Luís C., 2017. "Efficient modularity density heuristics for large graphs," European Journal of Operational Research, Elsevier, vol. 258(3), pages 844-865.
    2. Wu, Jianshe & Zhang, Long & Li, Yong & Jiao, Yang, 2016. "Partition signed social networks via clustering dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 568-582.
    3. Leo Liberti, 2020. "Distance geometry and data science," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 271-339, July.
    4. Roe, R.A. & Smeelen, M. & Hoefeld, C., 2005. "Outsourcing and organizational change : an employee perspective," Research Memorandum 045, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    5. Federico Della Croce, 2016. "MP or not MP: that is the question," Journal of Scheduling, Springer, vol. 19(1), pages 33-42, February.
    6. Liu, X. & Murata, T., 2010. "Advanced modularity-specialized label propagation algorithm for detecting communities in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(7), pages 1493-1500.
    7. Carrizosa, E. & Martin-Barragán, B. & Plastria, F. & Romero Morales, M.D., 2002. "A Dissimilarity-based approach for Classification," Research Memorandum 027, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    8. Harun Pirim & Burak Eksioglu & Fred W. Glover, 2018. "A Novel Mixed Integer Linear Programming Model for Clustering Relational Networks," Journal of Optimization Theory and Applications, Springer, vol. 176(2), pages 492-508, February.
    9. Scott P. Stevens & Susan W. Palocsay, 2017. "Teaching Use of Binary Variables in Integer Linear Programs: Formulating Logical Conditions," INFORMS Transactions on Education, INFORMS, vol. 18(1), pages 28-36, September.
    10. Rumen Andonov & Stefan Balev & Nicola Yanev, 2004. "Protein Threading: From Mathematical Models to Parallel Implementations," INFORMS Journal on Computing, INFORMS, vol. 16(4), pages 393-405, November.
    11. Dušan Džamić & Daniel Aloise & Nenad Mladenović, 2019. "Ascent–descent variable neighborhood decomposition search for community detection by modularity maximization," Annals of Operations Research, Springer, vol. 272(1), pages 273-287, January.
    12. Plastria, F., 2012. "A note towards improved homeland defense," Omega, Elsevier, vol. 40(2), pages 244-248, April.
    13. Sonia Cafieri & Alberto Costa & Pierre Hansen, 2014. "Reformulation of a model for hierarchical divisive graph modularity maximization," Annals of Operations Research, Springer, vol. 222(1), pages 213-226, November.
    14. Gambella, Claudio & Ghaddar, Bissan & Naoum-Sawaya, Joe, 2021. "Optimization problems for machine learning: A survey," European Journal of Operational Research, Elsevier, vol. 290(3), pages 807-828.
    15. Daniel Aloise & Pierre Hansen, 2011. "Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering," Journal of Global Optimization, Springer, vol. 49(3), pages 449-465, March.
    16. Sukeda, Issey & Miyauchi, Atsushi & Takeda, Akiko, 2023. "A study on modularity density maximization: Column generation acceleration and computational complexity analysis," European Journal of Operational Research, Elsevier, vol. 309(2), pages 516-528.
    17. Duchenne, Éric & Laporte, Gilbert & Semet, Frédéric, 2012. "The undirected m-Capacitated Peripatetic Salesman Problem," European Journal of Operational Research, Elsevier, vol. 223(3), pages 637-643.
    18. Li, Zhangtao & Liu, Jing, 2016. "A multi-agent genetic algorithm for community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 449(C), pages 336-347.
    19. Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
    20. Jan Pablo Burgard & Carina Moreira Costa & Christopher Hojny & Thomas Kleinert & Martin Schmidt, 2023. "Mixed-integer programming techniques for the minimum sum-of-squares clustering problem," Journal of Global Optimization, Springer, vol. 87(1), pages 133-189, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:245:y:2015:i:1:p:14-21. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.