CS 704 Artificial Intelligence Seminar (HWS 2018)

In this seminar, we study network analysis with application to various types of real-world networks.   

News

30.10:

Oral Presentation dates: 26-27 Nov, 9:00am-12:00pm. Presentations have a 30min slot each: 15 min presentation, 15 min Q&A. The order of presentation is the order of the topics. On 26th: topics 1.1->2.1 On 27th: 2.2->3.3 

 

05.10:

  • Introduction to Network Analysis Lecture date and time set: 16th October, 11:00, room C1.01. 
  • Bibliography added!

 

20.09: Kickoff meeting date set: 2nd of October!

19.09: Our slots are full now! However if you are interested, please send Ioana an email to be added to our waiting list. 

 

12.09: The topic list is out! Please email your choice to ioana(at)informatik.uni-mannheim.de ! 

Organization

Requirements

  • The report has to be written with Latex (Beginners are welcome)
  • No programming skills are required
  • Basic algebra
  • Some familiarity with/or interest to learn about network analysis
  • Good reading, communicating and writing in English

Goals

In this seminar, you will
  • Read, understand, and explore scientific literature
  • Summarize a current research topic in a concise report (10-15 pages)
Since a systematic, extensive literature review is not possible in the duration of the seminar, core bibliography (3-5 publications) will be provided! You are encouraged though to explore additional literature.

Evaluation

The final grade will consist of: 30% oral presentation and 70% written report.  

Schedule

  • Select at least one topic of interest from the list below, or by suggesting another related topic of your interest. Email your choice to ioana(at)informatik.uni-mannheim.de by 24th September.
  • Attend the kickoff meeting on: Tuesday, 2nd October
  • Attend the lecture Introduction to Network Analysis given by Dr. Ioana Hulpus on: Tuesday 16 Oct, 11:00, room C1.01
  • Give a 15 min presentation of one given publication on your topic on 26-27 November, 9:00-12:00 room C1.01.
  • Attend the lecture Introduction to Scientific Writing given by Dr. Ioana Hulpus on: TBD
  • Work independently towards a literature survey on your topic.
  • Submit by email a written report - a 10-15 page literature survey of your topic, by 15th January 2019, 23:59. 

 

 

 

Topics

The following list presents the main topics we will study during this seminar. If you are interesting in network analysis but for other topics, for example in network analysis for information retrieval, please do suggest your preference by email to Ioana and we will work together to define a suitable topic. 

1. Social capital - here, we study what is generally meant by social capital and how to measure it. We will look at different aspects of social capital such as:

  • 1.1 Strong and weak ties - how do social and economic relations classify as strong or weak and why do they matter?
  • 1.2 Embeddedness and economic performance - what does the network structure tell us about trust in economic relations?
  • 1.3 Structural holes and bridges - the social and economic advantage resulting from brokerage across structural holes. But is that sustainable?
  • 1.4 Social capital and inequality - the cost of social isolation, and what do networks tell us about phenomena such as inequalities on labor market, homophily, persistence of unemployment, segregation;
  • 1.5 Structure and tie strength in online social networks (OSN) - how do the relations in OSNs such as Facebook and Twitter look like?

 

2. Large scale structure of networks - here we study the structure of the network as a whole, and how this structure can be analysed to discover communities:

  • 2.1 Traditional community detection algorithms and their use on various types of networks: Girwan Newmann algorithm;
  • 2.2 Community detection algorithms on large networks: modularity optimization on citation networks to find scientific communities;
  • 2.3 Network formation and growth, preferential attachment: why do most real life networks (biological, social, WWW,etc) get to have very similar properties? 
  • 2.4 Growth models for particular networks: the growth of Wikipedia, semantic networks, etc.

 

3. Dynamics over social networks - here, we study how networks facilitate the spread of things, such as diseases, computer viruses, information, products, etc.:

  • 3.1 Models of epidemics (SIS and SIR) and how they can explain cascades on multiple types of networks;
  • 3.2 Viral marketing and word of mouth processes: the role of influentials in marketing and how to identify them in the network; What makes marketing viral?
  • 3.3 Collective action: what is the role of social networks in political participation, decision making and public opinion formation? How can this be modeled? 

 

