Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs

Details Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs

2006-09-20

arxiv.org/abs/cs/0609116v1

Computer Science

Data Structures and Algorithms

Scientific paper

Finding, counting and/or listing triangles (three vertices with three edges) in large graphs are natural fundamental problems, which received recently much attention because of their importance in complex network analysis. We provide here a detailed state of the art on these problems, in a unified way. We note that, until now, authors paid surprisingly little attention to space complexity, despite its both fundamental and practical interest. We give the space complexities of known algorithms and discuss their implications. Then we propose improvements of a known algorithm, as well as a new algorithm, which are time optimal for triangle listing and beats previous algorithms concerning space complexity. They have the additional advantage of performing better on power-law graphs, which we also study. We finally show with an experimental study that these two algorithms perform very well in practice, allowing to handle cases that were previously out of reach.

Affiliated with

Also associated with

No associations

Rating

Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-350724