K-truss decomposition for Scale-Free Graphs at Scale in Distributed Memory
Authors:
- 1 September 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
We update our prior 2017 Graph Challenge submission [11] on large scale triangle counting in distributed memory by extending it to compute the full k-truss decomposition [6] of large scale-free graphs. We build on heuristics to minimize `wedge checks', by operating on an ordered directed graph, and describe an algorithm to `unroll' triangle counts when they are scheduled for pruning by the k-truss decomposition. Our k-truss algorithm is implemented using HavoqGT, an asynchronous vertex-centric graph analytics framework for distributed memory. We present a brief experimental evaluation on two large, real-world, scale-free graphs: a 128B edge web-graph and a 1.4B edge twitter follower graph. To our knowledge, the 128B edge web-graph is the largest real-world graph to have its k-truss decomposition computed.Keywords
This publication has 15 references indexed in Scilit:
- Machine learning approach to detect intruders in database based on hexplet data structureJournal of Electrical Systems and Information Technology, 2016
- Security maturity in NoSQL databases - are they secure enough to haul the modern IT applications?2015
- A Dynamic Approach to Detect Anomalous Queries on Relational Databases2015
- Real-Time Intrusion Prediction Using Hidden Markov Model with Genetic Algorithm2014
- A novel approach for predicting the length of hospital stay with DBSCAN and supervised classification algorithms2014
- Intrusion detection in role administrated database: Transaction-based approach2013
- A hybrid method based on genetic algorithm, self-organised feature map, and support vector machine for better network anomaly detection2013
- A novel intrusion detection system based on hierarchical clustering and support vector machinesExpert Systems with Applications, 2011
- Detecting anomalous access patterns in relational databasesThe VLDB Journal, 2007
- Anomaly detection of web-based attacks2003