2011 TriangleListinginMassiveNetwork

• (Chu & Cheng, 2011) ⇒ Shumo Chu, and James Cheng. (2011). “Triangle Listing in Massive Networks and Its Applications.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020513

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Triangle+Listing+in+Massive+Networks+and+Its+Applications
• http://dl.acm.org/citation.cfm?id=2020408.2020513&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; clustering coefficient; data mining; experimentation; graph algorithms; large graphs; massive networks; performance; triangle counting; triangle listing

Abstract

Triangle listing is one of the fundamental algorithmic problems whose solution has numerous applications especially in the analysis of complex networks, such as the computation of clustering coefficient, transitivity, triangular connectivity, etc. Existing algorithms for [triangle listing]] are mainly in-memory algorithms, whose performance cannot scale with the massive volume of today's fast growing networks. When the input graph cannot fit into main memory, triangle listing requires random disk accesses that can incur prohibitively large I/O cost. Some streaming and sampling algorithms have been proposed but these are approximation algorithms. We propose an I/O-efficient algorithm for triangle listing. Our algorithm is exact and avoids random disk access. Our results show that our algorithm is scalable and outperforms the state-of-the-art local triangle estimation algorithm.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 TriangleListinginMassiveNetwork	Shumo Chu James Cheng			Triangle Listing in Massive Networks and Its Applications				10.1145/2020408.2020513		2011