Computer Laboratory

Course pages 2014–15

Social and Technological Network Analysis

Lecture Material

Lecture 1 (15/1/15): Networks and Random Graphs

Lecture 2 (20/1/15): Small World and Weak Ties

Lecture 3 (22/1/15): Network Centrality and Applications

Lecture 4 (27/1/15): Community Detection and Overlapping Communities

Lecture 5 (29/1/15): Structure of the Web, Search and Power Laws

Lecture 6 (3/2/15): Network Robustness and Applications

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.

Additional Readings per Lecture

Lecture 1

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

P. Sheridan Dodds, R. Muhamad, and D. J. Watts. An Experimental Study of Search in Global Social Networks. Science 8 August 2003: 301 (5634), 827-829.

J. Ugander, B. Karrer, L. Backstrom, C. Marlow.The Anatomy of the Facebook Social Graph, http://arxiv.org/abs/1111.4503

L. Backstrom, P. Boldi, M. Rosa, J. Ugander, S. Vigna. Four Degrees of Separation, http://arxiv.org/abs/1111.4570

Lecture 2

D.J. Watts, S. Strogatz, (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.

Eytan Bakshy, Itamar Rosenn, Cameron Marlow, and Lada Adamic. The role of social networks in information diffusion. 2012. In Proceedings of the 21st international conference on World Wide Web (WWW '12). ACM, New York, NY, USA, 519-528. .

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

Lecture 3

D. A. Shamma, L. Kennedy, and Elizabeth F. Churchill. 2009. Tweet the debates: understanding community annotation of uncollected sources. In Proceedings of the first SIGCOMM workshop on Social media (WSM '09). ACM, New York, NY, USA.

Lecture 4

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.

Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008 (10).

G. Palla, I. Derenyi, 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.

Lecture 5

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.

A. Barabasi and R. 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.

Lecture 6

R. Albert, H. Jeong, A.-L. Barabasi. 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.

C. Schneider, A. Moreira, J. S. Andrade, Jr., S. Havlin, and H. J. Herrmann. Mitigation of malicious attacks on networks. PNAS 2011 108 (10) 3838-3841.

Lecture 7