IDEAS home Printed from
   My bibliography  Save this paper

Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques


  • Timo Gschwind

    () (Johannes Gutenberg University Mainz)

  • Stefan Irnich

    () (Johannes Gutenberg University Mainz)

  • Fabio Furini

    () (Université Paris Dauphine)

  • Roberto Wol?er Calvo

    () (Universit´e de Paris Nord)


In social network analysis (SNA), relationships between members of a network are encoded in an undirected graph where vertices represent the members of the network and edges indicate the existence of a relationship. One important task in SNA is community detection, that is, clustering the members into communities such that relatively few edges are in the cutsets but relatively many are internal edges. The clustering is intended to reveal hidden or reproduce known features of the network, while the structure of communities is arbitrary. We propose decomposing a graph into the minimum number of relaxed cliques as a new method for community detection especially conceived for cases in which the internal structure of the community is important. Cliques, that is, subgraphs with pairwise connected vertices, can model perfectly cohesive communities, but often they are overly restrictive because many real communities form dense but not complete subgraphs. Therefore, different variants of relaxed cliques have been de?ned in terms of vertex degree and distance, edge density, and connectivity. They allow to impose application-speci?c constraints a community has to ful?ll such as familiarity and reachability among members and robustness of the communities. Standard compact formulations fail in ?nding optimal solutions even for small instances of such decomposition problems. Hence, we develop exact algorithms based on Dantzig-Wolfe reformulation and branch-and-price techniques. Extensive computational results demonstrate the e?ectiveness of all components of the algorithms and the validity of our approach when applied to social network instances from the literature.

Suggested Citation

  • Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wol?er Calvo, 2015. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1520, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
  • Handle: RePEc:jgu:wpaper:1520

    Download full text from publisher

    File URL:
    File Function: First version, 2015
    Download Restriction: no

    References listed on IDEAS

    1. Bourjolly, Jean-Marie & Laporte, Gilbert & Pesant, Gilles, 2002. "An exact algorithm for the maximum k-club problem in an undirected graph," European Journal of Operational Research, Elsevier, vol. 138(1), pages 21-28, April.
    2. Svyatoslav Trukhanov & Chitra Balasubramaniam & Balabhaskar Balasundaram & Sergiy Butenko, 2013. "Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations," Computational Optimization and Applications, Springer, vol. 56(1), pages 113-130, September.
    3. Veremyev, Alexander & Boginski, Vladimir, 2012. "Identifying large robust network clusters via new compact formulations of maximum k-club problems," European Journal of Operational Research, Elsevier, vol. 218(2), pages 316-326.
    4. Timo Gschwind & Stefan Irnich & Isabel Podlinski, 2015. "Maximum Weight Relaxed Cliques and Russian Doll Search Revisited," Working Papers 1504, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 19 May 2015.
    5. Pattillo, Jeffrey & Youssef, Nataly & Butenko, Sergiy, 2013. "On clique relaxation models in network analysis," European Journal of Operational Research, Elsevier, vol. 226(1), pages 9-18.
    Full references (including those not matched with items on IDEAS)

    More about this item


    Graph decomposition; community detection; clique relaxations; social network analysis; branch-and-price;

    NEP fields

    This paper has been announced in the following NEP Reports:


    Access and download statistics


    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:jgu:wpaper:1520. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Research Unit IPP). General contact details of provider: .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.