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

Timo Gschwind (), Stefan Irnich (), Fabio Furini () and Roberto Wolfler Calvo ()
Additional contact information
Timo Gschwind: Johannes Gutenberg University Mainz
Stefan Irnich: Johannes Gutenberg University Mainz
Fabio Furini: Université Paris Dauphine
Roberto Wolfler Calvo: Universit´e de Paris Nord

No 1520, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

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

Keywords: Graph decomposition; community detection; clique relaxations; social network analysis; branch-and-price (search for similar items in EconPapers)
Pages: 34 pages
Date: 2015-12-11
New Economics Papers: this item is included in nep-cdm, nep-cmp and nep-net
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1520.pdf First version, 2015 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1520

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().