Mobile phones have become one of the primary tools for individuals to communicate, to access data networks, and to share information. Service providers collect data about the calls placed on their network, and these calls exhibit a large degree of variability. Providers model the structure of the relationships between network subscribers as a mobile call graph. In this paper, we apply a new measure to quantify by how much a relationship between users in a mobile call graph deviate from an average relationship. This measure is used to explore the connection between calling behaviors and the complex structure mobile call graphs take. We study a large call graph from a major service provider and learn that distant, outlier relationships play the largest role in maintaining connectivity between cellular users, and that calling features of users more strongly influence tie variation compared to social features. We also observe a rapid decay of its massively connected component as outlier ties are removed.