Topics to be covered during the paper discussion:

PART I - STRUCTURE AND EVOLUTION OF ONLINE SOCIAL NETWORK


Graph: measurement of online social network and their evolution


Empirical


Fetterly et al. A large-scale study of the evolution of web pages. WWW '03: Proceedings of the 12th international conference on World Wide Web (2003)

Kossinets and Watts. Empirical analysis of an evolving social network. Science (2006) vol. 311 (5757) pp. 88

Mislove et al. Measurement and analysis of online social networks. Proceedings of the … (2007)

Leskovec et al. Microscopic evolution of social networks. Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (2008) pp. 462-470

Mislove et al. Growth of the flickr social network. Proceedings of the first workshop on Online social networks (2008) pp. 25-30

Torkjazi et al. Hot today, gone tomorrow: On the migration of MySpace users. Proceedings of the 2nd ACM workshop on Online social networks (2009) pp. 43-48

Garg et al. Evolution of an online social aggregation network: An empirical study. Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference (2009) pp. 315-321

Kumar et al. Structure and evolution of online social networks. Link Mining: Models, Algorithms, and Applications (2010) pp. 337-357

Burt. Structural Holes versus Network Closure as Social Capital. Chapter in Social Capital: Theory and Research (2000) pp. 1-30

Analysis


Leskovec et al. Graphs over time: densification laws, shrinking diameters and possible explanations. KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining (2005)

Backstrom et al. Group formation in large social networks: membership, growth, and evolution. KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (2006)

Palla et al. Quantifying social group evolution. Nature (2007)

Zheleva et al. Co-evolution of social and affiliation networks. Proceedings of the 15th ACM … (2009)

Chierichetti et al. On compressing social networks. Proceedings of the 15th ACM SIGKDD international … (2009)

Lattanzi and Sivakumar. Affiliation networks. Proceedings of the 41st annual ACM symposium on … (2009)

Groups: clusters and communities on online social networks and their evolution


Kumar et al. Trawling the Web for emerging cyber-communities. Computer Networks (1999) vol. 31 (11-16) pp. 1481-1493

Flake et al. Efficient identification of web communities. Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining (2000) pp. 160

Girvan and Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America (2002) vol. 99 (12) pp. 7821

Flake et al. Self-organization and identification of web communities. Computer (2002) vol. 35 (3) pp. 66-70

Clauset et al. Finding community structure in very large networks. Physical Review E (2004) vol. 70 (6) pp. 066111

Newman and Girvan. Finding and evaluating community structure in networks. Physical Review E (2004) vol. 69 (2) pp. 26113

Palla et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature (2005) vol. 435 (7043) pp. 814-818

Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences (2006) vol. 103 (23) pp. 8577

Fortunato and Barthélemy. Resolution limit in community detection. Proceedings of the National Academy of Sciences (2007) vol. 104 (1) pp. 36

Leskovec et al. Statistical properties of community structure in large social and information networks. WWW '08: Proceeding of the 17th international conference on World Wide Web (2008)

Backstrom et al. Preferential behavior in online groups. Proceedings of the international conference on Web search and web data mining (2008) pp. 117-128

Zhang et al. Parallel community detection on large networks with propinquity dynamics. Proceedings of the 15th ACM SIGKDD international … (2009)

Fortunato. Community detection in graphs. Physics Reports (2010) vol. 486 (3-5) pp. 75-174

Leskovec et al. Empirical comparison of algorithms for network community detection. WWW '10: Proceedings of the 19th international conference on World wide web (2010)

User Interaction: activities of user on online social networks


Lerman and Galstyan. Analysis of social voting patterns on digg. WOSP '08: Proceedings of the first workshop on Online social networks (2008)

Cha et al. A measurement-driven analysis of information propagation in the flickr social network. Proceedings of the 18th … (2009)

Viswanath et al. On the evolution of user interaction in facebook. Proceedings of the 2nd … (2009)

Wilson et al. User interactions in social networks and their implications. EuroSys '09: Proceedings of the 4th ACM European conference on Computer systems (2009)

