8-Facebook Interactions

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

By: johndel (110 month(s) ago)

really nice analysis

By: ravi.datti (110 month(s) ago)

Great PPT

Presentation Transcript

PowerPoint Presentation:

University of California at Santa Barbara Christo Wilson , Bryce Boe, Alessandra Sala, Krishna P. N. Puttaswamy, and Ben Zhao User Interactions in Social Networks and their Implications

Social Networks:

Social Networks

Social Applications:

Social Applications Enables new ways to solve problems for distributed systems Social web search Social bookmarking Social marketplaces Collaborative spam filtering (RE: Reliable Email) How popular are social applications? Facebook Platform – 50,000 applications Popular ones have >10 million users each

Social Graphs and User Interactions:

Social Graphs and User Interactions Social applications rely on Social graph topology User interactions Currently, social applications evaluated just using social graph Assume all social links are equally important/interactive Is this true in reality? Milgram’s familiar stranger Connections for ‘status’ rather than ‘friendship’ Incorrect assumptions lead to faulty application design and evaluation

Goals:

Goals Question: Are social links valid indicators of real user interaction? First large scale study of Facebook 10 million users (15% of total users) / 24 million interactions Use data to show highly skewed distribution of interactions <1% of people on Facebook talk to >50% of their friends Propose new model for social graphs that includes interaction information Interaction Graph Reevaluate existing social application using new model In some cases, break entirely

Outline:

Characterizing Facebook Analyzing User Interactions Interaction Graphs Effects on Social Applications Outline

Crawling Facebook for Data:

Crawling Facebook for Data Facebook is the most popular social network Crawling social networks is difficult Too large to crawl completely, must be sampled Privacy settings may prevent crawling Thankfully, Facebook is divided into ‘networks’ Represent geographic regions, schools, companies Regional networks are not authenticated

Crawling for Data, cont.:

Crawling for Data, cont. Crawled Facebook regional networks 22 largest networks: London, Australia, New York, etc Timeframe: March – May 2008 Start with 50 random ‘seed’ users, perform BFS search Data recorded for each user: Friends list History of wall posts and photo comments Collectively referred to as interactions Most popular publicly accessible Facebook applications

High Level Graph Statistics:

Facebook Orkut 1 Number of Users Crawled 10,697,000 1,846,000  Percentage of Total Users 15% 26.9% Number of Social Links Crawled 408,265,000 22,613,000 Radius 9.8 6 Diameter 13.4 9 Average Path Length 4.8 4.25 Clustering Coefficient 0.164 0.171 Power-law Coefficient α = 1.5, D = 0.55 α = 1.5, D = 0.6 High Level Graph Statistics 1. A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Measurement and analysis of online social networks. In Proc. of IMC, October 2007. Based on Facebook’s total size of 66 million users in early 2008 Represents ~50% of all users in the crawled regions ~49% of links were crawlable This provides a lower bound on the average number of in-network friends Avg. social degree = ~77 Low average path length and high clustering coefficient indicate Facebook is small-world

Outline:

Characterizing Facebook Analyzing User Interactions Interaction Graphs Effects on Social Applications Outline

Analyzing User Interactions:

Analyzing User Interactions Having established that Facebook has the expected social graph properties… Question: Are social links valid indicators of real user interaction? Examine distribution of interactions among friends

Distribution Among Friends:

Distribution Among Friends For 50% of users, 70% of interaction comes from 7% of friends. Almost nobody interacts with more than 50% of their friends! For 50% of users, 100% of interaction comes from 20% of friends. Social degree does not accurately predict human behavior Initial Question: Are social links valid indicators of real user interaction? Answer: NO

Outline:

Characterizing Facebook Analyzing User Interactions Interaction Graphs Effects on Social Applications Outline

A Better Model of Social Graphs:

A Better Model of Social Graphs Answer to our initial question: Not all social links are created equal Implication: can not be used to evaluate social applications What is the right way to model social networks? More accurately approximate reality by taking user interactivity into account Interaction Graphs Chun et. al. IMC 2008

Interaction Graphs:

Interaction Graphs Definition: a social graph parameterized by… n : minimum number of interactions per edge t : some window of time for interactions n = 1 and t = {2004 to the present}

