Exploring Triangle-Free Dense Structures

Lu, C; Yu, JX; Wei, H

Exploring Triangle-Free Dense Structures

Lu, C Yu, JX

Wei, H

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2018, 30 (2), pp. 278 - 291
Issue Date:: 2018-02-01

Closed Access

	Filename	Description	Size
	08074776.pdf	Published Version	1.38 MB		View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Lu, C	en_US
dc.contributor.author	Yu, JX https://orcid.org/0000-0002-9738-827X	en_US
dc.contributor.author	Wei, H	en_US
dc.date.issued	2018-02-01	en_US
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2018, 30 (2), pp. 278 - 291	en_US
dc.identifier.issn	1041-4347	en_US
dc.identifier.uri	http://hdl.handle.net/10453/131874
dc.description.abstract	© 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.	en_US
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering	en_US
dc.relation.isbasedon	10.1109/TKDE.2017.2764468	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Exploring Triangle-Free Dense Structures	en_US
dc.type	Journal Article
utslib.citation.volume	2	en_US
utslib.citation.volume	30	en_US
utslib.for	0803 Computer Software	en_US
utslib.for	08 Information and Computing Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	closed_access
pubs.issue	2	en_US
pubs.publication-status	Published	en_US
pubs.volume	30	en_US

Abstract:

© 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/131874