Shaping Communities out of Triangles

Abstract

Community detection has arisen as one of the most relevant topics in the field of graph data mining due to its importance in many fields such as biology, social networks or network traffic analysis. The metrics proposed to shape communities are generic and follow two approaches: maximizing the internal density of such communities or reducing the connectivity of the internal vertices with those outside the community. However, these metrics take the edges as a set and do not consider the internal layout of the edges in the community. We define a set of properties oriented to social networks that ensure that communities are cohesive, structured and well defined. Then, we propose the Weighted Community Clustering (WCC), which is a community metric based on triangles. We proof that analyzing communities by triangles gives communities that fulfill the listed set of properties, in contrast to previous metrics. Finally, we experimentally show that WCC correctly captures the concept of community in social networks using real and syntethic datasets, and compare statistically some of the most relevant community detection algorithms in the state of the art.

arXiv comment10 pages, 6 figures, CIKM 2012

References in corpus (19)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• The structure of scientific collaboration networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community detection algorithms: a comparative analysis
• Link communities reveal multiscale complexity in networks
• Community detection in complex networks using Extremal Optimization
• Why social networks are different from other types of networks
• Finding statistically significant communities in networks
• The performance of modularity maximization in practical contexts
• Networks of strong ties
• Communities and bottlenecks: Trees and treelike networks have high modularity