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
23/03/26, Hội nghị, hội thảo:
HỌC KỲ CHUYÊN ĐỀ: ĐỒ THỊ VÀ CÁC HƯỚNG NGHIÊN CỨU MỞ RỘNG
Xuất bản mới
Nguyễn Huyền Mười,
Vũ Ngọc Phát,
New design of robust $H_\infty$ controllers for descriptor discrete time-varying delay equations with bounded disturbances,
Transactions of the Institute of Measurement and Control, 48(2026), 87-97
(SCI(-E); Scopus)
.
Lê Xuân Thanh,
Lê Dũng Mưu,
Nguyễn Văn Quý,
A Dual Approach Based Extragradient-Type Method for Solving Quasi-Equilibrium Problems,
Journal of Optimization Theory and Applications, Volume 208, article number 59, (2026)
.
Vũ Thị Hướng,
Ida Litzel,
Thorsten Koch,
Similarity-based fuzzy clustering scientific articles: Potentials and challenges from mathematical and computational perspectives,
Journal of Nonlinear and Variational Analysis 10, 381-401 (2026).
(SCI-E, Scopus)
.