A Study of Phase Transition in New Random Graph Families

Abstract:

Random graphs are mathematical models for understanding real-world networks. Important properties can be captured, processes studied, and rigorous predictions made. Phase transitions (sudden changes in structural properties caused by varying an underlying parameter) are commonly observed in random graphs. Our work focuses on phase transitions in three models. We study emergence of cascades and impact of community structure on phase transition in threshold-based contagion models using modular random graphs generated by configuration model and differential equation method. Using local weak analysis, we study a new graph model generated by bilateral agreement of individuals and analyze when a giant component emerges. Using the objective method and motivated by particle tracking in physics and object tracking in videos, we study detectability threshold of a hidden planted matching in a complete bipartite randomly weighted graph.

Chair: Professors Mingyan Liu and Vijay Subramanian