Evolution of Social-Attribute Networks: Measurements, Modeling, and Implications using Google+

Neil Zhenqiang Gong; Wenchang Xu; Ling Huang; Prateek Mittal; Emil Stefanov; Vyas Sekar; Dawn Song

Source-linked AI summary

Evolution of Social-Attribute Networks: Measurements, Modeling, and Implications using Google+

Neil Zhenqiang Gong, Wenchang Xu, Ling Huang, Prateek Mittal, Emil Stefanov, Vyas Sekar, Dawn Song

arXiv:1209.0835v4Sep 5, 2012cs.SIcs.CYphysics.soc-ph

TL;DR

The paper addresses the lack of systematic, large-scale evidence on how social networks and user attributes jointly evolve. It analyzes Google+ snapshots and user profiles, then develops and evaluates a generative model for social-attribute networks. The model reproduces Google+ SAN structure across network metrics and performs better than the comparison model in Sybil defense and anonymous communication applications.

Problem
Few studies systematically measure and model the evolution of social-attribute networks, while prior work largely focuses on social structure despite attributes informing both network and attribute properties.
Method
The paper crawls Google+ over time, measures social and attribute structure, and develops a generative SAN model with attribute-augmented preferential attachment and triangle-closing.
Results
The model accurately reproduces Google+ SANs across degree distributions, joint degree distributions, and clustering coefficients, and outperforms the Zhel model in Sybil defense and anonymous communication.
Takeaways & Limitations
The findings show that social-attribute models capture network evolution and application behavior more accurately than models focused on social structure alone.
Takeaways & Limitations
The model focuses on static attributes selected when nodes join and leaves dynamic attributes for future work.

Abstract

from arXiv · show

Understanding social network structure and evolution has important implications for many aspects of network and system design including provisioning, bootstrapping trust and reputation systems via social networks, and defenses against Sybil attacks. Several recent results suggest that augmenting the social network structure with user attributes (e.g., location, employer, communities of interest) can provide a more fine-grained understanding of social networks. However, there have been few studies to provide a systematic understanding of these effects at scale. We bridge this gap using a unique dataset collected as the Google+ social network grew over time since its release in late June 2011. We observe novel phenomena with respect to both standard social network metrics and new attribute-related metrics (that we define). We also observe interesting evolutionary patterns as Google+ went from a bootstrap phase to a steady invitation-only stage before a public release. Based on our empirical observations, we develop a new generative model to jointly reproduce the social structure and the node attributes. Using theoretical analysis and empirical evaluations, we show that our model can accurately reproduce the social and attribute structure of real social networks. We also demonstrate that our model provides more accurate predictions for practical application contexts.

1. INTRODUCTION

The paper studies how social networks and user attributes jointly evolve, addressing the limited systematic measurement and modeling of social-attribute networks at scale. Using Google+ observations, it reports distinctive network patterns and develops a generative model that reproduces social and attribute structure.

Motivation: Social-attribute networks augment user-to-user topology with static or dynamic attributes such as employers, schools, cities, interests, and communities.This broader representation supports analysis of both attribute structure and its effects on social structure.
Research gap: Few prior studies systematically measure and model social-attribute network evolution, with most measurement and modeling work focusing primarily on social structure.The paper positions its study as addressing this gap at scale.
Approach: The study uses a large-scale Google+ crawl that observed the network’s complete evolution to around 30 million users within three months.The dataset includes both social-network structure and user profiles.
Findings: Google+ exhibits low reciprocity, lognormal rather than power-law social degree distributions, and nearly neutral assortativity rather than the positive assortativity common in many traditional networks.These observations distinguish Google+ from several traditional social networks and motivate new modeling choices.
Findings: The paper finds that Google+’s launch, invitation-only, and public-release phases manifest in both social and attribute structures.It also reports that some attribute metrics mirror social counterparts while others have significantly different distributions and trends.
Model: The proposed SAN generative model adds attribute-augmented preferential attachment and triangle-closing to reproduce real social-attribute networks.The model is evaluated through theoretical analysis and empirical comparisons across network metrics and applications.

2. PRELIMINARIES AND DATASET

The paper defines a Social-Attribute Network by combining directed user relationships with undirected links to attribute nodes, then constructs 79 Google+ snapshots from crawled profiles and social structure. The dataset covers distinct growth phases, reaches at least 70% estimated user coverage, and has acknowledged privacy and disclosure biases.

