Computer Laboratory

Social and Technological Network Analysis (Lent Term 2011-2012)

The current page for this course can be found from this link

Lecture 1: Networks and Random Graphs

Lecture 2: Small World and Weak Ties

Lecture 3: Network Centrality and Community Detection

Lecture 4: Modularity and Overlapping Communities

Lecture 5: Structure of the Web and Power Laws

Lecture 6: The Internet and Robustness

Lecture 7: Information Cascades on Networks

Lecture 8: Epidemic Dissemination on Networks

Lecture 9: Cascades and Epidemics: Applications

Lecture 10: Temporal Social Networks

Lecture 11 and 12: Practical NetworkX Analysis of Datasets

Lecture 13: Geo-Social Networks

Lecture 14 and 15: Student Presentations

Lecture 16: Industrial Lecture

Assessment

Details of the assessment process, papers and datasets are contained here

Readling List

D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.

M. Newmann. Networks. Oxford University Press. April 2010.

R. Albert, A. Barabasi. Statistical Mechanics of Complex Networks. Reviews of Modern Physics (74). Jan. 2002.

S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang. Complex Networks: Structure and Dynamics, Physics Reports 424 (2006) 175

Watts, D.J.; Strogatz, S.H. (1998). ”Collective dynamics of ’small-world’ networks. Nature 393 (6684): 40910.

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. Proceedings of the National Academy of Sciences, Vol. 104, No. 18. (13 Oct 2006), pp. 7332-7336.

C. Marlow, L. Byron, T. Lento, and I. Rosenn. Maintained relationships on facebook. 2009. On-line at http://overstated.net/2009/03/09/maintained- relationships-on-facebook.

B. A. Huberman, D. M. Romero, and F. Wu. Social networks that matter: Twitter under the microscope. First Monday, 14(1), January 2009.

M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA, 99(12):78217826, June 2002.

S. Fortunato. Community detection in graphs, Arxiv 2009.

M.E.J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 2004.

A. Clauset, M.E.J. Newman, C. Moore. Finding community structure in very large networks. Phys. Rev. E 70, 066111, 2004.

G. Palla, I. Derényi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature.  435, 814-818 (2005).

A. Lancichinetti, F. Radicchi,3 J. Ramasco, S. Fortunato. Finding statistically significant communities in networks. PLOS One 2011; 6(4). (not discussed in class).

P. Grabowicz, J. Ramasco, E. Moro, J. Pujol, V.. Eguiluz. Social features of online networks: the strength of weak ties in online social media. arXiv:1107.4009. July 2011.

A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the Web. In Proc. 9th International World Wide Web Conference, pages 309-320,2000.

A. Clauset, C. R. Shalizi and M. E. J. Newman, 2009. Power-law distributions in empirical data. SIAM Review Vol. 51, No. 4. (2 Feb 2009), 661.

Barabasi, Albert-Lszl and Rka Albert, ”Emergence of scaling in random networks”, Science, 286:509-512, October 15, 1999.

M. Salganik, P. Dodds, and D. Watts. Experimental study of inequality and unpredictability in an artificial cultural market. Science, 311:854-856, 2006.

R. Albert, H. Jeong, A.-L. Barabsi. Error and attack tolerance of complex networks. Nature 406, 378-482 (2000).

Cohen et al., Phys. Rev. Lett. 85, 4626 (2000)

D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Network robustness and fragility: Percolation on random graphs, Phys. Rev. Lett., 85 (2000), pp. 54685471.

Pastor-Satorras, R. and Vespignani, A. Epidemic Spreading in Scale-Free Networks. Phys. Rev. Lett.(86), n.14. Pages = 3200--3203. 2001.

Pastor-Satorras, R. and Vespignani, A. Immunization of Complex Networks. Physical Review E 65. 2002.

Marcelo Kuperman and Guillermo Abramson. Small world effect in an epidemiological model. Physical Review Letters, 86(13):2909–2912, March 2001.

Meeyoung Cha, Alan Mislove, Ben Adams, and Krishna P. Gummadi. 2008. Characterizing social cascades in flickr. In Proceedings of the first workshop on Online social networks (WOSN '08). ACM, New York, NY, USA, 13-18.

D. Liben-Nowell and J. Kleinberg. Tracing information flow on a global scale using Internet chain-letter data.PNAS March 25, 2008 vol. 105 no. 12 pp. 4633-4638.

J. Tang, S. Scellato, M. Musolesi, C. Mascolo and V. Latora. Small-world behavior in time-varying graph In Physical Review E. Vol. 81 (5), 055101, American Physical Society. May 2010.

J. Tang, M. Musolesi, C. Mascolo, V. Latora, V. Nicosia. Analysing Information Flows and Key Mediators through Temporal Centrality Metrics. In Proceedings of 3rd Workshop on Social Network Systems (SNS 2010). Paris, France. April 2010.

J. Tang, M. Musolesi, C. Mascolo and V. Latora. Temporal Distance Metrics for Social Network Analysis. In Proceedings of the 2nd ACM SIGCOMM Workshop on Online Social Networks (WOSN09). Barcelona, Spain. August 2009.

J. Tang, C. Mascolo, M. Musolesi, V. Latora. Exploiting Temporal Complex Network Metrics in Mobile Malware Containment. In Proceedings of IEEE 12th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WOWMOM2011). Lucca, Italy. June 2011.

S. Scellato, A. Noulas, R. Lambiotte and C. Mascolo. Socio-spatial Properties of Online Location-based Social Networks In Proceedings of Fifth International AAAI Conference on Weblogs and Social Media (ICWSM 2011). Barcelona, Spain, July 2011.

S. Scellato, C. Mascolo, M. Musolesi, V. Latora. Distance Matters: Geo-social Metrics for Online Social Networks In Proceedings of the 3rd Workshop on Online Social Networks (WOSN2010). Co-located with USENIX2010. Boston, MA. June 2010.