Higher-order network information improves overlapping community detection

Wednesday, April 13, 2022 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Xinyi Wu

Affiliation

IDSS

Building and Room Number

LIDS Lounge

Abstract

Identifying communities is a central problem in network science. While many methods exist, one major challenge in community detection is the often overlapping nature of communities such that nodes belong to multiple groups simultaneously. Link-based community detection paradigm redefines communities as groups of links rather than nodes and consequently discovers overlapping communities in a natural way with higher quality. Yet existing link partitioning methods are merely developed for graph-based representations of networks, which can only model pairwise relationships. Higher-order interactions and relationships are common and crucial in many complex networks. To this end, we introduce a link partitioning method that incorporates higher-order information of networks. We model networks using simplicial complexes which can include polyadic relationships and generalize graphs from the perspective of algebraic topology. We use random walk on links of simplicial complexes defined according to higher-order Laplacians to perform the link partitioning. Under reasonable conditions, optimizing modularity of the link communities using the random walk and the well-known Louvain method is guaranteed to produce interpretable results. Furthermore, we show that the random walk allows for a spectral theory of simplicial complexes. Experimental evidence suggests that using higher-order information provides substantial improvements in discovering overlapping community structure through links.

Biography

Xinyi Wu is a second-year Ph.D. student in Social and Engineering Systems at MIT, advised by Prof. Ali Jadbabaie. Prior to MIT, she graduated from Washington University in St. Louis with a B.A. in Mathematics. Her research interests include network science and machine learning.