Course pages 2013–14
Social and Technological Network Analysis
Lecture Material
Lecture 1 (17/1/14, noon): Networks and Random Graphs
Lecture 2 (22/1/14, 10am): Small World and Weak Ties
Lecture 3 (24/1/14, noon): Network Centrality and Applications
Lecture 4 (29/1/14, 10am): Community Detection and Overlapping Communities
Lecture 5 (31/1/14, noon): Structure of the Web, Search and Power Laws
Lecture 6 (5/2/14, 10am): Network Robustness and Applications
Lecture 7 (7/2/14, noon): Cascades and Behaviour Influence
Lecture 8 and 9 (12/2/14, 10am-12): Practical Network Analysis Tutorial by Petko Georgiev. Please install this software and download this dataset
Lecture 10 (14/2/14 noon): Epidemic Spreading and Examples (Guest Lecturer: Dr Mirco Musolesi, University of Birmingham)
Please note the one week break here.
Lecture 11 (26/2/14 10am): Epidemics and Information Cascades Applications
Lecture 12 (28/2/14 noon): Industrial Seminar on Spatial Network Analysis (Guest Lecturer: Dr Salvatore Scellato, Google UK)
Lecture 13 (5/3/14 10am): Temporal Network Analysis
Lecture 14 (7/3/14 noon): Industrial Seminar: "Rumors, cascades and word of mouth: observing virality on Facebook". Guest Lecturer: Adrien Friggeri, Facebook
Lecture 15 and 16 (12/3/14 10am-1pm): Student Presentations
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.
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
D. Centola. The Spread of Behavior in an Online Social Network Experiment. Science 329, 1194 (2010).
S. Gonzalez Bailon, J. Borge-Holthoefer, A. Rivero and
Y. Moreno. The Dynamics of Protest Recruitment through an Online
Network. Nature Scientific Reports, 1, 197 (2011).
Lecture 10
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.
V. Colizza, A. Barrat, M. Barthélemy and
A. Vespignani. Predictability and epidemic pathways in global
outbreaks of infectious diseases: the SARS case study. BMC Medicine
2007, 5:34.
Antonio Lima, Manlio De Domenico, Veljko Pejovic and Mirco Musolesi. Exploiting Cellular Data for Disease Containment and Information Dissemination Campaigns Strategies in Country-wide Epidemics. In Proceedings of NetMob’13. Boston, MA, USA. May 2013.
Marc Lipsitch, Lyn Finelli, Richard T. Heffernan, Gabriel M. Leung, and Stephen C. Redd. Improving the Evidence Base for Decision Making during a Pandemic: The Example of 2009 Influenza A/H1N1. In Biosecurity and Bioterrorism: Biodefense Strategy, Practice and Science. Volume 9, Number 2, 2011.
Matt J. Keeling and Pejman Rohani. Modeling Infectious Diseases in
Humans and Animals. Princeton University Press. 2007.
Lecture 11
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.
Lecture 12
The length of bridge ties: structural and geographic properties of online social
interactions. Yana Volkovich, Salvatore Scellato, David Laniado, Cecilia Mascolo
and Andreas Kaltenbrunner. In Proceedings of Sixth International AAAI Conference
on Weblogs and Social Media (ICWSM 2012). Ireland. June 2012.
Far from the eyes, close on the Web: impact of geographic distance on online
social interactions. Andreas Kaltenbrunner, Salvatore Scellato, Yana Volkovich,
David Laniado, Dave Currie, Erik J. Jutemar, Cecilia Mascolo. In ACM SIGCOMM
Workshop on Online Social Networks (WOSN 2012). Finland. 2012.
A tale of many cities: universal patterns in human urban mobility. Anastasios
Noulas, Salvatore Scellato, Renaud Lambiotte, Massimiliano Pontil, Cecilia
Mascolo. In PLoS ONE. PLoS ONE 7(5): e37027.
The Importance of Being Placefriends: Discovering Location-focused Online
Communities. Chloë Brown, Vincenzo Nicosia, Salvatore Scellato, Anastasios
Noulas, Cecilia Mascolo. In ACM SIGCOMM Workshop on Online Social Networks
(WOSN 2012). August 2012.
Porta, S. Latora, V, Strano,E, et al "Street centrality and densities of retail and
services in Bologna, Italy", Environment and Planning B: Planning and design,
36,3,450-465,2009.
Strano et al: Elementary Processes Governing the evolution of Street Network. Nature
Scientific Report (2012)
Porta S, Crucitti P, Latora V. (2006), The network analysis of
urban streets: a primal approach, «Environment and Planning B:
planning and design», 33
Strano, E. Viana, M. Cardillo, A. Porta, S. Da
Costa, L Latora, V. "Urban street networks, a
comparative analysis of ten European cities."
Environment and Planning B
Lecture 13
V. Nicosia, J. Tang, C. Mascolo, M. Musolesi, G. Russo and V. Latora. Graph Metrics for Temporal Networks. Book Chapter in Petter Home and Jari Saramaki (Editors). Temporal Networks. Springer. 2013.
J. Tang, I. Leontiadis, S. Scellato, V. Nicosia, C. Mascolo, M. Musolesi and V. Latora. Applications of Temporal Graph Metrics to Real-World Networks. Book Chapter in Petter Holme and Jari Saramaki (Editors). Temporal Networks. Springer. 2013.
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. May 2010.
J. Tang, M. Musolesi, C. Mascolo, V. Latora, V. Nicosia. Analysing Information Flows and Key Mediators through Temporal Centrality Metrics. In Proc. of the 3rd Workshop on Social Network Systems (SNS 2010). Apr 2010.
J. Tang, M. Musolesi, C. Mascolo and V. Latora. Temporal Distance Metrics for Social Network Analysis. In Proc, of the 2nd ACM SIGCOMM Workshop on Online Social Networks (WOSN09). Aug 2009.
J. Tang, C. Mascolo, M. Musolesi, V. Latora. Exploiting Temporal Complex Network Metrics in Mobile Malware Containment. In Proc. of the IEEE 12th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM2011). Jun 2011.
V. Nicosia, J. Tang, M. Musolesi, G. Russo, C. Mascolo, V. Latora. Components in time-varying graphs. In AIP Chaos. Vol.22 Issue 2. 2012.