| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs | Ethan R. Elenberg
; Karthikeyan Shanmugam
; Michael Borokhovich
; Alexandros G. Dimakis
; | Date: |
22 Jun 2015 | Abstract: | We study the problem of approximating the $3$-profile of a large graph.
$3$-profiles are generalizations of triangle counts that specify the number of
times a small graph appears as an induced subgraph of a large graph. Our
algorithm uses the novel concept of $3$-profile sparsifiers: sparse graphs that
can be used to approximate the full $3$-profile counts for a given large graph.
Further, we study the problem of estimating local and ego $3$-profiles, two
graph quantities that characterize the local neighborhood of each vertex of a
graph.
Our algorithm is distributed and operates as a vertex program over the
GraphLab PowerGraph framework. We introduce the concept of edge pivoting which
allows us to collect $2$-hop information without maintaining an explicit
$2$-hop neighborhood list at each vertex. This enables the computation of all
the local $3$-profiles in parallel with minimal communication.
We test out implementation in several experiments scaling up to $640$ cores
on Amazon EC2. We find that our algorithm can estimate the $3$-profile of a
graph in approximately the same time as triangle counting. For the harder
problem of ego $3$-profiles, we introduce an algorithm that can estimate
profiles of hundreds of thousands of vertices in parallel, in the timescale of
minutes. | Source: | arXiv, 1506.6671 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |