Paper Abstract and Keywords |
Presentation |
2012-09-02 10:30
Detecting Changes of Graph Partitioning Structures using Stochastic Decision Trees Shoichi Sato, Kenji Yamanishi (Univ. of Tokyo) PRMU2012-31 IBISML2012-14 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
We are concerned with the issue of estimating graph partitioning structures
from time series and tracking their changes over time.
The issue of graph partitioning is important in that it leads to
extracting network communities. Detecting changes of graph partitioning
may also be significant since it is related to event detection.
We present a new algorithm for detecting graph structure changes.
The key ideas are: 1) We employ stochastic
decision trees to represent probabilistic models of graph partitioning
structures. 2) We then reduce the issue of change detection for graph
structures to that of detecting changes of tree structures on the basis
of the minimum description length principle.
We use artificial and real data sets to empirically demonstrate the validity
of our algorithm in comparison with Sun et.al.'s existing algorithm. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
Stochastic Decision Tree / Normalized Maximum Likelihood(NML) / Dynamic Model Selection / Minimum Description Length(MDL) Principle / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 112, no. 198, IBISML2012-14, pp. 9-16, Sept. 2012. |
Paper # |
IBISML2012-14 |
Date of Issue |
2012-08-26 (PRMU, IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
PRMU2012-31 IBISML2012-14 |
Conference Information |
Committee |
PRMU IBISML IPSJ-CVIM |
Conference Date |
2012-09-02 - 2012-09-03 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
|
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
IBISML |
Conference Code |
2012-09-PRMU-IBISML-CVIM |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Detecting Changes of Graph Partitioning Structures using Stochastic Decision Trees |
Sub Title (in English) |
|
Keyword(1) |
Stochastic Decision Tree |
Keyword(2) |
Normalized Maximum Likelihood(NML) |
Keyword(3) |
Dynamic Model Selection |
Keyword(4) |
Minimum Description Length(MDL) Principle |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Shoichi Sato |
1st Author's Affiliation |
University of Tokyo (Univ. of Tokyo) |
2nd Author's Name |
Kenji Yamanishi |
2nd Author's Affiliation |
University of Tokyo (Univ. of Tokyo) |
3rd Author's Name |
|
3rd Author's Affiliation |
() |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2012-09-02 10:30:00 |
Presentation Time |
30 minutes |
Registration for |
IBISML |
Paper # |
PRMU2012-31, IBISML2012-14 |
Volume (vol) |
vol.112 |
Number (no) |
no.197(PRMU), no.198(IBISML) |
Page |
pp.9-16 |
#Pages |
8 |
Date of Issue |
2012-08-26 (PRMU, IBISML) |