Computer Laboratory

Course pages 2013–14

Social and Technological Network Analysis

1 - Research paper report

Every student will prepare one report (of approximately 1,500 words) on one assigned research paper. The report is worth 30% of the final mark.

The report will contain two parts of about 750 words each:

  • Critical analysis of the papers including, possibly, comparisons and references to other material presented in the course or found by the student and comments on how solid the result obtained are (e.g., comments on the evaluation methods or on the analysis applied can be included).
  • Discussion of possible future research ideas in the area.

This is a selection of mainly recent research papers on social and technological networks. Choose any still available paper and e-mail your choice to cm542: the submission of reports is to be done via email to cm542 in PDF format in addition to handing a hard copy to the office.

Deadline for choice: 25th January 2014

Deadline for submission: 14th February 2014

  1. D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. Proc. CIKM, 2003.
  2. D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, A. Tomkins. Geographic routing in social networks. Proc. Natl. Acad. Sci., 102, 2005.
  3. Christo Wilson, Bryce Boe, Alessandra Sala, Krishna P. N. Puttaswamy, Ben Y. Zhao. User Interactions in Social Networks and their Implications. ACM EuroSys 2009
  4. A. Goyal, F. Bonchi, L.V.S. Lakshmanan. Learning influence probabilities in social networks. In Proc. WSDM, 2010.
  5. Rongjing Xiang, Jennifer Neville, Monica Rogati. Modeling Relationship Strength in Online Social Network In Proc. WWW, 2010.
  6. Alessandra Sala, Lili Cao, Christo Wilson, Robert Zablit, Haitao Zheng, Ben Zhao. Measurement-calibrated Graph Models for Social Network Experiments In Proc. WWW, 2010.
  7. Munmun De Choudhury, Winter Mason, Jake Hofman, Duncan Watts. Inferring Relevant Social Networks from Interpersonal CommunicationIn Proc. WWW, 2010.
  8. J. Leskovec, D. Huttenlocher, J. Kleinberg. Signed Networks in Social Media. In Proc. CHI, 2010.
  9. D.M. Romero and J. Kleinberg. The Directed Closure Process in Hybrid Social-Information Networks, with an Analysis of Link Formation on Twitter. Proc. 4th International AAAI Conference on Weblogs and Social Media, 2010.
  10. J. Leskovec, D. Huttenlocher, J. Kleinberg. Predicting Positive and Negative Links in Online Social Networks. In Proc. WWW, 2010.
  11. Shuang-hong Yang, Bo Long, Alex Smola, Narayanan Sadagopan, Zhaohui Zheng and Hongyuan Zha. Like like alike: Joint friendship and interest propagation in social networks. Proceedings of WWW 2011, 2011.
  12. J. Cheng, D. Romero, B. Meeder, J. Kleinberg. Predicting Reciprocity in Social Networks. Proc. 3rd IEEE Conference on Social Computing, 2011.
  13. E. Sadikov, M. Medina, J. Leskovec, H. Garcia-Molina. Correcting for Missing Data in Information Cascades ACM International Conference on Web Search and Data Mining (WSDM), 2011
  14. Paul Expert, Tim S. Evans, Vincent D. Blondel, Renaud Lambiotte. Uncovering space-independent communities in spatial networks. Proceedings of the National Academy of Sciences, Vol. 108, No. 19. (10 May 2011), pp. 7663-7668.
  15. Lars Backstrom and Jon Kleinberg. Network Bucket Testing Proceedings of WWW 2011, 2011.
  16. Eytan Bakshy, Jake M Hofman, Duncan J Watts, Winter A Mason. Identifying Influencers on Twitter ACM International Conference on Web Search and Data Mining (WSDM), 2011
  17. Jukka-Pekka Onnela, Samuel Arbesman, Marta C. Gonzalez, Albert-Laszlo Barabasi, Nicholas A. Christakis. Geographic Constraints on Social Network Groups. PLoS ONE, Vol. 6, No. 4. (5 April 2011),
  18. Silvio Lattanzi, Alessandro Panconesi and D. Sivakumar. Milgram-Routing in Social Networks Proceedings of WWW 2011.
  19. Eytan Bakshy, Itamar Rosenn, Cameron Marlow, Lada Adamic. The Role of Social Networks in Information Diffusion Proceedings of WWW 2012.
  20. Xiaohan Zhao, Alessandra Sala, Christo Wilson, Xiao Wang, Sabrina Gaito, Haitao Zheng, Ben Y. Zhao. Multi-scale dynamics in a massive online social network Proceedings of IMC 2012.
  21. Michele Coscia, Giulio Rossetti, Fosca Giannotti, Dino Pedreschi. DEMON: a local-first discovery method for overlapping communities. Proceedings of KDD 2012.
  22. Blake Shaw, Jon Shea, Siddhartha Sinha and Andrew Hogue. Learning to Rank for Spatiotemporal Search. Proceedings of WSDM13.
  23. Justin Cranshaw, Raz Schwartz, Jason I. Hong and Norman Sadeh. The Livehoods Project: Utilizing Social Media to Understand the Dynamics of a City. Proceedings of ICWSM12.

