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
15/07/26, Hội nghị, hội thảo:
Hình học tôpô và các chủ đề liên quan
13/10/26, Hội nghị, hội thảo:
International Workshop on Optimization, Variational Analysis, and Control Theory
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
Đinh Nho Hào,
Maxim Shishlenin,
Van Ba Cong,
Stable Numerical Solution to Multi-dimensional Nonlinear Inverse Heat Conduction Problems via Artificial Neural Networks,
Lobachevskii Journal of Mathematics, Volume 47, pages 1213–1232 (2026)
Nguyễn Trung Thành,
Gianluca Barone,
Dat Tran,
Đinh Nho Hào,
All-at-once proximal alternating minimization method for an inverse medium scattering problem,
Journal of Computational Physics, Article: 115187 Volume: Volume 565 (2026)
Yongdo Lim,
Hoàng Ngọc Tuấn,
Nguyễn Đông Yên,
DC algorithms in Hilbert spaces and the solution of indefinite infinite-dimensional quadratic programs,
Journal of Global Optimization, Volume 95, pages 193–209 (2026)