.png){kind=icon}
返回
Exploring Triangle-Free Dense Structures
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2017.2764468.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Triangle-free
dense structures
social networks
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.9K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容