IDEAS home Printed from https://ideas.repec.org/a/spr/eurjco/v5y2017i4d10.1007_s13675-017-0082-6.html
   My bibliography  Save this article

Evaluating balancing on social networks through the efficient solution of correlation clustering problems

Author

Listed:
  • Mario Levorato

    (Fluminense Federal University)

  • Rosa Figueiredo

    (University of Avignon)

  • Yuri Frota

    (Fluminense Federal University)

  • Lúcia Drummond

    (Fluminense Federal University)

Abstract

One challenge for social network researchers is to evaluate balance in a social network. The degree of balance in a social group can be used as a tool to study whether and how this group evolves to a possible balanced state. The solution of clustering problems defined on signed graphs can be used as a criterion to measure the degree of balance in social networks and this measure can be obtained with the optimal solution of the correlation clustering problem, as well as a variation of it, the relaxed correlation clustering problem. However, solving these problems is no easy task, especially when large network instances need to be analyzed. In this work, we contribute to the efficient solution of both problems by developing sequential and parallel ILS metaheuristics. Then, by using our algorithms, we solve the problem of measuring the structural balance on large real-world social networks.

Suggested Citation

  • Mario Levorato & Rosa Figueiredo & Yuri Frota & Lúcia Drummond, 2017. "Evaluating balancing on social networks through the efficient solution of correlation clustering problems," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(4), pages 467-498, December.
    • Handle: RePEc:spr:eurjco:v:5:y:2017:i:4:d:10.1007_s13675-017-0082-6
    DOI: 10.1007/s13675-017-0082-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13675-017-0082-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13675-017-0082-6?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. Allison, Graham T., 1969. "Conceptual Models and the Cuban Missile Crisis," American Political Science Review, Cambridge University Press, vol. 63(3), pages 689-718, November.
    2. Mearsheimer, John J. & Walt, Stephen, 2006. "The Israel Lobby and U.S. Foreign Policy," Working Paper Series rwp06-011, Harvard University, John F. Kennedy School of Government.
    3. Douglas M. Stinnett & Jaroslav Tir & Paul F. Diehl & Philip Schafer & Charles Gochman, 2002. "The Correlates of War (Cow) Project Direct Contiguity Data, Version 3.0," Conflict Management and Peace Science, Peace Science Society (International), vol. 19(2), pages 59-67, September.
    4. Allison, Graham T., 1969. "Conceptual Models and the Cuban Missile Crisis," American Political Science Review, Cambridge University Press, vol. 63(3), pages 689-718, November.
    5. Falk Hüffner & Nadja Betzler & Rolf Niedermeier, 2010. "Separator-based data reduction for signed graph balancing," Journal of Combinatorial Optimization, Springer, vol. 20(4), pages 335-360, November.
    6. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    7. Figueiredo, Rosa & Frota, Yuri, 2014. "The maximum balanced subgraph of a signed graph: Applications and solution approaches," European Journal of Operational Research, Elsevier, vol. 236(2), pages 473-487.
    8. Macon, Kevin T. & Mucha, Peter J. & Porter, Mason A., 2012. "Community structure in the United Nations General Assembly," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(1), pages 343-361.
    9. 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.
    10. Michael Brusco & Hans-Friedrich Köhn, 2009. "Clustering Qualitative Data Based on Binary Equivalence Relations: Neighborhood Search Heuristics for the Clique Partitioning Problem," Psychometrika, Springer;The Psychometric Society, vol. 74(4), pages 685-703, December.
    11. Michael Brusco & Patrick Doreian & Andrej Mrvar & Douglas Steinley, 2011. "Two Algorithms for Relaxed Structural Balance Partitioning: Linking Theory, Models, and Data to Understand Social Network Phenomena," Sociological Methods & Research, , vol. 40(1), pages 57-87, February.
    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. Dewan F. Wahid & Elkafi Hassini, 2022. "A Literature Review on Correlation Clustering: Cross-disciplinary Taxonomy with Bibliometric Analysis," SN Operations Research Forum, Springer, vol. 3(3), pages 1-42, September.
    2. Eduardo Queiroga & Anand Subramanian & Rosa Figueiredo & Yuri Frota, 2021. "Integer programming formulations and efficient local search for relaxed correlation clustering," Journal of Global Optimization, Springer, vol. 81(4), pages 919-966, December.
    3. Zacharie Ales & Céline Engelbeen & Rosa Figueiredo, 2024. "Correlation Clustering Problem Under Mediation," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 672-689, March.

    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. Miriam Hartlapp & Julia Metz & Christian Rauh, 2010. "The agenda set by the EU Commission: the result of balanced or biased aggregation of positions?," LEQS – LSE 'Europe in Question' Discussion Paper Series 21, European Institute, LSE.
    2. Gaurav Sinha, 2015. "Responding to Complexity: Microfinance MIS Service Providers as Complex Adaptive Systems," Journal of Entrepreneurship and Innovation in Emerging Economies, Entrepreneurship Development Institute of India, vol. 1(2), pages 163-180, July.
    3. Edward H. Kaplan, 2012. "OR Forum---Intelligence Operations Research: The 2010 Philip McCord Morse Lecture," Operations Research, INFORMS, vol. 60(6), pages 1297-1309, December.
    4. Paul Cairney & Federico Toth, 2023. "The politics of COVID-19 experts: comparing winners and losers in Italy and the UK," Policy and Society, Darryl S. Jarvis and M. Ramesh, vol. 42(3), pages 392-405.
    5. Ade Muhammad & Utomo S. Putro & Manahan Siallagan & Kyoichi Kijima & Meditya Wasesa, 2021. "System of Diagnostic Systems framework and its application to the disharmony in Indonesian national security," Systems Research and Behavioral Science, Wiley Blackwell, vol. 38(1), pages 31-49, January.
    6. Nutt, Paul C, 1998. "Evaluating Alternatives to Make Strategic Choices," Omega, Elsevier, vol. 26(3), pages 333-354, June.
    7. Eben J. Christensen & Steven B. Redd, 2004. "Bureaucrats Versus the Ballot Box in Foreign Policy Decision Making," Journal of Conflict Resolution, Peace Science Society (International), vol. 48(1), pages 69-90, February.
    8. Michael Brecher & Patrick James, 1988. "Patterns of Crisis Management," Journal of Conflict Resolution, Peace Science Society (International), vol. 32(3), pages 426-456, September.
    9. Paul A. Raschky & Liang Choon Wang, 2017. "Reproductive behaviour at the end of the world: the effect of the Cuban Missile Crisis on U.S. fertility," Applied Economics, Taylor & Francis Journals, vol. 49(56), pages 5722-5727, December.
    10. Gunton, Cameron & Markey, Sean, 2021. "The role of community benefit agreements in natural resource governance and community development: Issues and prospects," Resources Policy, Elsevier, vol. 73(C).
    11. Michal Parízek, 2017. "Control, soft information, and the politics of international organizations staffing," The Review of International Organizations, Springer, vol. 12(4), pages 559-583, December.
    12. Paul DiMaggio, 2017. "Layers of endogeneity—How porous boundaries between state and society complicate institutional change," Rationality and Society, , vol. 29(1), pages 80-90, February.
    13. Arkadiy V. Sakhartov & Timothy B. Folta, 2013. "Rationalizing Organizational Change: A Need for Comparative Testing," Organization Science, INFORMS, vol. 24(4), pages 1140-1156, August.
    14. Heugens, P.P.M.A.R. & Zyglidopoulos, S.C., 2007. "Unfit to Learn? How Long View Organizations Adapt to Environmental Jolts," ERIM Report Series Research in Management ERS-2007-014-ORG, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    15. Kendall Moll, 1974. "International Conflict as a Decision System," Journal of Conflict Resolution, Peace Science Society (International), vol. 18(4), pages 555-577, December.
    16. Thomas J. Volgy & Jon E. Quistgaard, 1975. "Learning About the Value of Global Cooperation," Journal of Conflict Resolution, Peace Science Society (International), vol. 19(2), pages 349-376, June.
    17. Niittymies, Aleksi & Pajunen, Kalle & Lamberg, Juha-Antti, 2022. "Temporality and firm de-internationalization: Three historical approaches," Journal of World Business, Elsevier, vol. 57(6).
    18. Nutt, Paul C., 2000. "Context, tactics, and the examination of alternatives during strategic decision making," European Journal of Operational Research, Elsevier, vol. 124(1), pages 159-186, July.
    19. David Davis, 1972. "Consensus or conflict: Alternative strategies for the bureaucratic bargainer," Public Choice, Springer, vol. 13(1), pages 21-29, September.
    20. Davis B. Bobrow & Robert T. Kudrle, 1976. "Theory, Policy, and Resource Cartels," Journal of Conflict Resolution, Peace Science Society (International), vol. 20(1), pages 3-56, March.

    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:spr:eurjco:v:5:y:2017:i:4:d:10.1007_s13675-017-0082-6. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.