Paper Abstract and Keywords |
Presentation |
2020-12-04 14:00
[Invited Talk]
How many vertices does a random walk miss in a network with moderately increasing the number of vertices? Shuji Kijima (Kyushu Univ.), Nobutaka Shimizu (The Univ. of Tokyo), Takeharu Shiraga (Chuo Univ.) COMP2020-23 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
Real networks are often dynamic. In response to it, analyses of algorithms on dynamic networks attract more and more attention in network science and engineering. Random walks on dynamic graphs also have been investigated actively in more than a decade, where in most cases the edge set changes but the vertex set is static. The vertex sets are also dynamic in many real networks. Motivated by a new technology of the analysis of random walks on dynamic graphs, this paper introduces a simple model of graphs with an increasing number of vertices and presents an analysis of random walks associated with the cover time on such graphs. In particular, we studied the number of unvisited vertices of a random walk on a growing graph where a new vertex is attached at an interval defined by some duration function. In this talk, I’d like to show some interesting relationship between duration functions and the number of unvisited vertices. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
Cover time / Dynamic graph / Evolving graph / Temporal graph / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 120, no. 276, COMP2020-23, pp. 29-29, Dec. 2020. |
Paper # |
COMP2020-23 |
Date of Issue |
2020-11-27 (COMP) |
ISSN |
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 |
COMP2020-23 |
Conference Information |
Committee |
COMP |
Conference Date |
2020-12-04 - 2020-12-04 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Online |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
COMP |
Conference Code |
2020-12-COMP |
Language |
English |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
How many vertices does a random walk miss in a network with moderately increasing the number of vertices? |
Sub Title (in English) |
|
Keyword(1) |
Cover time |
Keyword(2) |
Dynamic graph |
Keyword(3) |
Evolving graph |
Keyword(4) |
Temporal graph |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Shuji Kijima |
1st Author's Affiliation |
Kyushu University (Kyushu Univ.) |
2nd Author's Name |
Nobutaka Shimizu |
2nd Author's Affiliation |
The University of Tokyo (The Univ. of Tokyo) |
3rd Author's Name |
Takeharu Shiraga |
3rd Author's Affiliation |
Chuo University (Chuo Univ.) |
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-3 |
Date Time |
2020-12-04 14:00:00 |
Presentation Time |
60 minutes |
Registration for |
COMP |
Paper # |
COMP2020-23 |
Volume (vol) |
vol.120 |
Number (no) |
no.276 |
Page |
p.29 |
#Pages |
1 |
Date of Issue |
2020-11-27 (COMP) |
|