User Interactions in Social Networks: Implications & Study Findings
Explore the implications of user interactions in social networks through a study conducted at the University of California, Santa Barbara. Discover the skewed distribution of interactions on platforms like Facebook, leading to the proposal of a new model for evaluating social links and user engagements. Gain insights into the importance of considering interaction data in social application design and evaluation.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
User Interactions in Social Networks and their Implications University of California at Santa Barbara Christo Wilson, Bryce Boe, Alessandra Sala, Krishna P. N. Puttaswamy, and Ben Zhao
Social Networks 2 University of California at Santa Barbara 4/2/2009
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 3 University of California at Santa Barbara 4/2/2009
Social Graphs and User Interactions Social applications rely on 1. Social graph topology 2. 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 4 University of California at Santa Barbara 4/2/2009
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 5 University of California at Santa Barbara 4/2/2009
Outline Characterizing Facebook Analyzing User Interactions Interaction Graphs Effects on Social Applications 6 University of California at Santa Barbara 4/2/2009
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 7 University of California at Santa Barbara 4/2/2009
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 8 University of California at Santa Barbara 4/2/2009
High Level Graph Statistics Low average ~49% of links were crawlable path length and high clustering coefficient indicate Facebook is small-world Based on Facebook s total size of 66 million users in early 2008 lower bound on the average number of in- network friends Facebook Orkut1 1,846,000 Number of Users Crawled Percentage of Total Users 10,697,000 15% 26.9% This provides a Number of Social Links Crawled 408,265,000 22,613,000 Radius 9.8 6 Represents ~50% of all users in the crawled regions Avg. social degree = ~77 Diameter 13.4 9 Average Path Length 4.8 4.25 Clustering Coefficient 0.164 0.171 =1.5, D=0.55 =1.5, D=0.6 Power-law Coefficient 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. 9 University of California at Santa Barbara 4/2/2009
Outline Characterizing Facebook Analyzing User Interactions Interaction Graphs Effects on Social Applications 10 University of California at Santa Barbara 4/2/2009
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 11 University of California at Santa Barbara 4/2/2009
Distribution Among Friends 100 90 Almost nobody interacts with more than 50% of their friends! Social degree does not accurately predict human behavior Initial Question: Are social links valid indicators of real user interaction? Answer: NO 80 % of Users (CDF) 70 For 50% of users, 100% of interaction comes from 20% of friends. 60 50 For 50% of users, 70% of interaction comes from 7% of friends. 40 30 70% Interaction Cumulative Fraction 90% Interaction Cumulative Fraction 100% Interaction Cumulative Fraction 20 10 0 0 10 20 30 40 50 % of Friends Involved University of California at Santa Barbara 12 4/2/2009
Outline Characterizing Facebook Analyzing User Interactions Interaction Graphs Effects on Social Applications 13 University of California at Santa Barbara 4/2/2009
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 14 University of California at Santa Barbara 4/2/2009
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} 15 University of California at Santa Barbara 4/2/2009
Social vs. Interaction Degree 500 450 400 1:1 Degree Ratio Interaction Degree 350 Interaction graph prunes useless edges Results agree with theoretical limits on human social cognition 300 99% of Facebook Users 250 200 150 100 Dunbar s Number (150) 50 0 0 500 1000 1500 Social Degree 16 University of California at Santa Barbara 4/2/2009
Interaction Graph Analysis Do Interaction Graphs maintain expected social network graph properties? Power-law scaling Scale-free behavior Small-world clustering But, exhibit less of these characteristics than the full social network Interaction Graphs still have 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 =1.5, D=0.55 =1.5, D=0.24 Power-law Coefficient 17 University of California at Santa Barbara 4/2/2009
Outline Characterizing Facebook Analyzing User Interactions Interaction Graphs Effects on Social Applications 18 University of California at Santa Barbara 4/2/2009
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 19 University of California at Santa Barbara 4/2/2009
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 20 University of California at Santa Barbara 4/2/2009
Sybilguard Algorithm B Step 1: Step 2: Bootstrap the network. Choose a verifier (A) and a suspect (B). All users exchange signed keys. A and B send out random walks of a certain length (2). Key exchange implies that both parties are human and trustworthy. Look for intersections. A knows B is not a Sybil because multiple paths intersect and they do so at different nodes. A 21 University of California at Santa Barbara 4/2/2009
Sybilguard Algorithm, cont. A B 22 University of California at Santa Barbara 4/2/2009
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 23 University of California at Santa Barbara 4/2/2009
Expected Impact B Fewer of edges, lower clustering lead to reduced performance Why? Self-loops A 24 University of California at Santa Barbara 4/2/2009
Sybilguard on Interaction Graphs 100 % of Intersections (CDF) 90 80 70 When evaluated under real world conditions, performance of social applications changes dramatically 60 Social Graph Full Interaction Graph Interaction Graph (1 Year) Interaction Graph (6 Months) Interaction Graph (2 Months) 50 40 30 20 10 0 0 500 Random Walk Path Length 1000 1500 25 University of California at Santa Barbara 4/2/2009
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! 26 University of California at Santa Barbara 4/2/2009
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 27 University of California at Santa Barbara 4/2/2009
Social Networks Social Networks are popular platforms for interaction, communication and collaboration > 110 million users 9th most trafficked site on the Internet > 170 million users #1 photo sharing site 4th most trafficked site on the Internet 114% user growth in 2008 > 800 thousand users 1,689% user growth in 2008 28 University of California at Santa Barbara 4/2/2009
High Level Graph Statistics Clustering Social networks display power law degree ~49% of links were crawlable Coefficient measures strength of local cliques distribution Based on Facebook s total size of 66 million users in early 2008 lower bound on the average number of in- network friends (random graphs) and one (complete connectivity) D is the fitting error Facebook Orkut1 1,846,000 Number of Users Crawled Percentage of Total Users 10,697,000 15% 26.9% This provides a Number of Social Links Crawled 408,265,000 22,613,000 Measured between zero curve of the power law Alpha is the Radius 9.8 6 Represents ~50% of all users in the crawled regions Avg. social degree = ~77 Diameter 13.4 9 Average Path Length 4.8 4.25 Clustering Coefficient 0.164 0.171 =1.5, D=0.55 =1.5, D=0.6 Power-law Coefficient 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. 29 University of California at Santa Barbara 4/2/2009
Social Degree CDF 100 90 80 % of Users (CDF) 70 60 50 YouTube LiveJournal Facebook Orkut 40 30 20 10 0 1 10 100 1000 Social Degree 30 University of California at Santa Barbara 4/2/2009
Nodes vs. Total Interactions 100 90 % of Total Interaction (CDF) Top 10% of most interactive users are responsible for 85% of total interactions 80 Social degree does not accurately predict human behavior Interactions are highly skewed towards a small percent of the Facebook population 70 60 Top 10% of most well connected users are responsible for 60% of total interactions 50 40 30 Sorted by Degree 20 Sorted by Total Interactions 10 0 0 10 20 30 40 50 60 % of Nodes 31 University of California at Santa Barbara 4/2/2009