Bakshy et al. Social influence and the diffusion of user-created content. EC '09: Proceedings of the tenth ACM conference on Electronic commerce (2009)

Schneider et al. Understanding online social network usage from a network perspective. IMC '09: Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference (2009)

Benevenuto et al. Characterizing user behavior in online social networks. IMC '09: Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference (2009)

Valafar et al. Beyond friendship graphs: a study of user interactions in Flickr. Proceedings of the 2nd ACM workshop on Online social networks (2009) pp. 25-30

Chan and Daly…. Decomposing discussion forums and boards using user roles. AAAI Conference on Weblogs and Social … (2010)

Kumar et al. Dynamics of conversations. KDD '10: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining (2010)

Jiang et al. Understanding latent interactions in online social networks. Proc. of the ACM SIGCOMM Internet Measurement Conference (2010)

Popularity and its evolution: web, user generated content, etc.

Domingos and Richardson. Mining the network value of customers. Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (2001) pp. 57-66

Aizen et al. Traffic-based feedback on the web. Proceedings of the National Academy of Sciences of the United States of America (2004) vol. 101 (Suppl 1) pp. 5254

Cha et al. I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system. IMC '07: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement (2007)

Crane and Sornette. Robust dynamic classes revealed by measuring the response function of a social system. Proceedings of the National Academy of Sciences (2008) vol. 105 (41) pp. 15649

Guo et al. Analyzing patterns of user content generation in online social networks. Proceedings of the 15th ACM SIGKDD international … (2009)