Social vs. Interaction Degree:

Social vs. Interaction Degree 1:1 Degree Ratio Dunbar’s Number (150) 99% of Facebook Users Interaction graph prunes useless edges Results agree with theoretical limits on human social cognition

Interaction Graph Analysis:

Interaction Graph Analysis Do Interaction Graphs maintain expected social network graph properties? Social Graph Interaction Graph Number of Vertices 10,697,000 8,403,000 Number of Edges 408,265,000 94,665,000 Radius 9.8 12.4 Diameter 13.4 19.8 Average Path Length 4.8 7.3 Clustering Coefficient 0.164 0.078 Power-law Coefficient α = 1.5, D = 0.55 α = 1.5, D = 0.24 Interaction Graphs still have Power-law scaling Scale-free behavior Small-world clustering … But, exhibit less of these characteristics than the full social network

Outline:

Characterizing Facebook Analyzing User Interactions Interaction Graphs Effects on Social Applications Outline

Social Applications, Revisited:

Social Applications, Revisited Recap: Need a better model to evaluate social applications Interaction Graphs augment social graphs with interaction information How do these changes effect social applications? Sybilguard Analysis of Reliable Email in the paper

Sybilguard:

Sybilguard Sybilguard is a system for detecting Sybil nodes in social graphs Why do we care about detecting Sybils? Social network based games: Social marketplaces: How Sybilguard works Key insight: few edges between Sybils and legitimate users (attack edges) Use persistent routing tables and random walks to detect attack edges

Sybilguard Algorithm:

Sybilguard Algorithm Step 1: Bootstrap the network. All users exchange signed keys. Key exchange implies that both parties are human and trustworthy. Step 2: Choose a verifier (A) and a suspect (B). A and B send out random walks of a certain length (2). Look for intersections. A knows B is not a Sybil because multiple paths intersect and they do so at different nodes. A B

Sybilguard Algorithm, cont.:

Sybilguard Algorithm, cont. A B

Sybilguard Caveats:

Sybilguard Caveats Bootstrapping requires human interaction Evaluating Sybilguard on the social graph is overly optimistic because most friends never interact! Better to evaluate using Interaction Graphs

Expected Impact:

Expected Impact Fewer of edges, lower clustering lead to reduced performance Why? Self-loops A B

Sybilguard on Interaction Graphs:

Sybilguard on Interaction Graphs When evaluated under real world conditions, performance of social applications changes dramatically

Social Networks:

Social Networks Social Networks are popular platforms for interaction, communication and collaboration > more than 110 million users > more than 170 million users > more than 800 thousand users

Conclusion:

Conclusion First large scale analysis of Facebook Answer the question: Are social links valid indicators of real user interaction? Formulate new model of social networks: Interaction Graphs Demonstrate the effect of Interaction Graphs on social applications Final takeaway: when building social applications, use interaction graphs!

Questions?:

Anonymized Facebook data (social graphs and interaction graphs) will be available for download soon at the Current Lab website! http://current.cs.ucsb.edu/facebook Questions?

High Level Graph Statistics:

Facebook Orkut 1 Number of Users Crawled 10,697,000 1,846,000  Percentage of Total Users 15% 26.9% Number of Social Links Crawled 408,265,000 22,613,000 Radius 9.8 6 Diameter 13.4 9 Average Path Length 4.8 4.25 Clustering Coefficient 0.164 0.171 Power-law Coefficient α = 1.5, D = 0.55 α = 1.5, D = 0.6 High Level Graph Statistics Based on Facebook’s total size of 66 million users in early 2008 Represents ~50% of all users in the crawled regions ~49% of links were crawlable This provides a lower bound on the average number of in-network friends Avg. social degree = ~77 Clustering Coefficient measures strength of local cliques Measured between zero (random graphs) and one (complete connectivity) Social networks display power law degree distribution Alpha is the curve of the power law D is the fitting error

Social Degree CDF:

Social Degree CDF

Nodes vs. Total Interactions:

Nodes vs. Total Interactions Top 10% of most well connected users are responsible for 60% of total interactions Top 10% of most interactive users are responsible for 85% of total interactions Social degree does not accurately predict human behavior Interactions are highly skewed towards a small percent of the Facebook population

authorStream Live Help