An Empirical Study of the Relation Between Community Structure and Transitivity

Abstract

One of the most prominent properties in real-world networks is the presence of a community structure, i.e. dense and loosely interconnected groups of nodes called communities. In an attempt to better understand this concept, we study the relationship between the strength of the community structure and the network transitivity (or clustering coefficient). Although intuitively appealing, this analysis was not performed before. We adopt an approach based on random models to empirically study how one property varies depending on the other. It turns out the transitivity increases with the community structure strength, and is also affected by the distribution of the community sizes. Furthermore, increasing the transitivity also results in a stronger community structure. More surprisingly, if a very weak community structure causes almost zero transitivity, the opposite is not true and a network with a close to zero transitivity can still have a clearly defined community structure. Further analytical work is necessary to characterize the exact nature of the identified relationship.

arXiv comment3rd Workshop on Complex Networks, Melbourne, Florida : United States (2012)

References in corpus (13)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Hierarchical structure and the prediction of missing links in networks
• Random graphs with clustering
• Characterizing the community structure of complex networks
• Complex cooperative networks from evolutionary preferential attachment
• Qualitative Comparison of Community Detection Algorithms

Cited by in corpus (9)

• On community structure in complex networks: challenges and opportunities
• Characterizing the Interactions Between Classical and Community-aware Centrality Measures in Complex Networks
• Comparative evaluation of community-aware centrality measures
• Towards realistic artificial benchmark for community detection algorithms evaluation
• Interplay between $k$-core and community structure in complex networks
• Micro, Meso, Macro: the effect of triangles on communities in networks
• A Generative Model of Software Dependency Graphs to Better Understand Software Evolution
• Understanding Trends, Patterns, and Dynamics in Global Company Acquisitions: A Network Perspective
• How Correlated are Community-aware and Classical Centrality Measures in Complex Networks?