On the Separability of Structural Classes of Communities
Channel: brunoutubeacc
Date: 2012-07-31

Three major factors govern the intricacies of community extraction in networks: (1) the application domain includes a wide variety of networks of fundamentally diﬀerent natures, (2) the literature oﬀers a multitude of disparate community detection algorithms, and (3) there is no consensus characterizing how to discriminate communities from noncommunities. In this paper, we present a comprehensive analysis of community properties through a class separability framework. Our approach enables the assessement of the structural dissimilarity among the output of multiple community detection algorithms and between the output of algorithms and communities that arise in practice. To demonstrate this concept, we furnish our method with a large set of structural properties and multiple community detection algorithms. Applied to a diverse collection of large scale
network datasets, the analysis reveals that (1) the diﬀerent detection algorithms extract fundamentally diﬀerent structures; (2) the structure of communities that arise in practice
is closest to that of communities that random-walk-based algorithms extract, although still siginiﬁcantly diﬀerent from that of the output of all the algorithms; and (3) a small
subset of the properties are nearly as discriminative as the full set, while making explicit the ways in which the algorithms produce biases. Our framework enables an informed
choice of the most suitable community detection method for a given purpose and network and allows for a comparison of existing community detection algorithms while guiding the
design of new ones.