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. 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.
    2. 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.
    3. 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.
    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. 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.
    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. MIZUNO Takayuki & SOUMA Wataru & WATANABE Tsutomu, 2015. "Buyer-Supplier Networks and Aggregate Volatility," Discussion papers 15056, Research Institute of Economy, Trade and Industry (RIETI).
    4. Gautier M Krings & Jean-François Carpantier & Jean-Charles Delvenne, 2014. "Trade Integration and Trade Imbalances in the European Union: A Network Perspective," PLOS ONE, Public Library of Science, vol. 9(1), pages 1-14, January.
    5. 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.
    6. 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.
    7. Campi, Mercedes & Dueñas, Marco, 2019. "Intellectual property rights, trade agreements, and international trade," Research Policy, Elsevier, vol. 48(3), pages 531-545.
    8. 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.
    9. Massimo Riccaboni & Alessandro Rossi & Stefano Schiavo, 2013. "Global networks of trade and bits," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 8(1), pages 33-56, April.
    10. Yue Pu & Yunting Li & Jinjin Zhang, 2023. "Features and evolution of the ‘Belt and Road’ regional value chain: Complex network analysis," The World Economy, Wiley Blackwell, vol. 46(7), pages 2134-2156, July.
    11. 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.
    12. Massimo Riccaboni & Stefano Schiavo, 2009. "The Structure and Growth of International Trade," Documents de Travail de l'OFCE 2009-24, Observatoire Francais des Conjonctures Economiques (OFCE).
    13. 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.
    14. João Amador & Sónia Cabral, 2017. "Networks of Value-added Trade," The World Economy, Wiley Blackwell, vol. 40(7), pages 1291-1313, July.
    15. 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.
    16. 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.
    17. 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.
    18. Massimo Riccaboni & Stefano Schiavo, 2009. "The Structure and Growth of Weighted Networks," Papers 0908.0348, arXiv.org, revised Dec 2009.
    19. Aller, Carlos & Ductor, Lorenzo & Herrerias, M.J., 2015. "The world trade network and the environment," Energy Economics, Elsevier, vol. 52(PA), pages 55-68.
    20. Rosanna Grassi & Paolo Bartesaghi & Stefano Benati & Gian Paolo Clemente, 2021. "Multi-Attribute Community Detection in International Trade Network," Networks and Spatial Economics, Springer, vol. 21(3), pages 707-733, 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: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.