2.1 Social-Attribute Network (SAN): A Social-Attribute Network adds one attribute node for each distinct binary attribute and connects users to their attributes with undirected links.Social links between users remain directed, and the SAN is represented as SAN = (V_s, V_a, E_s, E_a).
2.1 Social-Attribute Network (SAN): SANs distinguish social nodes and attribute nodes, with social, attribute, social-in, and social-out neighborhoods defined separately.Attribute nodes have only social neighbors.
2.2 Google+ Data: The Google+ crawl collected daily public snapshots from July 6 to October 11, 2011, following the platform’s June 28 launch and September 20 public opening.The first snapshot used breadth-first search; subsequent crawls expanded from the previous snapshot.
2.2 Google+ Data: The crawled component covers at least 70% of known users according to comparisons with external estimates of 10 million and 40 million users.The crawl could access both incoming and outgoing links, enabling coverage of a large weakly connected component.
2.2 Google+ Data: The dataset constructs each SAN from users, incoming and outgoing friendships, and four profile attribute types: School, Major, Employer, and City.This process produced 79 SAN snapshots.
2.2 Google+ Data: Google+ growth separates into three phases: dramatic early growth, stabilized invitation-only growth, and renewed dramatic growth after public release.Similar three-phase patterns appear in almost all subsequently analyzed network metrics.
2.2 Google+ Data: Potential biases include private friendship lists, which may underestimate degrees, and undeclared attributes, which may underestimate attribute effects.The authors report that roughly 22% of users declare at least one attribute and that further subsampling supports attribute representativeness.

3. SOCIAL STRUCTURE OF THE GOOGLE+ SAN

The Google+ SAN exhibits distinctive three-phase evolution across core social metrics, with degree distributions and degree correlations differing from patterns commonly reported for traditional networks. These observations characterize Google+ as a hybrid social and publisher-subscriber network whose structure becomes increasingly publisher-subscriber-like.

Reciprocity: Google+ reciprocity fluctuates in Phase I, decreases in Phase II, and decreases faster in Phase III, consistent with growing publisher-subscriber behavior.The paper compares Google+'s reciprocity with 0.62 on Flickr, 0.79 on YouTube, and 0.22 on Twitter.
Density: Google+ social density sharply decreases then increases in Phase I, rises in Phase II, and drops suddenly at public release before increasing steadily.The authors relate these changes to differing rates of user joining and link creation.
Diameter: 90% of connected node pairs have distances of 5, 6, or 7, with the distance distribution dominated by mode six.Effective diameter follows a three-phase evolution rather than the shrinking pattern reported for several other networks.
Clustering Coefficient: Average clustering decreases dramatically in Phase I, increases slowly in Phase II, and decreases again in Phase III.The metric captures community structure among a user's friends, and its evolution differs from the constant trend observed in an email network.
Degree Distributions: Social indegree and outdegree are best modeled by discrete lognormal distributions rather than the power-law distributions often reported for social networks.The fitted indegree and outdegree distributions follow similar trends, with fluctuations differing in magnitude; lognormal degrees imply probabilistically more low-degree nodes.
Joint Degree Distribution: Google+ assortativity approaches neutrality, unlike the positive coefficients reported for Flickr, LiveJournal, and Orkut, and evolves from positive to near zero to negative across phases.The paper interprets this pattern as consistent with a hybrid of traditional social-network and publisher-subscriber interactions.

4. ATTRIBUTE STRUCTURE OF THE GOOGLE+ SAN

The Google+ SAN’s attribute structure evolves across launch phases and differs from ordinary social structure in several metrics. Attribute information also correlates with social-network behavior, including reciprocity and community formation.

Attribute density: Attribute density rises rapidly in Phase I, remains relatively flat in Phase II, and slightly decreases in Phase III.The Phase III decrease is attributed to many new users joining with new attribute nodes having small social degrees.
Clustering coefficient: Attribute clustering evolves differently from its social counterpart and remains relatively stable during Phase II.Attribute clustering measures an attribute’s power to form communities among users sharing it.
Clustering coefficient: Attribute clustering coefficients follow a power-law distribution with respect to node degree, have a larger exponent than social clustering, and are generally lower.Shared attributes such as city or major do not necessarily translate into social relationships.
Degree distributions: Attribute degree of social nodes is best modeled by a lognormal distribution, whereas social degree of attribute nodes is best modeled by a power-law distribution.The fitted distribution parameters evolve over time; attribute-degree means decrease in Phases I and III but remain roughly constant in Phase II.
Influence on social structure: Reciprocity is almost twice as high for nodes sharing common attribute neighbors, regardless of the number of common social neighbors.The authors report diminishing reciprocity gains beyond 10 common social neighbors and recommend incorporating attributes into reciprocity predictors.
Influence on social structure: Employer, School, Major, and City attributes vary in their influence on community formation, while Employer=Google and Major=Computer Science users tend to have higher degrees.The observed attribute effects motivate using attributes to understand social structure and guide SAN modeling.
Validation via subsampling: Under a random, independent attribute-disclosure assumption, the attribute clustering distributions of the original and subsampled SANs are almost identical.This supports treating the attributes collected from 22% of users as representative of all users.

