Fast Triangle Counting through Wedge Sampling

Details Fast Triangle Counting through Wedge Sampling Fast Triangle Counting through Wedge Sampling

2012-02-23

arxiv.org/abs/1202.5230v1

Computer Science

Social and Information Networks

Scientific paper

Graphs and networks are used to model interactions in a variety of contexts, and there is a growing need to be able to quickly assess the qualities of a graph in order to understand its underlying structure. Some of the most useful metrics are triangle based and give a measure of the connectedness of "friends of friends." Counting the number of triangles in a graph has, therefore, received considerable attention in recent years. We propose new sampling-based methods for counting the number of triangles or the number of triangles with vertices of specified degree in an undirected graph and for counting the number of each type of directed triangle in a directed graph. The number of samples depends only on the desired relative accuracy and not on the size of the graph. We present extensive numerical results showing that our methods are often much better than the error bounds would suggest. In the undirected case, our method is generally superior to other approximation approaches; in the undirected case, ours is the first approximation method proposed.

Affiliated with

Also associated with

No associations

Rating

Fast Triangle Counting through Wedge Sampling 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 Fast Triangle Counting through Wedge Sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Triangle Counting through Wedge Sampling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-660676