Networks Seminar

We propose the first return time distribution (FRTD) of a random walk as an interpretable and mathematically grounded node embedding. The FRTD assigns a probability mass function to each node, allowing us to define a distance between any pair of nodes using standard metrics for discrete distributions. We present several arguments to motivate the FRTD embedding. First, we show that FRTDs are strictly more informative than eigenvalue spectra, yet insufficient for complete graph identification, thus placing FRTD equivalence between cospectrality and isomorphism. Second, we argue that FRTD equivalence between nodes captures structural similarity. Third, we empirically demonstrate that the FRTD embedding outperforms manually designed graph metrics in network alignment tasks. Finally, we show that random networks that approximately match the FRTD of a desired target also preserve other salient features. Together these results demonstrate the FRTD as a simple and mathematically principled embedding for complex networks.

Many complex systems have both cooperative and antagonistic interactions. For example, countries form alliances and wage wars, financial assets move together or in opposite directions, genes activate or inhibit each other, and users of online platforms endorse or reject each other. We can represent these systems as signed networks, in which each edge has a positive or a negative sign. However, most tools of network science assume non-negative weights. The common practices of discarding negative edges, taking absolute values, or treating signs as ordinary weights can thus lead to wrong or incomplete conclusions. In this talk, we first review where signed networks appear and which problems arise when we apply standard methods to them. Then we discuss three types of analysis that account for signs explicitly: measuring structural balance at different scales, detecting mesoscale structure, and constructing network embeddings. Throughout, we illustrate how incorporating the signs into the analysis reveals structural properties that conventional approaches can overlook.