If you have any question regarding the topics, or you want some more details on some topics of interest, please email ioana(at)informatik.uni-mannheim.de . 

Bibliography

1.1 Strong and Weak Ties

  • Granovetter, M. (1973). The Strength of Weak Ties. American Journal of Sociology, 78(6), 1360-1380.
  • Onnela, J.-P. , Saramäki, J. , Hyvönen, J. , Szabó, G., Lazer, D., Kaski, K., Kertész, J., & Barabási, A.-L. (2007). Structure and tie strengths in mobile communication networks. Proceedings of the National Academy of Sciences May 2007, 104 (18) 7332-7336; DOI: 10.1073/pnas.0610245104
  • Kossinets, G., Kleinberg, J., & Watts, D. (2008). The structure of information pathways in a social communication network. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '08). ACM, New York, NY, USA, 435-443. DOI: doi.org/10.1145/1401890.1401945

 

1.2 Embeddedness and Economic Performance

  • Uzzi, B. (1997). Social Structure and Competition in Interfirm Networks: The Paradox of Embeddedness. Administrative Science Quarterly, 42(1), 35-67. doi:10.2307/2393808
  • Shane, S., & Cable, D. (2002). Network Ties, Reputation, and the Financing of New Ventures. Management Science, 48(3), 364-381. 

 

1.3 Structural Holes and Bridges

  • Burt, R. (2004). Structural Holes and Good Ideas. American Journal of Sociology, 110(2), 349-399
  • Ahuja, G. (2000). Collaboration Networks, Structural Holes, and Innovation: A Longitudinal Study. Administrative Science Quarterly, 45(3), 425-455. doi:10.2307/2667105
  • Buskens, V., & Van de Rijt, A. (2008). Dynamics of Networks if Everyone Strives for Structural Holes. American Journal of Sociology, 114(2), 371-407. doi:10.1086/590674

 

1.4 Social Capital and Inequality

  • Currarini, S. , Jackson, M. O. and Pin, P. (2009), An Economic Model of Friendship: Homophily, Minorities, and Segregation. Econometrica, 77: 1003-1045. doi:10.3982/ECTA7528
  • Mouw, T. (2003). Social Capital and Finding a Job: Do Contacts Matter? American Sociological Review, 68(6), 868-898. 
  • Calvó-Armengol, A., & Jackson., M., O. (2004). The Effects of Social Networks on Employment and Inequality. American Economic Review, 94 (3): 426-454.

 

1.5 Structure and Tie Strength in Online Social Networks

  • Ellison, N. B., Steinfield, C. & Lampe, C. (2007), The Benefits of Facebook “Friends:” Social Capital and College Students’ Use of Online Social Network Sites. Journal of Computer‐Mediated Communication, 12: 1143-1168. doi:10.1111/j.1083-6101.2007.00367.x
  • Burke, M., Kraut, R., & Marlow., C. (2011). Social capital on facebook: differentiating uses and users. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI '11). ACM, New York, NY, USA, 571-580. DOI: doi.org/10.1145/1978942.1979023
  • Hofer, M., & Aubert, V. (2013). Perceived bridging and bonding social capital on Twitter: Differentiating between followers and followees. Comput. Hum. Behav. 29, 6 (November 2013), 2134-2142. DOI=http://dx.doi.org/10.1016/j.chb.2013.04.038
  • Huberman, B., Romero, D.M., & Wu, F (2008). Social networks that matter: Twitter under the microscope. First Monday, [S.l.], dec. 2008. ISSN 13960466.

 

2.1 Traditional Community Detection Algorithms*

  • **Fortunato, S., (2010). Community detection in graphs. Physics Reports, Volume 486, Issues 3–5, 2010, Pages 75-174, doi.org/10.1016/j.physrep.2009.11.002.
  • Girvan, M. & Newman,M. E. J. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences Jun 2002, 99 (12) 7821-7826; DOI: 10.1073/nas.122653799
  • *Please choose from article ** one additional community detection algorithm

 

