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-Universität Mainz, Germany
Stefan Irnich: Johannes Gutenberg-University Mainz, Germany
Fabio Furini: LAMSADE Université Paris Dauphine, France
Roberto Wolfler Calvo: LIPN Université Paris, France

No 1722, 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, subsets of vertices inducing complete subgraphs, can model perfectly cohesive communities, but often they are overly restrictive because many real communities form dense, but not complete subgraphs. Therefore, di erent variants of relaxed cliques have been defined in terms of vertex degree and distance, edge density, and connectivity. They allow to impose application-specific constraints a community has to fulfill such as familiarity and reachability among members and robustness of the communities. By discussing the results obtained for some very prominent social networks widely studied in the SNA literature we demonstrate the applicability of our approach.

Keywords: Community detection; graph decomposition; clique relaxations; social network analysis (search for similar items in EconPapers)
Pages: 27 pages
Date: 2017-12-20
New Economics Papers: this item is included in nep-cdm, nep-net and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1722.pdf First version, 2017 (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:1722

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