Presentation Information
[B-16-16]A Study on the Effect of Low-Degree Node Aggregation on Random-Walk Hitting Time
◎△Kazuma Denda1, Han Nay Aung1, Ohsaki Hiroyuki1 (1. Kwansei Gakuin University)
Keywords:
low-degree node aggregation,random walk,hitting time
The arrival time in a random walk on a network represents the expected number of steps required to reach a target node from the starting point and serves as a fundamental measure for evaluating the efficiency of search, surveillance, and distributed information gathering. Since the transition structure of a random walk directly reflects the connectivity between nodes, even minor local structural changes can alter the arrival time. In fact, it has been pointed out that in networks containing higher-order relationships, the definition and structural representation of a random walk can influence the properties of the transition process.
When dealing with large-scale graphs, aggregating leaf nodes of degree 1 and intermediate nodes of degree 2 into their adjacent nodes can be one method to reduce the scope of analysis. However, since aggregation simultaneously alters both the state space and the connectivity, the arrival times measured in the original graph are not necessarily comparable to those measured in the aggregated graph. Therefore, in this paper, we focus on undirected, unweighted, connected graphs and quantitatively evaluate the impact of aggregating leaf nodes and degree-2 nodes on the arrival time from a random starting point to a low-degree target node.
When dealing with large-scale graphs, aggregating leaf nodes of degree 1 and intermediate nodes of degree 2 into their adjacent nodes can be one method to reduce the scope of analysis. However, since aggregation simultaneously alters both the state space and the connectivity, the arrival times measured in the original graph are not necessarily comparable to those measured in the aggregated graph. Therefore, in this paper, we focus on undirected, unweighted, connected graphs and quantitatively evaluate the impact of aggregating leaf nodes and degree-2 nodes on the arrival time from a random starting point to a low-degree target node.