Spring 2015 CSE592 Social Networks

Time and Location

Monday Wednesday 2:30-3:50pm @ Frey Hall 313

Instructor

Jie Gao, 1415 Computer Science, jgao at cs dot stonybrook dot edu. Office hour: 4-5 MW, Skype ID: jiegao79.

Announcement:

  1. Homework 1 is posted on blackboard.
  2. Lecture notes for the first three classes are posted on blackboard.
  3. Project list is posted on blackboard.

Course Description:

Social interactions are an important part of our everyday lives. In this 3-credit course we will examine models of social interactions as well as applications that aid such interactions. We will study both structures of social networks such as small world phenomena, power law degree distribution as well as processes on social networks such as contagions, markets and games. Topics of the course will include, but not limited to

  • Small world phenomena
  • Power law degree distribution and preferential attachment
  • Internet backbone structure
  • Web structure, bow-tie
  • Random walk, PageRank algorithm
  • Diffusion, contagions, cascades
  • Road networks
  • Human mobility patterns

Requirements and Grading

  • Each student is required to give a 20-30 minutes paper presentation. Check the syllabus below for the dates of presentation. Presentation will be 20% of the final grade.
  • 2-3 written homework.
  • The main requirement of the course is a project (60% of final grade). Detailed to be discussed in class.
  • No exams.

Reading List:

Textbooks

  • [EK10] David Easley, Jon Kleinberg, Networks, Crowds and Markets, Cambridge University Press, 2010. This is the main textbook. You can download the electronic version here.
  • [LRU] Jure Leskovec, Anand Rajaraman, and Jeff Ullman Mining of Massive Datasets, Cambridge University Press, You can download the electronic version here.
  • [K11] David Kempe, Structure and Dynamics of Information in Networks, lecture notes, 2011. Available here.
  • [N10] M. E. J. Newman, Networks: An Introduction, Oxford University Press, 2010.
  • [WF09] Stanley Wasserman, Katherine Faust, Social Network Analysis, Methods and Applications, Cambridge University Press, 2009.

Syllabus

   Required reading 
1/26SNOW DAY

1/28Introduction
  • [EK10] Chapter 1

2/2SNOW DAY

2/4Strong tie & weak tie
  • [EK10] Chapter 2 & 3
  • Lars Backstrom, Jon Kleinberg, Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook, Proc. 17th ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW), 2014. pdf
  • J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, A.L. Barabasi. Structure and tie strengths in mobile communication networks. PNAS, 2007. pdf.

2/9Homophily, basic random graphs
  • [EK10] Chapter 4
  • Lars Backstrom, Jon Kleinberg, Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook, Proc. 17th ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW), 2014. pdf
  • Random graphs. Notes by Kleinberg available here.

2/11Random Graph Models
  • Random graphs. Notes by Kleinberg available here. Notes by Aaron Clauset here.
  • Configuration model. Notes by Aaron Clauset here

2/16 Student Presentation
  1. Eric Gilbert and Karrie Karahalios, Predicting Tie Strength With Social Media, CHI 2009, pdfMd Atiqur Rahman and Srikant Agarwal.
  2. J. Ugander, L. Backstrom, J. Kleinberg. Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections. Proc. 22nd International World Wide Web Conference, 2013. pdfSriganesh Navaneethakrishnan and Murali Krishna.
  3. Charalampos E. Tsourakakis, U Kang, Gary L. Miller, and Christos Faloutsos, DOULION: Counting Triangles in Massive Graphs with a Coin, KDD'09, pdf. Jian Yang and Weiliang Xing.
 
2/18Signed Network
Community Detection
 
2/23Spectral Clustering 
2/25 Student presentation
  1. Damon Centola, Juan Carlos Gonzalez-Avella, Vıctor M. Eguıluz, Maxi San Miguel, Homophily, Cultural Drift, and the Co-Evolution of Cultural Groups, Journal of Conflict Resolution, 2007. pdfHarish kumar RavichandranSaisruthi Sathyanarayanan.
  2. Cosma Rohilla ShaliziAndrew C. ThomasHomophily and Contagion Are Generically Confounded in Observational Social Network Studies, pdfMoiz Ali, Kavana Anand.
  3. Jérôme Kunegis, Applications of Structural Balance in Signed Social Networks, arXiv, 2014. pdfShikha Singh, Ankit Arun.
 
3/2Web graph, hub and authority, PageRank
  • [EK10] Chapter on WWW
 
3/4Analysis of Hub & Authority, PageRank

3/6 (SNOW DAY makeup)Power Law degree 
3/9 Small world phenomena
  •  [EK10] Chapter on small world
 