5. A GENERATIVE MODEL FOR SAN

The paper develops a generative model for SANs because prior models primarily reproduce social structure without modeling attributes or their impact. It augments preferential attachment and triangle-closing with attribute information, and evaluates the resulting model against Google+ data.

Motivation: The generative-model goal is to reproduce both the social and attribute structures observed in Google+ SANs.The model is intended to support understanding SAN growth and applications such as network extrapolation and sampling.
Motivation: Prior generative models primarily model social structure and do not capture attribute structure or its impact on social structure.The proposed approach incorporates attributes from first principles rather than overlaying them afterward.
Model design: The model extends preferential attachment and triangle-closing through attribute-augmented mechanisms for link generation and node addition.These components are designed to produce synthetic SANs that closely match the Google+ SAN.
Attribute-augmented preferential attachment: PAPA uses f(u, v) ∝ d_i(v)^α(1 + a(u, v)^β), while LAPA uses f(u, v) ∝ d_i(v)^α(1 + β · a(u, v)).Here d_i(v) is v’s indegree and a(u, v) is the number of attributes shared by social nodes u and v.
Model evaluation: 6.1% further improvement over the PA model is achieved by LAPA with α =1 and β = 200, while the PA model is 7.9% better than uniform random.LAPA outperforms PAPA, and α = 1 gives the best loglikelihood for each β, indicating linear effects of attributes and social degree.
Model evaluation: The model is evaluated using theoretical analysis and empirical evaluation to test whether it accurately reproduces real SAN structure.The reported summary describes a combined linear effect of social degree and attributes.

Attribute-Augmented Triangle-Closings

The paper incorporates user attributes into triangle-closing and develops a SAN evolution model combining attribute-augmented preferential attachment with attribute-augmented triangle-closing. Theoretical analysis shows the model produces lognormal social outdegrees and power-law attribute-node social degrees.

Triangle-closing types: 84% of observed Google+ friend requests are triadic closures, while 18% are focal closures involving a common attribute.The reported categories overlap because some requests belong to both closure types.
Attribute-augmented closure: RR improves triangle-closing prediction by 14% over Baseline, while RR-SAN improves it by 36% over RR.The comparison includes triadic closures, focal closures, or both.
Generative model: The model combines Linear Attribute Preferential Attachment (LAPA) with Random-Random-SAN (RR-SAN) triangle-closing.LAPA models attribute effects in preferential attachment, while RR-SAN incorporates attributes into triangle-closing.
Generative process: The model generates nodes that select attributes and social neighbors, then wake after sampled sleep times to add links through RR-SAN.The initial network uses a small complete SAN; simulations model one node arrival per discrete time step.
Theoretical analysis: Theorem 1 states that social outdegrees follow a lognormal distribution when sleep time has mean m_s/d_o.The stated lognormal mean is (µ_l + σ_lg(γ_l))/m_s.
Theoretical analysis: Theorem 2 states that social degrees of attribute nodes follow a power-law distribution with exponent 2−p.The derivation uses mean-field rate equations and assumes attribute-node arrival times are uniformly distributed.

6. EVALUATION

The evaluation compares the proposed SAN model with the Zhel model using a large Google+ snapshot and network-application fidelity tests. The proposed model more closely reproduces Google+ metrics and performs better in Sybil defense and anonymous communication contexts.

Experimental setup: The evaluation uses a Google+ snapshot with roughly 10 million nodes and guided greedy search to fit parameters for both models.The snapshot was crawled on July 15, 2011.
Degree distributions: The proposed model generates synthetic SANs whose social indegree and outdegree follow Google+-like lognormal distributions, unlike Zhel’s power-law distributions.Both models produce power-law social degrees for attribute nodes, matching the Google+ pattern.
Joint degree distributions: The proposed model matches Google+ joint degree distributions more closely than Zhel, including for attribute and social nodes.Joint degree distributions are evaluated using the degree correlation function k_nn.
Clustering coefficients: The proposed model reproduces both social and attribute clustering-coefficient distributions well, whereas Zhel does not.RR-SAN significantly affects the attribute clustering coefficient through focal closure.
Building blocks: LAPA changes the synthetic social indegree from a power-law-like distribution under classical PA to a lognormal distribution in the full model.Other evaluated metrics are qualitatively similar between the intermediate and full models, except social indegree.
Application fidelity: At 200,000 compromised nodes, Google+ yields about 25.3 million Sybil identities, while the model predicts 24.5 million with 3.1% error.The proposed model’s prediction is a close match and outperforms the Zhel baseline.
Application fidelity: The proposed model more accurately reproduces application outcomes than Zhel for Sybil defense and anonymous communication.Anonymous-communication evaluation measures end-to-end timing-analysis probability as a function of compromised nodes.

7. DISCUSSION