Cha et al. Analyzing the video popularity characteristics of large-scale user generated content systems. IEEE/ACM Transactions on Networking (TON (2009) vol. 17 (5)

Goel et al. Anatomy of the long tail: ordinary people with extraordinary tastes. WSDM '10: Proceedings of the third ACM international conference on Web search and data mining (2010)

Szabo and Huberman. Predicting the popularity of online content. Communications of the ACM (2010) vol. 53 (8)

PART II - DYNAMICS ON ONLINE SOCIAL NETWORKS AND OTHER SOCIAL MEDIA


General literature on communication pattern


Barabasi. The origin of bursts and heavy tails in human dynamics. Nature (2005) vol. 435 (7039) pp. 207-211
Empirical study of email communication patterns
Model: non-possionian, which implies bursty behavior.

Liben-Nowell and Kleinberg. Tracing information flow on a global scale using Internet chain-letter data. Proceedings of the National Academy of Sciences (2008) vol. 105 (12) pp. 4633
Empirical study of chain letters propagation: observe a counter-intuitive pattern but explain it: propagation through a narrow but very deep tree-like pattern for hundreds of steps.
Dataset: chain letters

Malmgren and Stouffer. A Poissonian explanation for heavy tails in e-mail communication. Proceedings of the … (2008)
Model: explore email communications by a cascading non-homogeneous Poisson process
Empirical study


Malmgren et al. Characterizing individual communication patterns. KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (2009)
Followup on the above work.
Problem: classifying people according to their communication patterns.
Model: simplified cascading non-homogeneous Poisson process
Empirical study
Dataset: two university network email datasets


Kossinets et al. The structure of information pathways in a social communication network. KDD '08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (2008)
Empirical study of temporal dynamics of email communications.
infer communication pathways in the network and weights for edges on the email graph.
Proof: NP-hardness

Social dynamics 1: Information propagation



Zoom on Flickr

Cha et al. Characterizing social cascades in flickr. WOSN '08: Proceedings of the first workshop on Online social networks (2008)
empirical study of social cascades and information dissemination on Flickr.

Cha et al. A measurement-driven analysis of information propagation in the flickr social network. Proceedings of the 18th … (2009)
full version of the above paper: empirical study of social cascades and information dissemination on Flickr.
dataset: 2.5 million users and 11 million photos

Zoom on blogs

Kumar et al. On the bursty evolution of blogspace. World Wide Web (2005) vol. 8 (2) pp. 159-178
Empirical studies on the growth and burst of the blogspace in early 2000's.
Dataset: a few blogging sites such as blogger.com

Adar and Adamic. Tracking information epidemics in blogspace. Web Intelligence, 2005. Proceedings. The 2005 IEEE/WIC/ACM International Conference on (2005) pp. 207 - 214
Track information flow in blogs using classifiers such as SVM classifier to infer information propagation routes and compare them with epidemiological models.
There is also a visualization tool for their model.

Leskovec et al. Cascading Behavior in Large Blog Graphs Patterns and a Model. Proc. SIAM International Conference on Data Mining (2007)
Empirical study on information propagation and cascades on the blogspace and also a generative model to emulate real cascades.
Dataset: 21.3 million posts from 2.5 million blogs

Agarwal et al. Identifying the influential bloggers in a community. Proceedings of the international conference on Web search and web data mining (2008) pp. 207-218
Problem: finding influential bloggers and posts. specify some parameters and build a preliminary model.
Experimental evaluation: real blog dataset.

El-Arini et al. Turning down the noise in the blogosphere. Proceedings of the 15th ACM SIGKDD international … (2009)
Problem: find the set of posts that maximize coverage of important news. formalize as a submodular optimization problem. computer near optimal solution. learning a personalized coverage function. a no-regret algorithm
Experimental evaluation on blog data and also user study

Götz et al. Modeling blog dynamics. AAAI Conference on … (2009)
Introduce a "zero-crossing" model for blog dynamics which generates patterns and properties of the blogosphere.
Experimental evaluation on a dataset of 2.2 million posts.

Zoom on twitter


Huberman et al. Social networks that matter: Twitter under the microscope. First Monday (2009) vol. 14 (1) pp. 8
Empirical study
Dataset: Twitter

Kwak et al. What is Twitter, a social network or a news media?. Proceedings of the 19th international conference on World wide web (2010) pp. 591-600
Empirical studies + some problems such as finding influential nodes. Techniques are simple: PageRank,...
Dataset: very huge dataset of Twitter

Sakaki et al. Earthquake shakes Twitter users: real-time event detection by social sensors. Proceedings of the 19th international conference on World wide web (2010) pp. 851-860
Problem: real time earth-quake detection.
Use Kalman and particle filtering methods.
Dataset: twitter
Experimental evaluation that confirms effectiveness of their methods.

Cha et al. Measuring User Influence in Twitter: The Million Follower Fallacy. Proceedings of the 4th … (2010)
Mostly empirical- No proofs.
Dataset: 6 million users of twitter.
Interesting observations.

Social dynamics 2: Influence and recommendation


Domingos and Richardson. Mining the network value of customers. Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (2001) pp. 57-66
Problem: extracting "network value" of users of a social network for viral marketing campaigns.
Model: social network as a Markov random field.
Dataset: a collaborative filtering database: a movie rating dataset.
Empirical study performed.

Richardson and Domingos. Mining knowledge-sharing sites for viral marketing. Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining (2002) pp. 70
Follow-up on the above work: improved function for the model used in the above paper, and therefore fixed some of the problems with that model.

Leskovec et al. The dynamics of viral marketing. ACM Transactions on the Web (2007)
Observation and empirical analysis on a real viral marketing campaign for a bookstore.
Empirical
Dataset: 4 million people, 16 million recommendations on 0.5 million products.


Leskovec and Singh…. Patterns of influence in a recommendation network. Advances in Knowledge Discovery … (2006)
Follow-up on the above work: extracted cascade patterns for recommendation systems.
Empirical.
Dataset: same as the above.

Bakshy et al. Social influence and the diffusion of user-created content. EC '09: Proceedings of the tenth ACM conference on Electronic commerce (2009)
Study influence and diffusion on Second Life dataset
Empirical
Dataset: Second Life

Onnela and Reed-Tsochas. Spontaneous emergence of social influence in online systems. Proceedings of the National Academy of Sciences (2010) vol. 107 (43) pp. 18375-18380
Empirical