A0259
Title: Node role discovery in networks: Approximating equitable partitions
Authors: Michael Scholkemper - RWTH Aachen Univeristy (Germany)
Michael Schaub - RWTH Aachen University (Germany)
Michael Schaub - RWTH Aachen University (Germany) [presenting]
Abstract: Similar to community detection, partitioning the nodes of a network according to their structural roles aims to identify the fundamental building blocks of a network. The found partitions can be used, e.g., to simplify descriptions of the network connectivity, to derive reduced order models for dynamical processes unfolding on processes, or as ingredients for various graph mining tasks. A fresh look is offered at the problem of role extraction and its differences from community detection, and a definition of node roles related to graph-isomorphism tests, the Weisfeiler-Leman algorithm, and equitable partitions is presented. Two associated optimization problems (cost functions) are studied, grounded in ideas from graph isomorphism testing, and present theoretical guarantees associated with the solutions of these problems. Finally, the approach is validated via a novel "role-infused partition benchmark", a network model from which we can sample networks in which nodes are endowed with different roles in a stochastic way.
