Detecting roles in very large graphs

Colloquia & Seminars

Detecting roles in very large graphs
Date/Time:03 Jan 2020 15:00 Venue: S17 #04-05 SR2 Speaker: Paul Van Dooren, Catholic University of Louvain, Belgium Detecting roles in very large graphs Computing meaningful clusters of nodes is crucial to analyze very large networks, but since this is a combinatorial optimization problem, its complexity can be prohibitive. In this talk, we present a pairwise node similarity measure that allows to extract roles, i.e. group of nodes sharing similar flow patterns within a network. We then propose a low rank iterative scheme to approximate the similarity measure for very large networks and we show that our low rank similarity score successfully extracts the different roles in random graphs of Erdös-Renyi type. We then argue that when projecting our similarity measure onto a low rank manifold (say, of rank r), the role models can be recovered using classical clustering techniques in an r-dimensional space, which reduces the complexity significantly. We illustrate these ideas with a number of real world applications including coral spawning in the great barrier reef. Add to calendar: