| Presentation | 2018-03-05 Implementation of global partition algorithm and verification of hyperfiniteness for property testing of real-world networks Yutaro Honda, Hiro Ito, Munehiko Sasajima, Yushi Uno, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In recent years, the necessity of analyzing big data is increasing to utilize them. In such cases, sublinear-time algorithms are required, and especially, if algorithms can run in constant-time. In theoretical computer science field, a topic called property testing has been actively studied recently. The basic framework of property testing is to decide within some inaccuracy if the input data has a certain property or far from it by only reading some part of the input. Hyperfiniteness is one of the concepts for guaranteeing such locality defined on graphs. This research tries to implement such purely theoretical property testing algorithms for graphs in order to practically analyze real-world networks. However, there is difficulty that if we can actually obtain partitions of networks that satisfy hyperfiniteness. The purpose of this research is to verify if various kinds of networks have that property. As a result, we find that property testing could be realized for networks that are close to planar graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | property testing / hyperfiniteness / constant-time algorithm / big data / real-world networks |
| Paper # | COMP2017-52 |
| Date of Issue | 2018-02-26 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2018/3/5(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Osaka Prefecture Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiro Ito(Univ. of Electro-Comm.) |
| Vice Chair | Yushi Uno(Osaka Pref. Univ.) |
| Secretary | Yushi Uno(Seikei Univ.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Implementation of global partition algorithm and verification of hyperfiniteness for property testing of real-world networks |
| Sub Title (in English) | |
| Keyword(1) | property testing |
| Keyword(2) | hyperfiniteness |
| Keyword(3) | constant-time algorithm |
| Keyword(4) | big data |
| Keyword(5) | real-world networks |
| 1st Author's Name | Yutaro Honda |
| 1st Author's Affiliation | Osaka Prefecture University(Osaka Pref. Univ.) |
| 2nd Author's Name | Hiro Ito |
| 2nd Author's Affiliation | University of Electro-Communications(UEC) |
| 3rd Author's Name | Munehiko Sasajima |
| 3rd Author's Affiliation | University of Hyogo(Univ. of Hyogo) |
| 4th Author's Name | Yushi Uno |
| 4th Author's Affiliation | Osaka Prefecture University(Osaka Pref. Univ.) |
| Date | 2018-03-05 |
| Paper # | COMP2017-52 |
| Volume (vol) | vol.117 |
| Number (no) | COMP-474 |
| Page | pp.pp.43-50(COMP), |
| #Pages | 8 |
| Date of Issue | 2018-02-26 (COMP) |