Extending the Walktrap Algorithm to Directed Graphs via Hitting Time and Stationary Distribution
Người báo cáo: Đỗ Duy Hiếu
Speaker: Đỗ Duy Hiếu, Viện Toán học
Thời gian: 14h Thứ 5, ngày 22/05/2025
Địa điểm: Phòng 507 nhà A6
Link online Zoom: https://zoom.us/j/96058506399?pwd=ZwJHlZg0qb5ijT8Mj5GttENSYED0Kh.1
Meeting ID: 891 3406 2450Passcode: 123456
Abstract: Community detection has been extensively studied through a wide range of algorithms. One of the most influential methods for undirected graphs is the Walktrap algorithm, which estimates distances between vertices via random walks and evaluates communities based on modularity derived from vertex degrees. While several attempts have been made to adapt this method to directed graphs, they have achieved limited success.
In this talk, I will revisit the Walktrap algorithm (Pons and Latapy, J. Graph Algorithms Appl., 10:191–218, 2006) and present an extension that is suitable for directed graphs. The key idea is to redefine the distance between vertices using the hitting time and the stationary distribution of a random walk. These definitions are both theoretically grounded and computationally efficient, as they rely on well-established algorithms. Notably, this framework also recovers the undirected case as a special instance. Finally, I will present an implementation of the proposed algorithm and discuss its practicality and effectiveness through experiments.
This work is based on joint research with Phan Thị Hà Dương and Đặng Tiến Đạt.
Tin tức nổi bật
Hoạt động tuần
Hội thảo sắp diễn ra
16/06/26, Hội nghị, hội thảo:
International Conference “Complex Hyperbolicity, Function fields and Non-archimedean Arithmetic
09/11/26, Hội nghị, hội thảo:
Workshop on singularities and related topics (Conference in memory of Professor Lê Dũng Tráng)
Xuất bản mới
Trần Quang Hóa,
Đỗ Trọng Hoàng,
Le Van Dinh,
Nguyễn Đăng Hợp,
Thái Thành Nguyễn,
Asymptotic depth of invariant chains of edge ideals,
Journal of Combinatorial Theory, Series A Volume 224, November 2026, 106221
.
Nguyễn Duy Tân,
Nguyễn Quốc Thắng,
On fields with Serre's property (F) and the finitude of Galois and flat cohomology of algebraic groups over fields,
Ars Mathematica Contemporanea, v. 26 (2026), No. 3
.
Tan H. Cao,
Boris S. Mordukhovich,
Dao Nguyen,
Trang Nguyen,
Nguyễn Năng Thiều,
Optimal control of nonconvex sweeping processes with variable time via finite-difference approximations,
Nonlinear Analysis: Hybrid Systems Volume 61, August 2026, 101755
.