====== Web Mining and Social Network Analysis 2011-2012====== * **Dino Pedreschi** Università di Pisa, Knowledge Discovery and Data Mining Lab [[pedre@di.unipi.it]] ===== News ===== * **Appelli sessione invernale 2012-2013: martedì 22 gennaio 2013 ore 9:00 aula A, martedì 12 febbraio 2013 ore 9:00 aula C** * Giovedì 21 giugno ore 9:00 Aula Seminari Ovest: Seminario conclusivo degli studenti sull'analisi della rete sociale del nostro corso costruita a partire da Facebook * Mercoledì 06.06.2012, ore 16:00-18:00, aula C1: Guest lecture di Paolo Cintia (Dottorato di Ricerca in Informatica): "Human mobility and social ties" * Mercoledì 16.05.2012, dalle 14:30 alle 18:30: Lezione Straordinaria all'interno del Workshop su "Tecnologie Linguistiche: un nuovo Rinascimento?". Presso l'Area della Ricerca del CNR, Aula 28 (Via G. Moruzzi, 1 - Pisa)" * La discussione del secondo esercizio (Analisi delle reti) si svolge Mercoledi 7 maggio * La lezione di Lunedì 5 Marzo si svolge col nuovo orario: ore 10:00 - 12:00, Aula D. * Orario di lunedi modificato: ore 10:00 - 12:00, Aula D * Prima lezione dell'edizione 2011-2012: Lunedì 20 Febbraio ===== 2012 Schedule ===== * **Monday, 10:00 - 12:00, Aula D** * **Wednesday, 16:00 - 18:00, Aula C1** ====== Goals ====== Over the past decade there has been a growing public fascination with the complex "connectedness" of modern society. This connectedness is found in many contexts: in the rapid growth of the Internet and the Web, in the ease with which global communication now takes place, and in the ability of news and information as well as epidemics and financial crises to spread around the world with surprising speed and intensity. These are phenomena that involve networks and the aggregate behavior of groups of people; they are based on the links that connect us and the ways in which each of our decisions can have subtle consequences for the outcomes of everyone else. This short course is an introduction to the analysis of complex networks, with a special focus on social networks and the Web - its structure and function, and how it can be exploited to search for information. Drawing on ideas from computing and information science, applied mathematics, economics and sociology, the course describes the emerging field of study that is growing at the interface of all these areas, addressing fundamental questions about how the social, economic, and technological worlds are connected. ====== Syllabus ====== 1) Graph theory and social networks * Graphs * Social, information, biological and technological networks * Strong and weak ties * Networks in their surrounding context 2) The World Wide Web * The structure of the Web * Link analysis and Web search * Web mining e sponsored search markets 3) Network dynamics * Information cascades * Power laws and rich-get-richer phenomena * The small-world phenomenon * Epidemics ====== Textbooks and materials ====== * Slides (see Calendar). * **David Easley, Jon Kleinberg: Networks, Crowds, and Markets. [[http://www.cs.cornell.edu/home/kleinber/networks-book/]]** Reading: * **M. E. J. Newman: The structure and function of complex networks**, SIAM Review, Vol. 45, p. 167-256, 2003. ({{:wma:newman_2003.pdf|download pdf}}) * **A.-L. Barabasi. Linked. PLUME, Penguin Group, 2002.** * Duncan J. Watts. //Six Degrees: The Science of a Connected Age.// Norton, New York, 2003. * Anand Rajaraman, Jeffrey D. Ullman, Mining of Massive Datasets. [[http://infolab.stanford.edu/~ullman/pub/book.pdf]] Course on **Network Science** held by **Albert-Laszlo Barabasi** at Northeastern University, Boston, MA: [[http://barabasilab.neu.edu/courses/phys5116/|link]] ====== Calendar ====== ^ ^ Date ^ Topic ^ Learning material ^ Homework ^ |1. | Monday, 20.02.2012 | Introduction to Complex Network Analysis. | {{:wma:pedreschi.wmr.2012.01.pdf|slides}} | Read Chapter 1, 2 of Kleinberg's book. | |2. | Wednesday, 22.02.2012 | Lezione cancellata | | | |3. | Monday, 27.02.2012 | Lezione cancellata | | | |4. | Wednesday, 29.02.2012 | From graph theory to complex network analysis | {{:wma:pedreschi.wmr.2012.02.pdf|slides}} | Read Chapters 1 and 2 of Barabasi's book | |5. | Monday, 05.03.2012 | Basic network measures: degree, distance, clustering | | | |6. | Wednesday, 07.03.2012 | Random networks vs. real networks | {{:wma:pedreschi.wmr.2012.03.pdf|slides}} | Read Chapter 3 of Barabasi's book | |7. | Monday, 12.03.2012 | Small world, Strength of weak ties | {{:wma:pedreschi.wmr.2012.04.pdf|slides}} | **Reading**: Chapter 3 of Kleinberg's book, {{:wma:travers69smallworld.pdf|Milgram's small world experiment}}, {{:wma:watts-smallworld2003.pdf|Watts' email experiment}}, {{:wma:leskovec-im.pdf|Leskovec's IM experiment}}, {{:wma:granstrengthweakties.pdf|Granovetter's Strength of Weak Ties theory}}, {{:wma:pnas-2007-onnela-7332-6.pdf|Onnela et al.'s Strength of Weak Ties experiment}} **Homework**: prepare a short discussion of either the three small-world papers, or the two weak-ties papers, and discuss it at the lecture of March 26. For each paper, provide a sketch of main results, three strong points and three weak points. Turn in your short write-up/presentation in pdf format. | |8. | Wednesday, 14.03.2012 | Scale free networks | | Read Chapter 4 of Barabasi's book. [[http://barabasilab.neu.edu/courses/phys5116/|Barabasi Class 4]] | |9. | Monday, 19.03.2012 | Centrality measures | {{:wma:pedreschi.wmr.2012.05.centrality.pdf|slides}} | | |10. | Wednesday, 21.03.2012 | Network analytics with Cytoscape | | [[http://www.cytoscape.org/|Cytoscape website]] | |11. | Monday, 26.03.2012 | Student presentations (Small world & strenght of weak ties) | | | |12. | Wednesday, 28.03.2012 | Second assignment | | Network analysis with Cytoscape [[http://www.giuliorossetti.net/about/ongoing-works/datasets/|Datasets]] | |13. | Monday, 16.04.2012 | Dunbar's number | {{:wma:lezionedunbar16032012.pdf|slides}} | Guest lecturer: Luca Pappalardo (Dottorato di Ricerca in Informatica, Università di Pisa) | |14. | Monday, 23.04.2012 | Generative models: Small World model and Barabasi-Albert model (Preferential attachment) | [[http://barabasilab.neu.edu/courses/phys5116/content/Class5_NetSci_2012/05_CLASS_2012_The_Small_World.pdf|slides Barabasi]] [[http://barabasilab.neu.edu/courses/phys5116/content/Class7_NetSci_2012/07_CLASS_2012_BAmodel.pdf|slides Barabasi]] | Read Chapter 5 and 6 of Barabasi's book and Chapter 18 and 20 of Kleinberg's book. | |15. | Wednesday, 02.05.2012 | Diffusion, spreading, contagion, epidemics | {{:wma:07-cascading_leskovec_.pdf|slides Leskovec}}, {{:wma:08-cascades_leskovec_.pdf|slides Leskovec}} | Read Chapter 16 and 17 of Kleinberg's book. | |16. | Monday, 07.05.2012 | Student presentations (exercise 2, network analysis) | | |17. | Wednesday, 09.05.2012 | Link prediction | {{:wma:lezionerossettilinkprediction09.05.2012.pdf|slides}} | Guest lecturer: Giulio Rossetti (Dottorato di Ricerca in Informatica, Università di Pisa) | |18. | Monday, 13.05.2012 | Diffusion, spreading, contagion, epidemics (2) | {{:wma:09-contagion.pdf|slides Leskovec}} [[http://barabasilab.neu.edu/courses/phys5116/content/Class17_NetSci_2012/17_CLASS_2012_Spreading.ppt|slides Barabasi]] | Read Chapter 19 and 21 of Kleinberg's book. | |19. | Wednesday, 09.05.2012 | **Aula 28 del CNR di Pisa, dalle 14:30 alle 18:30** | **Lezione straordinaria** nell'ambito del workshop: "Tecnologie linguistiche: un nuovo rinascimento?". | **Ore 14:30-16:30 - la rete sociale dell'Inferno di Dante (Pedreschi, Tavoni et al.)** ed intervento dell'artista **Elisabetta Salvatori (Lettura del Canto V dell'Inferno)**. **Ore 16:30-18:30: {{:wma:homophily.pdf|Omofilia ed assortatività delle reti}}, guest lecturer Letterio Galletta** (Dottorato di Ricerca in Informatica, Università di Pisa) | |20. | Monday, 28.05.2012 | Community Discovery. Bow-tie structure of the Web and link analysis (PageRank and HITS, hints) | {{:wma:14-weakties.pdf|slides}} {{:wma:13-pagerank.pdf|slides}} | Read Chapters 13 and 14 of Kleinberg's book. Read {{:wma:communitydiscoverysurvey.pdf|A Classification for Community Discovery Methods in Complex Networks}}, by Michele Coscia, Fosca Giannotti and Dino Pedreschi (SNAM Journal, 2012) | |21. | Wednesday, 06.06.2012 |**Guest lecture: aula C1**| Human mobility and social ties | Guest lecturer: Paolo Cintia (Dottorato di Ricerca in Informatica, Università di Pisa) | |22. | Thursday, 21.06.2012 |**h 9:00 - Aula Seminari Ovest**| **Student seminars - final project** | ** Joint analysis of the social network of this class built by combining each student's ego network on Facebook.** | ====== Second Assignment ====== Network analysis with Cytoscape: deadline for reports submission 02/05/2012. ^ ^ Students ^ Chosen Datasets ^ |1. | Bennato - Martinelli | IMDB & Twitter Social | |2. | Conti - Tremamondo | DBLP & GTD | |3. | Ferretti - Lima | Foursquare checkin (30 min) & GTD | |4. | Ferrucci - Guarasci | DBLP & IMDB | |5. | Fontana - Maci | Foursquare checkin (15 min) & Twitter Mentions | |6. | Fulgeri | GTD & Twitter Social | |7. | Passeri | IMDB & Twitter Mentions | |8. | De Faveri - Marchini | DBLP & Twitter Mentions | |9. | Daga | IMDB & GTD | |10. | Isca - Chersoni | Osaka Social & Twitter Social | ====== Link alle edizioni precedenti ====== * Edizione 2011-2012 [[WMA20112012]] * Edizione 2010-2011 [[WMA20102011]] * Edizione 2008-2009 [[WMA20082009]]