First Passage Time for RandomWalks in Heterogeneous Networks

박사과정 황성민군 과 강병남 교수는 인하대 이덕선 교수와 공동연구로 복잡계 네트워크 위에서 random walks 에 대한 연구를 수행하였다. 특별히 first passage time 분포함수에 대한 연구를 해석적으로 구한 연구이다. 이 양은 복잡계 통계물리에서 잘 알려진 물리 양이지만 수학적으로 구하기가 어려워서 그의 성질이 알려지지 않은 양이었다. 본 논문에서 구한 해석적인 해를 기반으로 해서 차후에 복잡계에서의 여러 동역학적 성질이 밝혀질 것으로 기대된다.

The first passage time (FPT) for random walks is a key indicator of how fast information diffuses in a given system. Despite the role of FPT as a fundamental feature in transport phenomena, its behavior, particularly in heterogeneous networks, is not yet fully understood. Here, we study, both analytically and numerically, the scaling behavior of the FPT distribution to a given target node, averaged over all starting nodes.We find that random walks arrive quickly at a local hub, and therefore, the FPT distribution shows a crossover with respect to time from fast decay behavior (induced from the attractive effect to the hub) to slow decay behavior (caused by the exploring of the entire system). Moreover, the mean FPT is independent of the degree of the target node in the case of compact exploration. These theoretical results justify the necessity of using a random jump protocol (empirically used in search engines) and provide guidelines for designing an effective network to make information quickly accessible.

PRL 109, 088701 (2012)