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 metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/hal-00692548
Contributor : Adrien Friggeri <>
Submitted on : Monday, April 30, 2012 - 7:04:46 PM
Last modification on : Wednesday, November 20, 2019 - 2:38:57 AM
Long-term archiving on: Thursday, December 15, 2016 - 3:48:02 AM

File

RR-7947.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00692548, version 1

Citation

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

Share

Metrics

Record views

551

Files downloads

288