Research progress of triangle counting in big data
Counting triangles in a graph is an important step to calculate the clustering coefficient and the transitivity ratio of the network，which is widely used in important role identification，spam detection，community discovery，biological detection etc.Counting triangles algorithm is mainly faced with two...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Beijing Xintong Media Co., Ltd
2016-06-01
|
| Series: | Dianxin kexue |
| Subjects: | |
| Online Access: | http://www.telecomsci.com/zh/article/doi/10.11959/j.issn.1000-0801.2016169/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841529899275255808 |
|---|---|
| author | Hongqiao JIN Yihong DONG |
| author_facet | Hongqiao JIN Yihong DONG |
| author_sort | Hongqiao JIN |
| collection | DOAJ |
| description | Counting triangles in a graph is an important step to calculate the clustering coefficient and the transitivity ratio of the network，which is widely used in important role identification，spam detection，community discovery，biological detection etc.Counting triangles algorithm is mainly faced with two major problems of space-time consumption and accuracy.The representative algorithm of the counting triangles in the big graph was introduced.There existed two kinds of algorithms，which were exact counting algorithm and approximate counting algorithm.Exact counting algorithms were divided into internal memory algorithm，external memory algorithm and distributed algorithm.The space-time consumption or I/O consumption of exact counting algorithm was very large.Approximate counting algorithms were divided into auxiliary algorithm，static algorithm and streaming algorithm.In the end，the counting triangles algorithms were summarized. |
| format | Article |
| id | doaj-art-961c254304af4a1aad7999a4bfcee840 |
| institution | Kabale University |
| issn | 1000-0801 |
| language | zho |
| publishDate | 2016-06-01 |
| publisher | Beijing Xintong Media Co., Ltd |
| record_format | Article |
| series | Dianxin kexue |
| spelling | doaj-art-961c254304af4a1aad7999a4bfcee8402025-01-15T03:14:45ZzhoBeijing Xintong Media Co., LtdDianxin kexue1000-08012016-06-013215316259608447Research progress of triangle counting in big dataHongqiao JINYihong DONGCounting triangles in a graph is an important step to calculate the clustering coefficient and the transitivity ratio of the network，which is widely used in important role identification，spam detection，community discovery，biological detection etc.Counting triangles algorithm is mainly faced with two major problems of space-time consumption and accuracy.The representative algorithm of the counting triangles in the big graph was introduced.There existed two kinds of algorithms，which were exact counting algorithm and approximate counting algorithm.Exact counting algorithms were divided into internal memory algorithm，external memory algorithm and distributed algorithm.The space-time consumption or I/O consumption of exact counting algorithm was very large.Approximate counting algorithms were divided into auxiliary algorithm，static algorithm and streaming algorithm.In the end，the counting triangles algorithms were summarized.http://www.telecomsci.com/zh/article/doi/10.11959/j.issn.1000-0801.2016169/exact countingapproximate countingtrianglegraph |
| spellingShingle | Hongqiao JIN Yihong DONG Research progress of triangle counting in big data Dianxin kexue exact counting approximate counting triangle graph |
| title | Research progress of triangle counting in big data |
| title_full | Research progress of triangle counting in big data |
| title_fullStr | Research progress of triangle counting in big data |
| title_full_unstemmed | Research progress of triangle counting in big data |
| title_short | Research progress of triangle counting in big data |
| title_sort | research progress of triangle counting in big data |
| topic | exact counting approximate counting triangle graph |
| url | http://www.telecomsci.com/zh/article/doi/10.11959/j.issn.1000-0801.2016169/ |
| work_keys_str_mv | AT hongqiaojin researchprogressoftrianglecountinginbigdata AT yihongdong researchprogressoftrianglecountinginbigdata |