PTE
Authors:
Open Access
- 13 August 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1115-1124
Abstract
How can we enumerate triangles from an enormous graph with billions of vertices and edges? Triangle enumeration is an important task for graph data analysis with many applications including identifying suspicious users in social networks, detecting web spams, finding communities, etc. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks; however, they suffer from the massive shuffled data resulting in a very long processing time. In this paper, we propose PTE (Pre-partitioned Triangle Enumeration), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read. Experimental results show that PTE provides up to 47 times faster performance than recent distributed algorithms on real world graphs, and succeeds in enumerating more than 3 trillion triangles on the ClueWeb12 graph with 6.3 billion vertices and 72 billion edges, which any previous triangle computation algorithm fail to process.Keywords
Funding Information
- Ministry of Science, ICT and Future Planning (R0101-15-0176,R0190-15-2012)
This publication has 22 references indexed in Scilit:
- Uncovering social network Sybils in the wildACM Transactions on Knowledge Discovery From Data, 2014
- Net-Ray: Visualizing and Mining Billion-Scale GraphsLecture Notes in Computer Science, 2014
- Massive graph triangulation2013
- gbase: an efficient analysis platform for large graphsThe VLDB Journal, 2012
- Efficient algorithms for large-scale local triangle countingACM Transactions on Knowledge Discovery From Data, 2010
- Discovering Community-Oriented Roles of Nodes in a Social NetworkLecture Notes in Computer Science, 2010
- Main-memory triangle computations for very large (sparse (power-law)) graphsTheoretical Computer Science, 2008
- Defining and identifying communities in networksProceedings of the National Academy of Sciences, 2004
- Curvature of co-links uncovers hidden thematic layers in the World Wide WebProceedings of the National Academy of Sciences, 2002
- New hash functions and their use in authentication and set equalityJournal of Computer and System Sciences, 1981