2 - Project

Every student will complete a project which consists of analysis of an assigned dataset according to some indicated network measures using NetworkX: the analysis should be reported in a document of about 1,500 words where the results are commented and justified. This will be worth 50% of the final mark.

Each student is encouraged to come up with original project proposals which may be inspired by the ideas reported below.

Deadline for choice: 14th February 2014

Deadline for submission: 11th March 2014 at noon

Datasets (list to be confirmed)

  1. Amazon: co-purchase product network and all product information. (548,552 products)
    Project ideas:
    • extraction of network communities and analysis of their homogeneity with respect to product categories;
    • analysis of potential correlations between network node metrics and product sales/reviews;
    • prediction model for product sales given network properties and product characteristics.
  2. HEP-PH: citation graph among papers in high-energy physics with temporal publication data of each paper. (34,546 nodes and 421,578 directed edges)
    Project ideas:
    • investigation of power-law network structure evolution over time with a generative model;
    • analysis of the first-mover advantage for scientific publications;
    • analysis/design of ranking algorithms to facilitate search among publications.
  3. Epinions: trust and distrust signed social network among users on (131,828 nodes and 841,372 directed edges)
    Project ideas:
    • analysis of the structure of the social network arising from positive, negative and aggregated edges, with an investigation of the correlations among them;
    • analysis of social triangles and verification of structural balance theory ("the enemy of my enemy is my friend");
    • prediction models of the sign of a social link.
  4. Facebook: friendship connections within one regional network and information about interaction events between users, such as likes, comments and the like. (657,681 nodes and 1,302,764 undirected edges)
    Project ideas:
    • analysis and comparison of the social network among Facebook users and the network arising from their explicit interactions;
    • prediction models of interaction between users;
    • analysis of user activity as a function of ego-network properties.
  5. Cond-Mat: collaboration network extracted from the e-print arXiv, covering co-authorship ties from the papers submitted to the Condensed Matter category. (23,133 nodes and 186,936 undirected edges)
    Project ideas:
    • analysis of the social properties of the coauthorship networl
    • study of correlation between scientific productivity and network position
  6. Enron: email communication network between Enron employees and with external email addresses. (36,692 nodes and 367,662 undirected edges)
    Project ideas:
    • study of the statistical properties of an email network
    • analysis of the communication patterns
  7. Roads: road network of Pennsylvania, each node is an intersection and each edge is a road. (1,088,092 nodes and 3,083,796 undirected edges)
    Project ideas:
    • characteristics of a planar networks
    • community detection in a planar network
  8. Web: web hyperlinks between pages in the domain. (281,903 nodes and 2,312,497 directed edges)
    Project ideas:
    • centrality measures in a Web graph
    • ranking of Web pages
  9. Wikipedia: discussion network between Wikipedia users. (2,394,385 nodes and 5,021,410 directed edges)
    Project ideas:
    • statistical properties of a large-scale discussion network
    • social network properties of Wikipedia users
  10. Brightkite: social networks arising among Brightkite users, including also a total of 4,491,143 checkins of these users over the period of Apr. 2008 - Oct. 2010. (2,394,385 nodes and 5,021,410 directed edges)
    Project ideas:
    • spatial properties of the social network
    • analysis of the relationship between user mobility and social properties

3 - Presentation

Every student will prepare a brief oral presentation of the project findings. Each presentation MUST last 8 minutes, including questions: thus, a reasonable combination would be a 6-minute talk followed by 2 minutes for questions.

The presentations will take place on 12th March 2014.

Slides must be sent in PDF fomat before 23:59 11th March 2014.

The presentation is worth 20% of the final mark and it will be evaluated along these categories:

  1. Presentation skills [20%]
  2. General knowledge of the subject [20%]
  3. Discussion of findings [40%]
  4. Questions and answers [20%]