Degree Relations of Triangles in Real-world Networks and Models

Abstract

Triangles are an important building block and distinguishing feature of real-world networks, but their structure is still poorly understood. Despite numerous reports on the abundance of triangles, there is very little information on what these triangles look like. We initiate the study of degree-labeled triangles -- specifically, degree homogeneity versus heterogeneity in triangles. This yields new insight into the structure of real-world graphs. We observe that networks coming from social and collaborative situations are dominated by homogeneous triangles, i.e., degrees of vertices in a triangle are quite similar to each other. On the other hand, information networks (e.g., web graphs) are dominated by heterogeneous triangles, i.e., the degrees in triangles are quite disparate. Surprisingly, nodes within the top 1% of degrees participate in the vast majority of triangles in heterogeneous graphs. We also ask the question of whether or not current graph models reproduce the types of triangles that are observed in real data and showed that most models fail to accurately capture these salient features.

References in corpus (9)

• Emergence of scaling in random networks
• Power-law distributions in empirical data
• Assortative mixing in networks
• Biological network comparison using graphlet degree distribution
• Kronecker Graphs: An Approach to Modeling Networks
• Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web
• Community structure and scale-free collections of Erdös-Rényi graphs
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Exploring the assortativity-clustering space of a network's degree sequence

Cited by in corpus (14)

• Counting Triangles in Massive Graphs with MapReduce
• Tensor Spectral Clustering for Partitioning Higher-order Network Structures
• Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs
• The impossibility of low rank representations for triangle-rich complex networks
• ESCAPE: Efficiently Counting All 5-Vertex Subgraphs
• Directed Random Geometric Graphs
• Evolution of Directed Triangle Motifs in the Google+ OSN
• Random clique covers for graphs with local density and global sparsity
• Self-Coordinated Corona Graphs: a model for complex networks
• On the Power of Edge Independent Graph Models
• Counting Triangles in Real-World Graph Streams: Dealing with Repeated Edges and Time Windows
• Large Graph Models: A Review
• Do Language Models Pass the Bechdel Test? Auditing Gender Biases in LLM-Generated Screenplays
• How the Degeneracy Helps for Triangle Counting in Graph Streams