Exploring Triangle-Free Dense Structures

© 2017 IEEE. Triadic closure is ubiquitous in social networks, which refers to the property among three individuals, A, B, and C, such thatif 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, thenumber of triangles has been extensively studied since it can be effectively used as a metric to analyze the structure and function of anetwork. In this paper, from a different viewpoint, we study triangle-free dense structures which have received little attention. We focuson K3;3 where there are two subsets of three vertices, a vertex in a subset has an edge connected to every vertex in another subsetwhile it does not have an edge to any other vertex in the same subset. Such Kn;n in general implies a philosophy contradiction: (a) Anytwo 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 K3;3 does exist frequently, and they do not disappear over time over a real academic collaborationnetwork. In addition, in the real datasets tested, nearly all edges appearing in K3;3 appear in some triangles. We analyze the expectednumbers of induced K3;3 and triangles (D) 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 toenumerate all distinct K3;3 in an undirected social network. We conduct extensive experiments on both real and synthetic datasets toconfirm our findings. As an application, such K3;3 found helps to find new stars collaborated by well-known figures who themselves donot collaborate