2012 OntheSeparabilityofStructuralCl

(Abrahao et al., 2012) ⇒ Bruno Abrahao, Sucheta Soundarajan, John Hopcroft, and Robert Kleinberg. (2012). “On the Separability of Structural Classes of Communities.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339631

Subject Headings:

Notes

Cited By

Quotes

Author Keywords

Class separability; community structure; design methodology; detection algorithms; networks

Abstract

Three major factors govern the intricacies of community extraction in networks: (1) the application domain includes a wide variety of networks of fundamentally different natures, (2) the literature offers a multitude of disparate community detection algorithms, and (3) there is no consensus characterizing how to discriminate communities from non-communities. 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 demostrate 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 different detection algorithms extract fundamentally different structures; (2) the structure of communities that arise in practice is closest to that of communities that random-walk-based algorithms extract, although still siginificantly different 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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 OntheSeparabilityofStructuralCl	John E. Hopcroft Bruno Abrahao Sucheta Soundarajan Robert Kleinberg			On the Separability of Structural Classes of Communities				10.1145/2339530.2339631		2012