Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Finding cohesive communities with C³

Adrien Friggeri 1, 2 Eric Fleury 1, 2, 3 
Abstract : Social communities have drawn a lot of attention in the past decades. We have previously introduced and validated the use of the cohesion, a graph metric which quantitatively captures the community-ness in a social sense of a set of nodes in a graph. Here we show that the problem of maximizing this quantity is NP-Hard. Furthermore, we show that the dual problem of minimizing this quantity, for a fixed set size is also NP-Hard. We then propose a heuristic to optimize the cohesion which we apply to the graph of voting agreement between U.S Senators. Finally we conclude on the validity of the approach by analyzing the resulting agreement communities.
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download
Contributor : Adrien Friggeri Connect in order to contact the contributor
Submitted on : Monday, April 30, 2012 - 7:04:46 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:40 AM
Long-term archiving on: : Thursday, December 15, 2016 - 3:48:02 AM


Files produced by the author(s)


  • HAL Id : hal-00692548, version 1


Adrien Friggeri, Eric Fleury. Finding cohesive communities with C³. [Research Report] RR-7947, INRIA. 2012. ⟨hal-00692548⟩



Record views


Files downloads