Paper Info
Title
Degree relations of triangles in real-world networks and graph 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 investigate whether current graph models reproduce the types of triangles that are observed in real data and observe that most models fail to accurately capture these salient features.
Year
DOI
Venue
2012
10.1145/2396761.2398503
CIKM
Keywords
Field
DocType
distinguishing feature,degree homogeneity,real-world graph,degree-labeled triangle,current graph model,collaborative situation,information network,real-world network,heterogeneous triangle,degree relation,heterogeneous graph,social networks
Graph,Discrete mathematics,Combinatorics,Information networks,Social network,Vertex (geometry),Computer science,Homogeneous,CPCTC,Nested triangles graph,Salient
Conference
ISSN
Citations 
PageRank 
CIKM '12: Proceedings of the 21st ACM International Conference on Information and Knowledge Management, ACM, pp. 1712-1716, 2012
13
0.66
References 
Authors
17
4
Name
Order
Citations
PageRank
Nurcan Durak1435.33
Ali Pinar289764.46
Tamara G. Kolda35079262.60
C. Seshadhri493661.33