.png){kind=icon}
.png){kind=icon}
Return
Exploring Triangle-Free Dense Structures
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2017.2764468.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Triadic closure is ubiquitous in social networks, which refers to the property among three individuals, A, B, and C, such that if there exist strong ties between A-B and A-C, then there must be a strong or weak tie between B-C. Related to triadic closure, the number of triangles has been extensively studied since it can be effectively used as a metric to analyze the structure and function of a network. In this paper, from a different viewpoint, we study triangle-free dense structures which have received little attention. We focus on K-3,K-3 where there are two subsets of three vertices, a vertex in a subset has an edge connected to every vertex in another subset while it does not have an edge to any other vertex in the same subset. Such K-n,K-n in general implies a philosophy contradiction: (a) Any two individuals are friends if they have no common friends, and (b) Any two individuals are not friends if they have common friends. However, we find such induced K-3,K-3 does exist frequently, and they do not disappear over time over a real academic collaboration network. In addition, in the real datasets tested, nearly all edges appearing in K-3,K-3 appear in some triangles. We analyze the expected numbers of induced K-3,K-3 and triangles (Delta) in four representative random graph models, namely, Erdos-Renyi random graph model, Watts-Strogatz small-world model, Barabasi-Albert preferential attachment model, and configuration model, and give an algorithm to enumerate all distinct K-3,K-3 in an undirected social network. We conduct extensive experiments on both real and synthetic datasets to confirm our findings. As an application, such K-3,K-3 found helps to find new stars collaborated by well-known figures who themselves do not collaborate.
Keywords:
Triangle-free
dense structures
social networks
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.4
Papers:
6.8K
Citations:
3.2W