Social networks and spin glasses

Scott Kirkpatrick, Alex Kulakovsky, Manuel Cebrián, Alex Pentland

TL;DR

This paper analyzes a massive dataset of UK telephone call records to investigate the structure of personal communication networks. By applying techniques from statistical physics, specifically "k-shell decomposition," the authors reveal that these networks exhibit characteristics of both social and communication networks, suggesting that statistical mechanics can offer powerful insights into their formation and dynamics.

What Problem Does This Paper Address?

The paper tackles the challenge of understanding the complex structure of large-scale communication networks, specifically personal telephone networks. While previous work has explored internet infrastructure (like the AS graph) and smaller social networks, there's a need to bridge this gap with real-world, large-scale personal communication data. The authors aim to determine whether these networks are best characterized as purely social (driven by local preferences) or as communication networks (optimized for long-distance transport), or if they possess a hybrid nature. This understanding is crucial for developing predictive models of network growth and response to disruptions.

Methods

The core methodological contribution is the application of k-shell decomposition to telephone call detail records (CDRs). This technique, borrowed from graph theory, recursively prunes nodes with fewer than k neighbors to identify hierarchical structures within the network. The authors also differentiate between "work period" and "leisure time" calls, creating two distinct subnetworks to analyze. Additionally, they examine degree-degree correlations to distinguish between assortative (social) and disassortative (communication) network behaviors.

Datasets

The primary dataset used is a comprehensive collection of four weeks of UK telephone call detail records (CDRs) from August 2005. This dataset covers over 90% of mobile phones and 99% of landlines in the UK, logging over 7 billion calls from more than 100 million unique numbers. The data was anonymized by hashing numbers and aggregated into 1.503 billion distinct directed links. A smaller subset, focusing on a single metropolitan area ("PnLa"), was also analyzed.

Key Insights and Ideas

  • Hybrid Nature: Telephone networks are not purely social or communication networks; they are a superposition of communities interacting at different scales.
  • Work vs. Leisure: Separating calls into "work" and "leisure" periods reveals distinct network characteristics, suggesting different underlying drivers for communication.
  • K-Shells Reveal Hierarchy: The k-shell decomposition effectively uncovers hierarchical structures, with lower k-shells potentially representing local social connections and higher k-shells indicating more institutional or long-distance communication.
  • Spin Glass Analogy: The paper reinforces the idea that statistical mechanics, particularly analogies to spin glasses, can provide powerful tools for understanding the formation and dynamics of complex networks, including social ones.
  • Surprising Degree Correlation: The degree-degree correlation analysis yielded an unexpected "flat" curve for reciprocated links, which the authors currently lack a definitive explanation for.

Key Results

  • The k-shell analysis of the CDR data showed significantly different patterns compared to the internet's AS graph, which exhibits a more straightforward power-law behavior.
  • The "work period" network showed a steeper falloff in the tail of the k-shell distribution and largely accounted for the high-connectivity shells of the full network.
  • The "leisure period" network exhibited a flatter initial region in its k-shell distribution, suggesting a greater concentration of connections within lower k-shells (more local interactions).
  • Analysis of reciprocated links revealed that very small k-shells (local interactions) are more likely to be unreciprocated, while the fraction of reciprocated links increases with k up to a certain point, potentially indicating a shift towards more institutional or business-related communication.

Limitations and Future Work

  • Data Granularity: While the CDR data is extensive, it's anonymized, and the exact nature of the entities in the higher k-shells (e.g., government vs. commercial enterprises) remains unknown.
  • "Flat" Degree Correlation: The unexpected flat degree-degree correlation for reciprocated links requires further investigation and explanation.
  • Predictive Modeling: The authors suggest that constructing predictive models for network growth and response to disturbances will necessitate multiple submodels tailored to different community interactions and scales.
  • Spin Glass Dynamics: The paper hints at opportunities to exploit statistical mechanics for understanding network formation and dynamics, suggesting future work could delve deeper into spin glass models for this purpose.

Summary updated

Abstract

Abstract The networks formed from the links between telephones observed in a month's call detail records (CDRs) in the UK are analyzed, looking for the characteristics thought to identify a communications network or a social network. Some novel methods are employed. We find similarities to both types of network. We conclude that, just as analogies to spin glasses have proved fruitful for optimization of large-scale practical problems, there will be opportunities to exploit the statistical mechanics of the formation and dynamics of social networks in today's electronically connected world. Keywords: spin dynamicsglassorder Acknowledgements This work was initiated during SK's summer visit to the MIT Media Lab and its Human Dynamics group during 2010, and continued in summer 2011. At the Hebrew University, SK and AK have enjoyed the support of the LAWA project, an EC collaborative research project (number 258105) on “Longitudinal Analytics of Web Archive Data.” MC is supported by the National Science Foundation under Grant No. 0905645. AP is partially supported the ARL under Agreement W911NF-09-2-0053, and by AFOSR under Award Number FA9550-10-1-0122.
BibTeX
@article{kirkpatrick2011social,
  author = {Scott Kirkpatrick and Alex Kulakovsky and Manuel Cebrián and Alex Pentland},
  title = {{Social networks and spin glasses}},
  journal = {The Philosophical Magazine A Journal of Theoretical Experimental and Applied Physics},
  year = {2011},
  doi = {10.1080/14786435.2011.634858},
}
Figure