IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v602y2022ics0378437122004253.html
   My bibliography  Save this article

A mathematical programming approach to overlapping community detection

Author

Listed:
  • Benati, Stefano
  • Puerto, Justo
  • Rodríguez-Chía, Antonio M.
  • Temprano, Francisco

Abstract

We propose a new optimization model to detect overlapping communities in networks. The model elaborates suggestions contained in Zhang et al. (2007), in which overlapping communities were identified through the use of a fuzzy membership function, calculated as the outcome of a mathematical programming problem. In our approach, we retain the idea of using both mathematical programming and fuzzy membership to detect overlapping communities, but we replace the fuzzy objective function proposed there with another one, based on the Newman and Girvan’s definition of modularity. Next, we formulate a new mixed-integer linear programming model to calculate optimal overlapping communities. After some computational tests, we provide some evidence that our new proposal can fix some biases of the previous model, that is, its tendency of calculating communities composed of almost all nodes. Conversely, our new model can reveal other structural properties, such as nodes or communities acting as bridges between communities. Finally, as mathematical programming can be used only for moderate size networks due to its computation time, we proposed two heuristic algorithms to solve the largest instances, that compare favourably to other methodologies.

Suggested Citation

  • Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M. & Temprano, Francisco, 2022. "A mathematical programming approach to overlapping community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 602(C).
    • Handle: RePEc:eee:phsmap:v:602:y:2022:i:c:s0378437122004253
    DOI: 10.1016/j.physa.2022.127628
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437122004253
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2022.127628?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. Laura Bennett & Aristotelis Kittas & Songsong Liu & Lazaros G Papageorgiou & Sophia Tsoka, 2014. "Community Structure Detection for Overlapping Modules through Mathematical Programming in Protein Interaction Networks," PLOS ONE, Public Library of Science, vol. 9(11), pages 1-15, November.
    2. Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M., 2017. "Clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 261(1), pages 43-53.
    3. Gergely Palla & Imre Derényi & Illés Farkas & Tamás Vicsek, 2005. "Uncovering the overlapping community structure of complex networks in nature and society," Nature, Nature, vol. 435(7043), pages 814-818, June.
    4. Li, Hui-Jia & Xu, Wenzhe & Song, Shenpeng & Wang, Wen-Xuan & Perc, Matjaž, 2021. "The dynamics of epidemic spreading on signed networks," Chaos, Solitons & Fractals, Elsevier, vol. 151(C).
    5. Chen, Duanbing & Shang, Mingsheng & Lv, Zehua & Fu, Yan, 2010. "Detecting overlapping communities of weighted networks via a local algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(19), pages 4177-4187.
    6. Enrico Angelelli & Renata Mansini & M. Speranza, 2012. "Kernel Search: a new heuristic framework for portfolio selection," Computational Optimization and Applications, Springer, vol. 51(1), pages 345-361, January.
    7. Zhang, Shihua & Wang, Rui-Sheng & Zhang, Xiang-Sun, 2007. "Identification of overlapping community structure in complex networks using fuzzy c-means clustering," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 374(1), pages 483-490.
    8. Garlaschelli, Diego & Loffredo, Maria I., 2005. "Structure and evolution of the world trade network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 355(1), pages 138-144.
    9. Zhenping Li & Xiang-Sun Zhang & Rui-Sheng Wang & Hongwei Liu & Shihua Zhang, 2013. "Discovering Link Communities in Complex Networks by an Integer Programming Model and a Genetic Algorithm," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-10, December.
    10. D. Garlaschelli & M. I. Loffredo, 2005. "Structure and Evolution of the World Trade Network," Papers physics/0502066, arXiv.org, revised May 2005.
    Full references (including those not matched with items on IDEAS)

    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. Barigozzi, Matteo & Fagiolo, Giorgio & Mangioni, Giuseppe, 2011. "Identifying the community structure of the international-trade multi-network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(11), pages 2051-2066.
    2. Carlo Piccardi, 2011. "Finding and Testing Network Communities by Lumped Markov Chains," PLOS ONE, Public Library of Science, vol. 6(11), pages 1-13, November.
    3. Marco Dueñas & Giorgio Fagiolo, 2013. "Modeling the International-Trade Network: a gravity approach," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 8(1), pages 155-178, April.
    4. Hao, Xiaoqing & An, Haizhong & Qi, Hai & Gao, Xiangyun, 2016. "Evolution of the exergy flow network embodied in the global fossil energy trade: Based on complex network," Applied Energy, Elsevier, vol. 162(C), pages 1515-1522.
    5. Florian Blöchl & Fabian J. Theis & Fernando Vega-Redondo & Eric O'N. Fisher, 2010. "Which Sectors of a Modern Economy are most Central?," CESifo Working Paper Series 3175, CESifo.
    6. Zhang, Zhiwei & Wang, Zhenyu, 2015. "Mining overlapping and hierarchical communities in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 421(C), pages 25-33.
    7. Bartesaghi, Paolo & Clemente, Gian Paolo & Grassi, Rosanna & Luu, Duc Thi, 2022. "The multilayer architecture of the global input-output network and its properties," Journal of Economic Behavior & Organization, Elsevier, vol. 204(C), pages 304-341.
    8. Stefano Schiavo & Javier Reyes & Giorgio Fagiolo, 2010. "International trade and financial integration: a weighted network analysis," Quantitative Finance, Taylor & Francis Journals, vol. 10(4), pages 389-399.
    9. Arribas Ivan & Perez Francisco & Tortosa-Ausina Emili, 2010. "The Determinants of International Financial Integration Revisited: The Role of Networks and Geographic Neutrality," Studies in Nonlinear Dynamics & Econometrics, De Gruyter, vol. 15(1), pages 1-55, December.
    10. Wu, Zhihao & Lin, Youfang & Wan, Huaiyu & Tian, Shengfeng & Hu, Keyun, 2012. "Efficient overlapping community detection in huge real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(7), pages 2475-2490.
    11. Zaclicever, Dayna, 2020. "A network analysis approach to vertical trade linkages: the case of Latin America and Asia," Comercio Internacional 45060, Naciones Unidas Comisión Económica para América Latina y el Caribe (CEPAL).
    12. Daniel Nepelski & Giuditta De Prato, 2020. "Technological complexity and economic development," Review of Development Economics, Wiley Blackwell, vol. 24(2), pages 448-470, May.
    13. Chiarucci, Riccardo & Ruzzenenti, Franco & Loffredo, Maria I., 2014. "Detecting spatial homogeneity in the World Trade Web with Detrended Fluctuation Analysis," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 401(C), pages 1-7.
    14. Wu, Jianshe & Wang, Xiaohua & Jiao, Licheng, 2012. "Synchronization on overlapping community network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(3), pages 508-514.
    15. Elisa Letizia & Fabrizio Lillo, 2017. "Corporate payments networks and credit risk rating," Papers 1711.07677, arXiv.org, revised Sep 2018.
    16. Badie, Reza & Aleahmad, Abolfazl & Asadpour, Masoud & Rahgozar, Maseud, 2013. "An efficient agent-based algorithm for overlapping community detection using nodes’ closeness," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(20), pages 5231-5247.
    17. Giorgio Fagiolo & Javier Reyes & Stefano Schiavo, 2010. "The evolution of the world trade web: a weighted-network analysis," Journal of Evolutionary Economics, Springer, vol. 20(4), pages 479-514, August.
    18. Marcos Duenas & Rossana Mastrandrea & Matteo Barigozzi & Giorgio Fagiolo, 2017. "Spatio-Temporal Patterns of the International Merger and Acquisition Network," LEM Papers Series 2017/13, Laboratory of Economics and Management (LEM), Sant'Anna School of Advanced Studies, Pisa, Italy.
    19. Silvia Sopranzetti, 2018. "The Italian Districts in the Global Value Chains," Italian Economic Journal: A Continuation of Rivista Italiana degli Economisti and Giornale degli Economisti, Springer;Società Italiana degli Economisti (Italian Economic Association), vol. 4(3), pages 497-522, November.
    20. Rita María del Río-Chanona & Jelena Grujić & Henrik Jeldtoft Jensen, 2017. "Trends of the World Input and Output Network of Global Trade," PLOS ONE, Public Library of Science, vol. 12(1), pages 1-14, January.

    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:phsmap:v:602:y:2022:i:c:s0378437122004253. 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.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.