The discussion connects attribute-aware modeling to defenses, recommendation systems, and heterogeneous-network research while identifying computational, attribute-dynamics, inference, and parsimony boundaries.

Implications for defenses: Attribute structure may strengthen attack defenses by checking whether nodes resemble normal attribute patterns or limiting compromised-edge influence.The paper presents this as a hypothesis for defenses such as Sybil proofing.
Limitations: LAPA requires a costly linear-time step in the number of nodes when a new node arrives.A heuristic can approximate LAPA by selecting one new-node attribute and applying PA among nodes having that attribute.
Limitations: The model focuses on static attributes and leaves dynamic attributes for future work.In the proposed model static attributes influence social structure, unlike the compared model’s direction of influence.
Limitations: Model parameters are currently estimated with guided greedy search rather than a more rigorous maximum-likelihood procedure.The authors identify maximum-likelihood inference as future work.
Limitations: The authors identify designing a more parsimonious model as future work after showing that each current component is necessary.This leaves model simplicity as an explicit open issue.
Implications for social-network design: Users sharing an employer are more likely to be linked than users sharing other attributes, informing friend-recommendation design.The discussion frames friend recommendation as a fundamental online-social-network component.
Heterogeneous networks: The SAN framework could be generalized to other heterogeneous networks used for link prediction, attribute inference, and community detection.The paper identifies this generalization as future work.

8. RELATED WORK

The paper positions itself as a first large-scale evolutionary study of Google+ SANs and as a model extending prior social-network and SAN-generation work. Its distinctive focus is how static attributes influence social-structure formation.

Positioning: The paper’s contributions are characterizing Google+ evolution and developing measurement-driven models of attribute effects on social structure.The work is framed within the broader literature on measuring and modeling social networks.
Measuring social networks: Most prior social-network measurement studies analyze static snapshots, while this work examines evolutionary behavior using Google+ snapshots.The related work notes only a few prior studies with comparable evolutionary focus.
Measuring social networks: Prior Google+ studies examined early growth, geographic and public-information patterns, cross-platform differences, adoption, and privacy concerns.These studies provide related Google+ characterization but not the same SAN focus described here.
Social-attribute networks: Earlier attribute-focused studies emphasized social structure influencing dynamic attributes, whereas this paper models static attributes influencing social-structure formation.The paper describes these as orthogonal analytical directions.
Modeling social networks: The dynamic model extends prior network-generation work by provably producing a lognormal social-outdegree distribution while capturing social and attribute structure.This distinguishes it from models focused only on generating social topology.
Modeling social-attribute networks: Compared with Zheleva et al., the paper models static rather than dynamic attributes and targets directed rather than undirected social networks.The related SAN literature contains relatively few joint social-and-attribute generation models.

9. CONCLUSION

Using a Google+ dataset, the paper characterizes social-attribute structure and evolution, introduces attribute metrics, and proposes and validates a generative SAN model.

The study uses Google+ crawl data to examine attribute structure, its impact on social structure, and their evolution.The dataset was collected since Google+ launched in June 2011.
Social degree distributions are lognormal, assortativity is neutral, and distinct evolutionary phases appear in Google+ network structure.These observations differ from patterns reported for many other social networks.
The paper defines new metrics for characterizing attribute structure and finds that attributes can significantly impact social structure.
A new generative model for social-attribute networks is validated against real Google+ data using network metrics and application contexts.The validation evaluates both structural similarity and practical application contexts.

A. A CONSTANT TIME ALGORITHM FOR APPROXIMATING CLUSTERING COEFFICIENTS

The paper defines clustering over sampled triples in social-attribute networks and uses a constant-time sampling algorithm to approximate average clustering coefficients with a probabilistic error bound.

Definitions: A triple consists of a center node and two endpoints selected from the center's social neighbors.The center is u, while v and w are the endpoints.
Algorithm: Algorithm 2 takes a SAN, a node set Ω, and sample count K, then outputs an approximate average clustering coefficient ˜CΩ.The node set Ω determines which nodes' average clustering coefficient is approximated.
Algorithm: The algorithm samples endpoint pairs uniformly from a center node's social neighbors and repeats this process while k < K.
Definitions: For directed SANs, F(t) records whether endpoints are disconnected, linked by one directed edge, or reciprocally linked; undirected SANs use disconnected versus connected.The indicator I distinguishes directed and undirected SANs and gives 0 ≤ F(t) ≤ 2I.
Algorithm: The algorithm computes average social or attribute clustering coefficients by setting Ω to Vs or Va, respectively.It can also compute average clustering-coefficient distributions with respect to node degrees.
Guarantee: With K = ⌈ln2ν/(2ϵ^2)⌉ samples, the approximated coefficient satisfies |˜CΩ−CΩ| ≤ ϵ with probability at least 1 − 1/ν.