Uncovering Several Useful Structures of Complex Networks in Computer Science Applications

Graph theory originated in the 18th century when Euler worked on the Konigsberg 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 systems communities, and point out their limitations. We discuss opportunities to uncover the structural properties of several complex networks, especially in a dynamic and mobile environment, and summarize three promising approaches to uncover useful structures: trimming, layering, and remapping. Finally, we study several distributed labeling and coding methods and their relationships to machine learning (ML), in particular, graph neural networks (GNNs). We also present some challenges in algorithmic techniques, with a focus on distributed and localized solutions, to uncover and/or represent various structures.