2.2 Community Detection Algorithms on Large Networks

  • Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences Jun 2006, 103 (23) 8577-8582; DOI: 10.1073/pnas.0601602103
  • Gregory, S. (2010). Finding overlapping communities in networks by label propagation. New Journal of  Physics. 12 103018

 

2.3 Network Formation and Growth, Preferential Attachment

  • Barabasi. A.-L., & Albert, R.. (1999). Emergence of Scaling in Random Networks SCIENCE, 5439(285) : 509-512
  • Newman, M. (2001). Clustering and preferential attachment in growing networks. Physical Review E, 64, 025102
  • Abbasi, A., Hossain, L., & Leydesdorff, L. (2012). Betweenness centrality as a driver of preferential attachment in the evolution of research collaboration networks, Journal of Informetrics, Volume 6, Issue 3, 2012, Pages 403-412, ISSN 1751-1577, doi.org/10.1016/j.joi.2012.01.002.

 

2.4 Growth Models for Particular Networks

  • Kumar, R., Novak, J., & Tomkins, A. (2006). Structure and evolution of online social networks. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '06). ACM, New York, NY, USA, 611-617. DOI=http://dx.doi.org/10.1145/1150402.1150476
  • Capocci, A., Servedio, V. D. P. , Colaiori, F., Buriol, L. S., Donato, D., Leonardi, S., & Caldarelli, G. (2006) Preferential attachment in the growth of social networks: The internet encyclopedia Wikipedia , Phys. Rev. E 74, 036116
  • Mislove, A., Koppula, H. S., Gummadi, K. P., Druschel, P., & Bhattacharjee, B. (2008). Growth of the flickr social network. In Proceedings of the first workshop on Online social networks (WOSN '08). ACM, New York, NY, USA, 25-30. DOI: doi.org/10.1145/1397735.1397742
  • Steyvers, M., & Tenenbaum, J. B. (2005), The Large‐Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth. Cognitive Science, 29: 41-78. doi:10.1207/s15516709cog2901_3

 

3.1 Models of Epidemics (SIS, SIR)

  • Keeling, M. J., & Eames, K. T. . (2005). Networks and epidemic models. Journal of the Royal Society Interface, 2(4), 295–307. doi.org/10.1098/rsif.2005.0051
  • Hill, A. L.  Rand, D. G., Nowak, M. A., & Christakis, N. A. (2010). Emotions as infectious diseases in a large social network: the SISa model, Proceedings of the Royal Society. DOI: 10.1098/rspb.2010.1217.
  • Pastor-Satorras, R., & Vespignani, A. (2001) Epidemic Spreading in Scale-Free Networks. Physical Review Letters 86 (14), 3200-3203, American Physical Society;

 

3.2 Viral Marketing and Word Of Mouth Processes

  • Leskovec, J., Adamic, L. A., & Huberman, B. A. (2007). The dynamics of viral marketing. ACM Trans. Web 1, 1, Article 5 (May 2007). DOI=http://dx.doi.org/10.1145/1232722.1232727
  • Kempe, D., Kleinberg, J., & Tardos, E. (2003). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '03). ACM, New York, NY, USA, 137-146. DOI=http://dx.doi.org/10.1145/956750.956769
  • Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E., & Makse, H. A. (2010). Identification of influential spreaders in complex networks. Nature Physics volume 6, pages 888–893 
  •  

3.3 Collective Action

  • Siegel, D. (2009). Social Networks and Collective Action. American Journal of Political Science, 53(1), 122-138
  • Chwe, M. (1999). Structure and Strategy in Collective Action. American Journal of Sociology, 105(1), 128-156. doi:10.1086/210269
  • Watts, D. J., Dodds, P. S. (2007). Influentials, Networks, and Public Opinion Formation. Journal of Consumer Research, 34(4), 441-458. doi:10.1086/518527