Publication Date:
2018-01-12
Description:
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,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,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,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,3}$ appear in some triangles. We analyze the expected numbers of induced $K_{3,3}$ and triangles ( $Delta$ ) in four representative random graph models, namely, Erdős-Rényi random graph model, Watts-Strogatz small-world model, Barabási-Albert preferential attachment model, and configuration model, and give an algorithm to enumerate all distinct $K_{3,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,3}$ found helps to find new stars collaborated by well-known figures who themselves do not collaborate.
Print ISSN:
1041-4347
Electronic ISSN:
1558-2191
Topics:
Computer Science
Permalink
