Uncovering Several Useful Structures of Complex Networks in Computer Science Applications

Graph theory originated in the 18th century when Euler worked on the Königsberg bridge problem. Since then, graph theory has been applied to many fields, ranging from biological networks to transportation networks. In this paper, we study complex networks and their applications in computer science, with a focus on computer system and network applications, including mobile and wireless networks. In a social society, many group activities can be represented as a complex network in which entities (vertices) are connected in pairs by lines (edges). Uncovering useful global structures of complex networks is important for understanding system behaviors and providing global guidance for application designs. We briefly review existing graph models, discuss several mechanisms used in traditional graph theory, distributed computing, and system communities, and point out their limitations. Throughout the paper, we focus on how to uncover useful structures in dynamic networks and summarize three promising approaches to uncover useful structures: trimming, layering, and remapping. We then study several distributed and local labeling and coding methods as a way of learning and their relationships to machine learning (ML), including graph neural networks (GNNs). Finally, we present challenges in algorithmic techniques, with a focus on distributed and localized ones, in labeling and coding in a dynamic network.