title: Seeding for pervasively overlapping communities.
abstract: In some social and biological networks, the majority of nodes belong to multiple communities. It has recently been shown that a number of the algorithms specifically designed to detect overlapping communities do not perform well in such highly overlapping settings. Here, we consider one class of these algorithms, those which optimize a local fitness measure, typically by using a greedy heuristic to expand a seed into a community. We perform synthetic benchmarks which indicate that an appropriate seeding strategy becomes more important as the extent of community overlap increases. We find that distinct cliques provide the best seeds. We find further support for this seeding strategy with benchmarks on a Facebook network and the yeast interactome.
authors.affiliation: Clique Research Cluster, Complex and Adaptive Systems Laboratory, University College Dublin, 8 Belfield Office Park, Clonskeagh, Dublin 4, Ireland. conradlee@gmail.com
authors.forename: Conrad
authors.initials: C
authors.lastname: Lee
authors.forename: Fergal
authors.initials: F
authors.lastname: Reid
authors.forename: Aaron
authors.initials: A
authors.lastname: McDaid
authors.forename: Neil
authors.initials: N
authors.lastname: Hurley
mesh_terms: D000465:Algorithms; D019985:Benchmarking; D008962:Models, Theoretical; D012441:Saccharomyces cerevisiae / Q000378:metabolism; D060756:Social Networking; D013269:Stochastic Processes