The triangle k-club problem

Filipa D. Carvalho () and Maria Teresa Almeida ()
Additional contact information
Filipa D. Carvalho: ISEG, Universidade de Lisboa
Maria Teresa Almeida: ISEG, Universidade de Lisboa

Journal of Combinatorial Optimization, 2017, vol. 33, issue 3, No 2, 814-846

Abstract: Abstract Graph models have long been used in social network analysis and other social and natural sciences to render the analysis of complex systems easier. In applied studies, to understand the behaviour of social networks and the interactions that command that behaviour, it is often necessary to identify sets of elements which form cohesive groups, i.e., groups of actors that are strongly interrelated. The clique concept is a suitable representation for groups of actors that are all directly related pair-wise. However, many social relationships are established not only face-to-face but also through intermediaries, and the clique concept misses all the latter. To deal with these cases, it is necessary to adopt approaches that relax the clique concept. In this paper we introduce a new clique relaxation—the triangle k-club—and its associated maximization problem—the maximum triangle k-club problem. We propose integer programming formulations for the problem, stated in different variable spaces, and derive valid inequalities to strengthen their linear programming relaxations. Computational results on randomly generated and real-world graphs, with $$k=2$$ k = 2 and $$k=3$$ k = 3 , are reported.

Keywords: Clique relaxations; Integer formulations; Valid inequalities; Cliques; Social network analysis (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0009-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:33:y:2017:i:3:d:10.1007_s10878-016-0009-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0009-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().