所属 コンピュータサイエンス学部 コンピュータサイエンス学科 職種 専任講師
|標題||Estimating Node Connectedness in Spatial Network under Stochastic Link Disconnection Based on Efficient Sampling|
|掲載誌名||Applied Network Science|
|著者・共著者||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.