3/11    
3/23 Internet Curvature

3/25   
3/27 (SNOW day makeup) Student presentation
  1. Deeper Inside PageRank, Amy N. Langville† and Carl D. Meyer, presented by Vineeth Lakshminarayanan and Ashwin Giridharan
  2. What's New on the Web, The Evolution of the web from a Search Engine PerspectiveAlexandros NtoulasJunghoo ChoChristopher Olstonpresented by Pragathi Reddy Mallu and Vivek Nuthalapati 
  3. Link communities reveal multiscale complexity in networksYong-Yeol AhnJames P. Bagrow Sune Lehmann, presented by Nitish Garg and Isha Khanna
    http://www.nature.com/nature/journal/v466/n7307/full/nature09182.html
 
3/30  Epidemics
  •   [EK10] Chapter on epidemics
 
4/1 Student presentation
  1. On the Treeness of Internet Latency and Bandwidth, Venugopalan Ramasubramanian, Dahlia Malkhi, Fabian Kuhn, Mahesh Balakrishnan, Archit Gupta, Aditya Akella. Presented by Vasudevan Nagendra
  2. F. Papadopoulos, C. Psomas, and D. Krioukov, Network Mapping by Replaying Hyperbolic Growth, PDF. Presented by Nupur Dichwalkar
    Aadarsh Kenia
  3. M. Boguna, D. Krioukov, and K. C. Claffy. Navigability of complex networks. Nature Physics, 5:74–80, January 2009. pdf. Presented by Rutuja Marathe, Tanvi Sirsat .

4/6 Social Contagion
  •  [EK10] Chapter on cascading 

4/8 Influence maximization
  • David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of influence in a social network. In Proc. 9th Intl. Conf. on Knowledge Discovery and Data Mining, pages 137–146, 2003. pdf
  • [K11] Chapter 8

4/13


4/15Student presentation
  1. Chen Avin, Barbara Keller, Zvi Lotker, Claire Mathieu, David Peleg, Yvonne-Anne Pignolet, Homophily and the Glass Ceiling Effect in Social Networks. ITCS'15, pdfMehak Mehta, Amit Khandelwal
  2. Wei Chen, Yajun Wang, Siyu Yang, Efficient Influence Maximization in Social Networks, KDD‘09, pdfSreenath Mullassery
  3. Marcelo Kuperman and Guillermo Abramson. Small world effect in an epidemiological model. Physical Review Letters, 86(13):2909–2912, March 2001. pdfShrey Shah, Swijal Patil

4/20Student presentation
  1. M. E. J. Newman, I. Jensen, and R. M. Ziff, Percolation and epidemics in a two-dimensional small world, Phys. Rev. E 65, 021904 – Published 16 January 2002. pdf Saransh Zargar
  2. Jeremy Ginsberg, Matthew H. Mohebbi, Rajan S. Patel, Lynnette Brammer, Mark S. Smolinski & Larry Brilliant, Detecting influenza epidemics using search engine query data, Nature, 457, 1012-1014 (19 February 2009). pdfAashray Arora, VARUN KUMAR VALA
  3. Henry L. RoedigerMichelle L. MeadeErik T. BergmanSocial contagion of memory, Psychonomic Bulletin & ReviewJune 2001, Volume 8, Issue 2, pp 365-371. pdf. bharat singh

4/22Road network
4/27  Mobility trajectories  
4/29  Paper presentation
  1. Matthew J. Salganik, Peter Sheridan Dodds, Duncan J. Watts, Experimental Study of Inequality and Unpredictability in an Artificial Cultural Market, Science. pdf Upasi Mehta, Minesh Javiya
  2. The ties that lead: A social network approach to leadership, Prasad BalkundiMartin Kilduff. The Leadership Quarterly
    Volume 17, Issue 4, August 2006, Pages 419–439, pdfNeeraj Devadath
    Shashi Ranjan
  3. "A Review of Urban Computing for Mobile Phone Traces: Current Methods, Challenges and Opportunities", S. Jiang, Y. Yang, G. Fiore, J. Ferreira Jr., E. Frazzoli, M.C. González, Proceedings of the ACM SIGKDD International Workshop on Urban Computing,  (2013).  Jianglin Wu & Jiaqi Chen
 
5/4
Project Presentation    
5/6
Project Presentation

Additional Reading:

Tie Strength
  • Mark Granovetter. “The Strength of Weak Ties.” American Journal of Sociology. 1973. pdf.
  • Cameron Marlow, Lee Byron, Tom Lento, and Itamar Rosenn, Maintained Relationship on Facebook, online.
  • J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, A.L. Barabasi. Structure and tie strengths in mobile communication networks. PNAS, 2007. pdf.
  • Tie strength introduced in LinkedIn. http://mashable.com/2014/01/29/linkedin-kevin-bacon/
    http://blog.linkedin.com/2014/01/29/seeing-who-you-know-and-how-you-know-them-just-got-easier-with-linkedin/
  • Lars Backstrom, Jon Kleinberg, Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook, Proc. 17th ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW), 2014. pdf
  • Eric Gilbert and Karrie Karahalios, Predicting Tie Strength With Social Media, CHI 2009, pdf
  • J. Ugander, L. Backstrom, J. Kleinberg. Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections. Proc. 22nd International World Wide Web Conference, 2013. pdf
  • Charalampos E. Tsourakakis, U Kang, Gary L. Miller, and Christos Faloutsos, DOULION: Counting Triangles in Massive Graphs with a Coin, KDD'09, pdf
Homophily
  • Damon Centola, Juan Carlos Gonzalez-Avella, Vıctor M. Eguıluz, Maxi San Miguel, Homophily, Cultural Drift, and the Co-Evolution of Cultural Groups, Journal of Conflict Resolution, 2007. pdf.
  • Cosma Rohilla Shalizi, Andrew C. Thomas, Homophily and Contagion Are Generically Confounded in Observational Social Network Studies, pdf.
Small World and Navigation
  • J. Travers and S. Milgram. An experimental study of the small world problem. Sociometry 32(1969). pdf
  • Random graphs. Notes by Kleinberg available here.
  • Watts, D. J.; Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature 393 (6684): 440–442. pdf.
  • J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006. pdf.
  • Peter Sheridan Dodds, Roby Muhamad, Duncan J. Watts. An Experimental Study of Search in Global Social Networks. Science 301(2003), 827. pdf.
  • D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. In Proceedings of the National Academy of Science, volume 102, pages 11623–11628, 2005. pdf.
  • O. Simsek and D. Jensen. Navigating networks by using homophily and degree. In Proceedings of the National Academy of Sciences, pages 12758–12762, September 2008. pdf
  • J. Kleinberg. Small-world phenomena and the dynamics of information. In In Advances in Neural Information Processing Systems 14. MIT Press, 2001.pdf.
  • M. Boguna, D. Krioukov, and K. C. Claffy. Navigability of complex networks. Nature Physics, 5:74–80, January 2009. pdf.
Link Prediction
  • David Liben-Nowell, Job Kleinberg, The link prediction problem for social networks, CIKM'03 Proceedings of the 20th International Conference on Information and Knowledge Management, 556-559, 2003. pdf
  • Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56:89–113, 2004. pdf.
Signed Networks
  • Signed Networks in Social Media by J. Leskovec, D. Huttenlocher, J. Kleinberg. ACM SIGCHI Conference on Human Factors in Computing Systems (CHI), 2010.
  • R. V. Guha, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins. Propagation of trust and distrust. In Proc. 13th International World Wide Web Conference, 2004. pdf.
  • Aris Anagnostopoulos, Ravi Kumar, and Mohammad Mahdian. Influence and correlation in social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, pages 7–15, New York, NY, USA, 2008. ACM. pdf
  • Jérôme Kunegis, Applications of Structural Balance in Signed Social Networks, arXiv, 2014. pdf.
Community Discovery
Web Graph and PageRank
Power Law DegreeContagion and Diffusion
Friendship Paradox
Human Mobility
  • A.-L. Barabási, The origin of bursts and heavy tails in human dynamics. Nature 435, 207–211 (2005). PDF 
  • de Montjoye, Yves-Alexandre; César A. Hidalgo, Michel Verleysen, Vincent D. Blondel (March 25, 2013). "Unique in the Crowd: The privacy bounds of human mobility". Nature srep. doi:10.1038/srep01376
  • Understanding the spreading patterns of mobile phone viruses (P. Wang, M.C. González, C.A. Hidalgo, A.-L. Barabási), In Science, volume 324, 2009. [pdf
  • Understanding individual human mobility patterns (M.C. González, C.A. Hidalgo, A.-L. Barabási), In Nature, volume 453, 2008. [pdf
Network Evolution
Internet Topology
Road Network

Project:

  • Project proposal due 3/23/15 (after spring break). Each student needs to submit one to two pages document describing the project objective, the methodology to be adopted, the technical challenges, project deliverables. 
  • If multiple students work on the components of a bigger project, the group need to submit a proposal for the big project, and each group member needs to have a one page document on  individual task.

Resources:

Other courses: