フシミ　タカヤス   Takayasu Fushimi   伏見　卓恭    所属   コンピュータサイエンス学部 コンピュータサイエンス学科    職種   専任講師
言語種別	英語
発行・発表の年月	2019/08
形態種別	学術論文
査読	査読あり
標題	Estimating Node Connectedness in Spatial Network under Stochastic Link Disconnection Based on Efficient Sampling
執筆形態	共著
掲載誌名	Applied Network Science
掲載区分	国外
巻・号・頁	4(66),pp.1-24
著者・共著者	Takayasu Fushimi，Kazumi Saito，Tetsuo Ikeda，Kazuhiro Kazama
概要	Many networks including spatial networks, social networks, and web networks, are not deterministic but probabilistic due to the uncertainty of link existence. From networks with such uncertainty, to extract densely connected nodes, we propose connectedness centrality and its extended version, group connectedness centrality, where the connectedness of each node is defined as the expected size of its connected component over all possible graphs produced by an uncertain graph. In a large-scale network, however, since the number of combinations of possible graphs is enormous, it is difficult to strictly calculate the expected value. Therefore, we also propose an efficient estimation method based on Monte Carlo sampling. When applying our method to road networks, the extracted nodes can be regarded as candidate sites of evacuation facilities that many residents can reach even in the situation where roads are stochastically blocked by natural disasters. In our experimental evaluations using actual road networks, we show the following promising characteristics: our proposed method 1) works stably with respect to the number of simulations; 2) extracts nodes set reachable from more nodes even in a situation that many links are deleted; and 3) computes much more efficient, compared to existing centrality measures and community extraction methods.